2018/03/06 by Tonello, Elisa, Farcot, Etienne, Chaouiya, Claudine
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1803.02095
We consider the following question on the relationship between the asymptotic behaviours of asynchronous dynamics of Boolean networks and their regulatory structures: does the presence of a cyclic attractor imply the existence of a local negative circuit in the regulatory graph? When the number of model components n verifies n ≥ 6, the answer is known to be negative. We show that the question can be translated into a Boolean satisfiability problem on n ⋅ 2n variables. A Boolean formula expressing the absence of local negative circuits and a necessary condition for the existence of cyclic attractors is found unsatisfiable for n ≤ 5. In other words, for Boolean networks with up to 5 components, the presence of a cyclic attractor requires the existence of a local negative circuit.