Abstract
Various threshold Boolean networks (TBNs), a formalism used to model different types of biological networks (genes notably), can produce similar dynamics, i.e. share same behaviors. Among them, some are complex (according to Kolmogorov complexity), others not. By computing both structural and behavioral complexities, we show that most TBNs are structurally complex, even those having simple behaviors. For this purpose, we developed a new method to compute the structural complexity of a TBN based on estimates of the sizes of equivalence classes of the threshold Boolean functions composing the TBN.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
The \(^*\) operator is the usual Kleene star, denoting any number of repetitions of a substring.
References
Barthe F, Guedon O, Mendelson S, Naor A (2005) A probabilistic approach to the geometry of the \(l_p^n\)-ball. Ann Prob 2:480–513
Ben Amor H, Corblin F, Fanchon E, Elena A, Trilling L, Demongeot J, Glade N (2013) Formal methods for hopfield-like networks. Acta Biotheor 61:21–39
Bornhold S (2008) Boolean network models of cellular regulation: prospects and limitations. J R Soc Interface 5:S85–S94
Corblin F, Tripodi S, Fanchon E, Ropers D, Trilling L (2009) A declarative constraint-based method for analyzing discrete genetic regulatory networks. Biosystems 2:91–104
Didonato AR, Morris AH Jr (1992) Algorithm 708: Significant digit computation of the incomplete beta function ratios. ACM Trans Math Softw 18:360–373
Elena A (2009) Robustesse des réseaux d’automates booléens à seuil aux modes d’itération. Application la modélisation des réseaux de régulation génétique. Ph.D. Thesis (French), Université Joseph Fourier. https://tel.archives-ouvertes.fr/tel-00447564/
Gebser M, Kaminski R, Kaufmann B, Ostrowski M, Schaub T, Schneider M (2011) Potassco: the potsdam answer set solving collection. AI Comm 24:107–124
Glass L, Kauffman S (1973) The logical analysis of continuous, nonlinear biochemical control networks. J Theor Biol 39:103–129
Goldford JE, Segr D (2018) Modern view of ancient metabolic networks. Curr Opin Syst Biol 8:117–124
Hopfield JJ (1982) Neural networks and physical systems with emergent collective computational abilities. Proc Natl Acad Sci USA 79:2554–2558
Kauffman S (1969) Metabolic stability and epigenesis in randomly constructed genetic nets. J Theor Biol 22:437–467
Kolmogorov AN (1968) Three approaches to the quantitative definition of information. Int J Comp Math 2:157–168
McCulloch WS, Pitts W (1943) A logical calculus of the ideas immanent in nervous activity. Bull Math Biophys 5:115–133
Mendoza L, Alvarez-Buylla ER (1998) Dynamics of the genetic regulatory network for Arabidopsis thaliana flower morphogenesis. J Theor Biol 193:307–319
Sol R, Oll-Vila A, Vidiella B, Duran-Nebreda S, Conde-Pueyo N (2018) The road to synthetic multicellularity. Curr Opin Syst Biol 7:1–8
Soler-Toscano F, Zenil H, Delahaye J-P, Gauvrit N (2014) Calculating Kolmogorov complexity from the output frequency distributions of small turing machines. PLoS ONE 9:e96223
Solomonoff RJ (1960) A preliminary report on a general theory of inductive inference, Report ZTB-138. Zator Co., Cambridge, MA
Thomas R (1980) On the relation between the logical structure of systems and their ability to generate multiple steady states or sustained oscillations. Springer Ser Synerg 9:180–193
Tran V, McCall MN, McMurray HR, Almudevar A (2013) On the underlying assumptions of threshold Boolean networks as a model for genetic regulatory network behavior. Frontiers Gen 4:263
Vincent M (2011) Cancer: a de-repression of a default survival program common to all cells. BioEssays 34:72–82
Vuong Q-T, Chauvin R, Ivanov S, Glade N, Trilling L (2017) A logical constraint-based approach to infer and explore diversity and composition in threshold Boolean automaton networks, studies in computational intelligence series. In: Proceedings of the complex networks 2017 conference. https://doi.org/10.1007/978-3-319-72150-7_46
Wan Tsang W, Marsaglia G (2000) The Ziggurat method for generating random variables. J Stat Soft 05:1–7
Wang X (2005) Volumes of generalized unit balls. Math Mag 78:390–395
Zañudo JGT, Aldana M, Martínez-Mekler G (2011) Boolean threshold networks: virtues and limitations for biological modeling. In: Niiranen S, Ribeiro A (eds) Information processing and biological systems. Intelligent systems reference library, vol 11. Springer, Berlin
Zenil H, Hernández-Orozco S, Kiani NA, Soler-Toscano F, Rueda-Toicen A, Tegnér J (2018) A decomposition method for global evaluation of Shannon entropy and local estimations of algorithmic complexity. Entropy 20
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Christen, U., Ivanov, S., Segretain, R. et al. On Computing Structural and Behavioral Complexities of Threshold Boolean Networks. Acta Biotheor 68, 119–138 (2020). https://doi.org/10.1007/s10441-019-09358-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10441-019-09358-8