Asynchronous Boolean networks are a type of discrete dynamical system in which each variable can take one of two states, and a single variable state is updated in each time step according to pre-selected rules. Boolean networks are popular in systems biology due to their ability to model long-term biological phenotypes within a qualitative, predictive framework. Boolean networks model phenotypes as attractors, which are closely linked to minimal trap spaces (inescapable hypercubes in the system's state space). In biological applications, attractors and minimal trap spaces are typically in one-to-one correspondence. However, this correspondence is not guaranteed: motif-avoidant attractors (MAAs) that lie outside minimal trap spaces are possible. MAAs are rare and poorly understood, despite recent efforts. In this contribution to the BMB & JMB Special Collection "Problems, Progress and Perspectives in Mathematical and Computational Biology", we summarize the current state of knowledge regarding MAAs and present several novel observations regarding their response to node deletion reductions and linear extensions of edges. We conduct large-scale computational studies on an ensemble of 14 000 models derived from published Boolean models of biological systems, and more than 100 million Random Boolean Networks. Our findings quantify the rarity of MAAs; in particular, we only observed MAAs in biological models after applying standard simplification methods, highlighting the role of network reduction in introducing MAAs into the dynamics. We also show that MAAs are fragile to linear extensions: in sparse networks, even a single linear node can disrupt virtually all MAAs. Motivated by this observation, we improve the upper bound on the number of delays needed to disrupt a motif-avoidant attractor.

Department of Physics Davey Laboratory Pennsylvania State University 16802 University Park Pennsylvania USA

Department of Systems Science and Industrial Engineering Binghamton University Engineering Building 13850 Vestal New York USA

Faculty of Informatics Masaryk University Botanicka 68a 60200 Brno Czech Republic

Institute of Science and Technology Austria Am Campus 1 3400 Klosterneuburg Austria

See more in PubMed

Abou-Jaoudé W, Traynard P, Monteiro PT, Saez-Rodriguez J, Helikar T, Thieffry D, Chaouiya C (2016) Logical modeling and dynamical analysis of cellular networks. Front Genet 7:94. 10.3389/fgene.2016.00094 PubMed PMC

Akman OE, Wareham BJ, Doherty K (2023) BDEtools: A MATLAB package for Boolean delay equation modeling. J Comput Biol 30(1):52–69. 10.1089/cmb.2021.0658 PubMed

Albert R, Othmer HG (2003) The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in Drosophila melanogaster. J Theor Biol 223(1):1–18. 10.1016/S0022-5193(03)00035-3 PubMed PMC

Albert I, Thakar J, Li S, Zhang R, Albert R (2008) Boolean network simulations for life scientists. Source Code Biol Med 3:1–8 PubMed PMC

Aldana M, Coppersmith S, Kadanoff LP (2003) Boolean dynamics with random couplings. Perspectives and problems in nolinear science: A celebratory Volume in Honor of Lawrence Sirovich, 23–89

Beneš N, Brim L, Kadlecaj J, Pastva S, Šafránek D (2022) Exploring attractor bifurcations in Boolean networks. BMC Bioinformatics 23(1):173 PubMed PMC

Beneš N, Brim L, Huvar O, Pastva S, Šafránek D, Šmijáková E (2022) AEON.py: Python library for attractor analysis in asynchronous Boolean networks. Bioinformatics 38(21):4978–4980 PubMed

Beneš N, Brim L, Kadlecaj J, Pastva S, Šafránek D (2020) AEON: attractor bifurcation analysis of parametrised Boolean networks. In: Computer Aided Verification: 32nd International Conference, CAV 2020, Los Angeles, CA, USA, July 21–24, 2020, Proceedings, Part I 32, pp. 569–581. Springer

Beneš N, Brim L, Pastva S, Šafránek D (2021) Computing bottom SCCs symbolically using transition guided reduction. In: Computer Aided Verification: 33rd International Conference, CAV 2021, Virtual Event, July 20–23, 2021, Proceedings, Part I 33, pp. 505–528. Springer

Brim L, Pastva S, Šafránek D, Šmijáková E (2023) Temporary and permanent control of partially specified Boolean networks. Biosystems 223:104795 PubMed

Cheng X, Socolar JE, Sun M (2013) Autonomous Boolean modelling of developmental gene regulatory networks. J R Soc Interface 10(78):20120574. 10.1098/rsif.2012.0574 PubMed PMC

Cifuentes-Fontanals L, Tonello E, Siebert H (2022) Control in Boolean networks with model checking. Frontiers in Applied Mathematics and Statistics 8:838546

Correia RB, Gates AJ, Wang X, Rocha LM (2018) Cana: A python package for quantifying control and canalization in boolean networks. Front Physiol 9:1046. 10.3389/fphys.2018.01046 PubMed PMC

Costa FX, Rozum JC, Marcus AM, Rocha LM (2023) Effective connectivity and bias entropy improve prediction of dynamical regime in automata networks. Entropy 25(2):374. 10.3390/e25020374 PubMed PMC

Dahlhaus M, Burkovski A, Hertwig F, Mussel C, Volland R, Fischer M, Debatin K-M, Kestler HA, Beltinger C (2016) Boolean modeling identifies Greatwall/MASTL as an important regulator in the AURKA network of neuroblastoma. Cancer Lett 371(1):79–89. 10.1016/j.canlet.2015.11.025 PubMed

Gates AJ, Brattig Correia R, Wang X, Rocha LM (2021) The effective graph reveals redundancy, canalization, and control pathways in biochemical regulation and signaling. Proc Natl Acad Sci 118(12):2022598118. 10.1073/pnas.2022598118 PubMed PMC

Gonzalez AG, Naldi A, Sanchez L, Thieffry D, Chaouiya C (2006) Ginsim: a software suite for the qualitative modelling, simulation and analysis of regulatory networks. Biosystems 84(2):91–100 PubMed

Greil F, Drossel B (2005) Dynamics of critical Kauffman networks under asynchronous stochastic update. Phys Rev Lett 95:048701. 10.1103/PhysRevLett.95.048701 PubMed

Gupta S, Silveira DA, Hashimoto RF, Mombach JCM (2022) A Boolean model of the proliferative role of the lncrna XIST in non-small cell lung cancer cells. Biology 11(4):480 PubMed PMC

Harris SE, Sawhill BK, Wuensche A, Kauffman S (2002) A model of transcriptional regulatory networks based on biases in the observed regulation rules. Complexity 7(4):23–40. 10.1002/cplx.10022

Helikar T, Kowal B, McClenathan S, Bruckner M, Rowley T, Madrahimov A, Wicks B, Shrestha M, Limbu K, Rogers JA (2012) The Cell Collective: toward an open and collaborative approach to systems biology. BMC Syst Biol 6:1–14 PubMed PMC

Jarrah AS, Raposa B, Laubenbacher R (2007) Nested canalyzing, unate cascade, and polynomial functions. Physica D 233(2):167–174. 10.1016/j.physd.2007.06 PubMed PMC

Kadelka C, Butrie T-M, Hilton E, Kinseth J, Schmidt A, Serdarevic H (2024) A meta-analysis of Boolean network models reveals design principles of gene regulatory networks. Sci Adv 10(2):0822 PubMed PMC

Kauffman SA (1969) Metabolic stability and and epigenesis in randomly constructed genetic nets. J Theor Biol 22:437–467 PubMed

Kaufman V, Mihaljev T, Drossel B (2005) Scaling in critical random Boolean networks. Phys Rev E 72:046124. 10.1103/PhysRevE.72.046124 PubMed

Klarner H, Siebert H (2015) Approximating attractors of Boolean networks by iterative CTL model checking. Frontiers in Bioengineering and Biotechnology 3:130. 10.3389/fbioe.2015.00130 PubMed PMC

Klarner H, Bockmayr A, Siebert H (2015) Computing maximal and minimal trap spaces of Boolean networks. Nat Comput 14:535–544

Klemm K, Bornholdt S (2005) Stable and unstable attractors in Boolean networks. Phys Rev E 72:055101. 10.1103/PhysRevE.72.055101 PubMed

Malik-Sheriff RS, Glont M, Nguyen TV, Tiwari K, Roberts MG, Xavier A, Vu MT, Men J, Maire M, Kananathan S et al (2020) BioModels –15 years of sharing computational models in life science. Nucleic Acids Res 48(D1):407–415 PubMed PMC

Manicka S, Marques-Pita M, Rocha L (2022) Effective connectivity determines the critical dynamics of biochemical networks. J R Soc Interface 19:20210659. 10.1098/rsif.2021.0659 PubMed PMC

Moon K, Lee K, Paulevé L (2022) Computational complexity of minimal trap spaces in Boolean networks. arXiv preprint arXiv:2212.12756

Mori T, Akutsu T (2022) Attractor detection and enumeration algorithms for Boolean networks. Comput Struct Biotechnol J 20:2512–2520 PubMed PMC

Naldi A, Rémy E, Thieffry D, Chaouiya C (2011) Dynamically consistent reduction of logical regulatory graphs. Theoret Comput Sci 412(21):2207–2218. 10.1016/j.tcs.2010.10.021. (

Naldi A, Richard A, Tonello E (2023) Linear cuts in Boolean networks. Nat Comput 22:431–451. 10.1007/s11047-023-09945-2

Orlando DA, Lin CY, Bernard A, Wang JY, Socolar JE, Iversen ES, Hartemink AJ, Haase SB (2008) Global control of cell-cycle transcription by coupled CDK and network oscillators. Nature 453:944–947. 10.1038/nature06955 PubMed PMC

Ostaszewski M, Mazein A, Gillespie ME, Kuperstein I, Niarakis A, Hermjakob H, Pico AR, Willighagen EL, Evelo CT, Hasenauer J et al (2020) COVID-19 Disease Map, building a computational repository of SARS-CoV-2 virus-host interaction mechanisms. Scientific data 7(1):136 PubMed PMC

Park KH, Costa FX, Rocha LM, Albert R, Rozum JC (2023) Models of cell processes are far from the edge of chaos. PRX Life 1:023009. 10.1103/PRXLife.1.023009 PubMed PMC

Pastva S, Šafránek D, Beneš N, Brim L, Henzinger T (2023) Repository of logically consistent real-world Boolean network models. bioRxiv, 2023–06

Paul S, Su C, Pang J, Mizera A (2019) An efficient approach towards the source-target control of Boolean networks. IEEE/ACM Trans Comput Biol Bioinf 17(6):1932–1945 PubMed

Paulevé L, Richard A (2012) Static analysis of Boolean networks based on interaction graphs: a survey. Electronic Notes in Theoretical Computer Science 284:93–104

Paulevé L, Kolćák J, Chatain T, Haar S (2020) Reconciling qualitative, abstract, and scalable modeling of biological networks. Nat Commun 11:4256. 10.1038/s41467-020-18112-5 PubMed PMC

Richard A (2010) Negative circuits and sustained oscillations in asynchronous automata networks. Adv Appl Math 44(4):378–392. 10.1016/j.aam.2009.11.011

Richard A, Comet J-P (2007) Necessary conditions for multistationarity in discrete dynamical systems. Discret Appl Math 155(18):2403–2413. 10.1016/j.dam.2007.04.019

Richard A, Tonello E (2023) Attractor separation and signed cycles in asynchronous Boolean networks. Theoret Comput Sci 947:113706. 10.1016/j.tcs.2023.113706

Rozum JC, Zanudo JGT, Gan X, Deritei D, Albert R (2021) Parity and time reversal elucidate both decision-making in empirical models and attractor scaling in critical Boolean networks. Sci Adv 7(29):8124. 10.1126/sciadv.abf8124 PubMed PMC

Rozum JC, Deritei D, Park KH, Gómez Tejeda Zañudo J, Albert R (2022) pystablemotifs: Python library for attractor identification and control in Boolean networks. Bioinformatics 38(5):1465–1466 PubMed

Rozum JC, Campbell C, Newby E, Nasrollahi FSF, Albert R (2024) Boolean networks as predictive models of emergent biological behaviors. Elements in the structure and dynamics of complex networks. Cambridge University Press, Cambridge, UK

Sánchez-Villanueva JA, Rodríguez-Jorge O, Ramírez-Pliego O, Rosas Salgado G, Abou-Jaoudé W, Hernandez C, Naldi A, Thieffry D, Santana MA (2019) Contribution of ROS and metabolic status to neonatal and adult CD8+ T cell activation. PLoS ONE 14(12):1–12. 10.1371/journal.pone.0226388 PubMed PMC

Schwab JD, Kühlwein SD, Ikonomi N, Kühl M, Kestler HA (2020) Concepts in Boolean network modeling: What do they all mean? Comput Struct Biotechnol J 18:571–582. 10.1016/j.csbj.2020.03.001 PubMed PMC

Shmulevich I, Kauffman SA (2004) Activities and sensitivities in boolean network models. Phys Rev Lett 93:048701. 10.1103/PhysRevLett.93.048701 PubMed PMC

Subbaroyan A, Martin OC, Samal A (2022) Minimum complexity drives regulatory logic in Boolean models of living systems. PNAS Nexus 1(1):017. 10.1093/pnasnexus/pgac017 PubMed PMC

Thomas R (1973) Boolean formalization of genetic control circuits. J Theor Biol 42:563–585 PubMed

Tonello E, Paulevé L (2023) Attractor identification in asynchronous Boolean dynamics with network reduction. In: International Conference on Computational Methods in Systems Biology, pp. 202–219. Springer

Trinh V-G, Park KH, Pastva S, Rozum JC (2024) Mapping the attractor landscape of Boolean networks. bioRxiv 10.1101/2024.09.30.615897 PubMed PMC

Van Giang T, Hiraishi K (2021) An improved method for finding attractors of large-scale asynchronous Boolean networks. In: 2021 IEEE Conference on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB), pp. 1–9. IEEE

Veliz-Cuba A (2011) Reduction of Boolean network models. J Theor Biol 289:167–172. 10.1016/j.jtbi.2011.08.042 PubMed

Zañudo JG, Albert R (2013) An effective network reduction approach to find the dynamical repertoire of discrete dynamic networks. Chaos: An Interdisciplinary Journal of Nonlinear Science, 23(2) PubMed