Topology and Dynamics of Biological Networks

Complex networks have been of great interests in many disciplines including mathematics, computer science, biology, and social studies. In molecular biology, networks can be used to model the interacts within a biological system. 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 certain Boolean network model for biological networks. Under this model, the reverse engineering problem is naturally related to the Satisfiability Problem. We will show the following results. (1). The decision problem for network solution can be solved in polynomial time.
That is, given information on dynamics, there is a polynomial time algorithm that determines either (a) there is no network which yields the given dynamics or (b) there is such a network. In the case of (b), the algorithm provides a specific network solution. (2). The problem of finding a minimal network with the given property of dynamics is NP-hard.