|
Organizers |
Computational complexity for topology and dynamics of boolean networks
by
Yongwu Rong
George Washington University
Coauthors: Rahul Simha, Guanyu Wang, Chen Zeng.
Networks have been of great interests in many areas in recent years. Such a network often consists of units with various levels of activities that evolve over time, mathematically represented by the dynamics of the network. The interaction between units is represented by the topology of a graph. An interesting problem is to study the connection between topology and dynamics of such networks. In particular, the so called reverse engineering problem asks for the topology of the network given information on its dynamics.
In this talk, we focus on a specific Boolean network model for biological networks. Under this model, the reverse engineering problem is naturally related to the Satisfiability Problem. We explain our results that (1) the decision problem can be solved in polynomial time, and (2) the problem of finding the minimal network solution is NP-hard.
Date received: May 15, 2010
Copyright © 2010 by the author(s). The author(s) of this work and the organizers of the conference have granted their consent to include this abstract in Topology Atlas. Document # cbaf-24.