Local negative circuits and cyclic attractors in Boolean networks with at most five components

Tonello, Elisa; Farcot, Etienne; Chaouiya, Claudine

Abstract

We consider the following question on the relationship between the asymptotic behaviors 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 to be 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.

Citation

Tonello, E., Farcot, E., & Chaouiya, C. (2019). Local negative circuits and cyclic attractors in Boolean networks with at most five components. SIAM Journal on Applied Dynamical Systems, 18(1), 68-79. https://doi.org/10.1137/18m1173988

• Journal Article Type: Article
• Acceptance Date: Oct 12, 2018
• Online Publication Date: Jan 15, 2019
• Publication Date: Jan 15, 2019
• Deposit Date: Jan 18, 2019
• Publicly Available Date: Jan 21, 2019
• Journal: SIAM Journal on Applied Dynamical Systems
• Print ISSN: 1536-0040
• Electronic ISSN: 1536-0040
• Publisher: Society for Industrial and Applied Mathematics
• Peer Reviewed: Peer Reviewed
• Volume: 18
• Issue: 1
• Pages: 68-79
• DOI: https://doi.org/10.1137/18m1173988
• Keywords: Modelling and Simulation; Analysis
• Public URL: https://nottingham-repository.worktribe.com/output/1481812
• Publisher URL: https://epubs.siam.org/doi/10.1137/18M1173988