Preprint 2014-30
Julio Aracena, Luis Gomez, Lilian Salinas:
Complexity of limit cycle existence and feasibility problems in Boolean networks
Abstract:
Boolean networks have been used as models of gene regulation and other biological networks. One key element in the dynamical behavior of the networks are the limit cycles, which are very sensitive to changes in the update schedule used. In this paper we study two problems related to the inferring of update schemes and limit cycles in Boolean networks: Limit Cycle Existence problem and Feasible Limit Cycle problem. We explore in families of Boolean networks with different types of local activation function and structural properties of the interaction digraph to define the sharp delineation of the algorithmic complexity for both problems. We show that they are NP-Hard for different deterministic update schedules, even in AND-OR Boolean networks or with symmetric interaction digraph. However, they are polynomial problems in the case of verifying both conditions. As particular example of this, we prove that in the case of AND-OR networks with symmetric interaction digraph, there exists a limit cycle in a network iterated with a block-sequential update if and only if there exists a limit cycle with parallel scheme. This last condition is equivalent to a topological property on the network which can be verified in polynomial time.
