# American Institute of Mathematical Sciences

December  2011, 4(6): 1629-1640. doi: 10.3934/dcdss.2011.4.1629

## Dynamics of boolean networks

 1 Department of Mathematical Sciences, University of Wisconsin-Milwaukee, Milwaukee, United States

Received  March 2009 Revised  October 2009 Published  December 2010

Boolean networks are special types of finite state time-discrete dynamical systems. A Boolean network can be described by a function from an $n$-dimensional vector space over the field of two elements to itself. A fundamental problem in studying these dynamical systems is to link their long term behaviors to the structures of the functions that define them. In this paper, a method for deriving a Boolean network's dynamical information via its disjunctive normal form is explained. For a given Boolean network, a matrix with entries $0$ and $1$ is associated with the polynomial function that represents the network, then the information on the fixed points and the limit cycles is derived by analyzing the matrix. The described method provides an algorithm for the determination of the fixed points from the polynomial expression of a Boolean network. The method can also be used to construct Boolean networks with prescribed limit cycles and fixed points. Examples are provided to explain the algorithm.
Citation: Yi Ming Zou. Dynamics of boolean networks. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1629-1640. doi: 10.3934/dcdss.2011.4.1629
##### References:
 [1] R. Albert and H. Othmer, The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in Drosophila melanogaster,, J. Theor. Biol., 223 (2003), 1. doi: 10.1016/S0022-5193(03)00035-3. Google Scholar [2] C. L. Barrett, W. Y. C. Chen and M. J. Zheng, Discrete dynamical systems on graphs and boolean functions,, Math. Comput. Simul., 66 (2004), 487. doi: 10.1016/j.matcom.2004.03.003. Google Scholar [3] D. Bollman, O. Coló-Reyes and E. Orozco, Fixed points in discrete models for regulatory genetic networks,, EURASIP Journal on Bioinformatics and System Biology, (2007). Google Scholar [4] G. Boole, "The Mathematical Analysis of Logic, Being an Essay Towards a Calculus of Deductive Reasoning,", Macmillan, (1847). Google Scholar [5] G. Boole, "An Investigation of the Laws of Thought, on Which are Founded the Mathematical Theories of Logic and Probabilities,", Macmillan, (1960). Google Scholar [6] M. Brickenstein and A. Dreyer, PolyBoRi: A framework for Gröbner-basis computations with Boolean polynomials,, J. Symbolic Comput., 44 (2009), 1326. doi: 10.1016/j.jsc.2008.02.017. Google Scholar [7] M. Brickenstein, A. Dreyer, G-M. Greuel, M. Wedler and O. Wienand, New developments in the theory of Gröbner bases and applications to formal verification,, J. Pure Appl. Algebra, 213 (2009), 1612. Google Scholar [8] O. Colón-Reyes, R. Laubenbacher and B. Pareigis, Boolean monomial dynamical systems,, Annals of Combinatorics, 8 (2004), 425. Google Scholar [9] M. I. Davidich and S. Bornholdt, Boolean network model predicts cell cycle sequence of fission yeast,, PLoS ONE, 3 (2008). Google Scholar [10] E. Dubrova, M. Teslenko and A. Martinelli, Kauffman networks: Analysis and applications,, Computer-Aided Design, (2005), 479. doi: 10.1109/ICCAD.2005.1560115. Google Scholar [11] E. D. Fabricius, "Modern Digital Design and Switching Theory,", CRC Press 1992., (1992). Google Scholar [12] J. F. Groote and M. Keinänen, A sub-quadratic algorithm for conjunctive and disjunctive BESs,, Theoretical aspects of computing-ICTAC 2005, 3722 (2005), 532. Google Scholar [13] R. A. Hernádez-Toledo, Linear finite dynamical systems,, Communications in Algebra, 33 (2005), 2977. doi: 10.1081/AGB-200066211. Google Scholar [14] A. Ilichinsky, "Cellular Automata: A Discrete Universe,", World Scientific Publishing Company, (2001). Google Scholar [15] A. Jarrah, R. Laubenbacher, B. Stigler and M. Stillman, Reverse-engineering of polynomial dynamical systems,, Adv. in Appl. Math., 39 (2007), 477. Google Scholar [16] A. Jarrah, B. Raposa and R. Laubenbacher, Nested canalyzing, unate cascade, and polynomial functions,, Physica D, 233 (2007), 167. Google Scholar [17] A. Jarrah, R. Laubenbacher and A. Veliz-Cuba, The dynamics of conjunctive and disjunctive Boolean networks,, preprint available at: \arXiv{0805.0275v1}., (). Google Scholar [18] W. Just, The steady state system problem is NP-hard even for monotone quadratic Boolean dynamical systems,, preprint available at: \url{http://www.math.ohiou.edu/ just/publ.html}., (). Google Scholar [19] S. Kauffman, C. Peterson, B. Samuelsson and C. Troein, Genetic networks with canalyzing Boolean rules are always stable,, PNAS, 101 (2004), 17102. doi: 10.1073/pnas.0407783101. Google Scholar [20] R. Laubenbacher and B. Stigler, A computational algebra approach to the reverse engineering of gene regulatory networks,, J. Theor. Biol., 229 (2004), 523. Google Scholar [21] T. E. Malloy, J. Butner and G. C. Jensen, The emergence of dynamic form through phase relations in dynamic systems,, Nonlinear Dynamics, 12 (2008), 371. Google Scholar [22] R. Pal, I. Ivanov, A. Datta, M. L. Bittner and E. R. Dougherty, Generating Boolean networks with a prescribed attractor structure,, Bioinformatics, 21 (2005), 4021. doi: 10.1093/bioinformatics/bti664. Google Scholar [23] J. Reger and K. Schmidt, Modeling and analyzing finite state automata in the finite field $F_2$,, Mathematics and Computers in Simulation, 66 (2004), 193. doi: 10.1016/j.matcom.2003.11.005. Google Scholar [24] N. A. W. Riel, Dynamic modelling and analysis of biochemical networks: mechanism-based models and model-based experiments,, Briefings in Bioinformatics, 7 (2006), 364. doi: 10.1093/bib/bbl040. Google Scholar [25] S. Rudeanu, "Boolean Functions and Equations,", North-Holland, (1974). Google Scholar [26] M. H. Stone, The theory of representation for Boolean algebras,, Transactions of American Mathematical Society, 40 (1936), 37. Google Scholar [27] T. Tamura and T. Akutsu, Algorithms for singleton attractor detection in planar and nonplanar AND/OR Boolean networks,, Math. Comput. Sci., 2 (2009), 401. doi: 10.1007/s11786-008-0063-5. Google Scholar [28] C. J. Tomlin and J. D. Aelrod, Biology by numbers: Mathematical modelling in developmental biology,, Nature Reviews Genetics, 8 (2007), 331. doi: 10.1038/nrg2098. Google Scholar [29] S-Q. Zhang, M. Hayashida, T. Akutsu, W-K. Ching and M. K. Ng, Algorithms for finding small attractors in Boolean networks,, EURASIP Journal on Bioinformatics and Systems Biology (2007)., (2007). doi: 10.1155/2007/20180. Google Scholar

show all references

##### References:
 [1] R. Albert and H. Othmer, The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in Drosophila melanogaster,, J. Theor. Biol., 223 (2003), 1. doi: 10.1016/S0022-5193(03)00035-3. Google Scholar [2] C. L. Barrett, W. Y. C. Chen and M. J. Zheng, Discrete dynamical systems on graphs and boolean functions,, Math. Comput. Simul., 66 (2004), 487. doi: 10.1016/j.matcom.2004.03.003. Google Scholar [3] D. Bollman, O. Coló-Reyes and E. Orozco, Fixed points in discrete models for regulatory genetic networks,, EURASIP Journal on Bioinformatics and System Biology, (2007). Google Scholar [4] G. Boole, "The Mathematical Analysis of Logic, Being an Essay Towards a Calculus of Deductive Reasoning,", Macmillan, (1847). Google Scholar [5] G. Boole, "An Investigation of the Laws of Thought, on Which are Founded the Mathematical Theories of Logic and Probabilities,", Macmillan, (1960). Google Scholar [6] M. Brickenstein and A. Dreyer, PolyBoRi: A framework for Gröbner-basis computations with Boolean polynomials,, J. Symbolic Comput., 44 (2009), 1326. doi: 10.1016/j.jsc.2008.02.017. Google Scholar [7] M. Brickenstein, A. Dreyer, G-M. Greuel, M. Wedler and O. Wienand, New developments in the theory of Gröbner bases and applications to formal verification,, J. Pure Appl. Algebra, 213 (2009), 1612. Google Scholar [8] O. Colón-Reyes, R. Laubenbacher and B. Pareigis, Boolean monomial dynamical systems,, Annals of Combinatorics, 8 (2004), 425. Google Scholar [9] M. I. Davidich and S. Bornholdt, Boolean network model predicts cell cycle sequence of fission yeast,, PLoS ONE, 3 (2008). Google Scholar [10] E. Dubrova, M. Teslenko and A. Martinelli, Kauffman networks: Analysis and applications,, Computer-Aided Design, (2005), 479. doi: 10.1109/ICCAD.2005.1560115. Google Scholar [11] E. D. Fabricius, "Modern Digital Design and Switching Theory,", CRC Press 1992., (1992). Google Scholar [12] J. F. Groote and M. Keinänen, A sub-quadratic algorithm for conjunctive and disjunctive BESs,, Theoretical aspects of computing-ICTAC 2005, 3722 (2005), 532. Google Scholar [13] R. A. Hernádez-Toledo, Linear finite dynamical systems,, Communications in Algebra, 33 (2005), 2977. doi: 10.1081/AGB-200066211. Google Scholar [14] A. Ilichinsky, "Cellular Automata: A Discrete Universe,", World Scientific Publishing Company, (2001). Google Scholar [15] A. Jarrah, R. Laubenbacher, B. Stigler and M. Stillman, Reverse-engineering of polynomial dynamical systems,, Adv. in Appl. Math., 39 (2007), 477. Google Scholar [16] A. Jarrah, B. Raposa and R. Laubenbacher, Nested canalyzing, unate cascade, and polynomial functions,, Physica D, 233 (2007), 167. Google Scholar [17] A. Jarrah, R. Laubenbacher and A. Veliz-Cuba, The dynamics of conjunctive and disjunctive Boolean networks,, preprint available at: \arXiv{0805.0275v1}., (). Google Scholar [18] W. Just, The steady state system problem is NP-hard even for monotone quadratic Boolean dynamical systems,, preprint available at: \url{http://www.math.ohiou.edu/ just/publ.html}., (). Google Scholar [19] S. Kauffman, C. Peterson, B. Samuelsson and C. Troein, Genetic networks with canalyzing Boolean rules are always stable,, PNAS, 101 (2004), 17102. doi: 10.1073/pnas.0407783101. Google Scholar [20] R. Laubenbacher and B. Stigler, A computational algebra approach to the reverse engineering of gene regulatory networks,, J. Theor. Biol., 229 (2004), 523. Google Scholar [21] T. E. Malloy, J. Butner and G. C. Jensen, The emergence of dynamic form through phase relations in dynamic systems,, Nonlinear Dynamics, 12 (2008), 371. Google Scholar [22] R. Pal, I. Ivanov, A. Datta, M. L. Bittner and E. R. Dougherty, Generating Boolean networks with a prescribed attractor structure,, Bioinformatics, 21 (2005), 4021. doi: 10.1093/bioinformatics/bti664. Google Scholar [23] J. Reger and K. Schmidt, Modeling and analyzing finite state automata in the finite field $F_2$,, Mathematics and Computers in Simulation, 66 (2004), 193. doi: 10.1016/j.matcom.2003.11.005. Google Scholar [24] N. A. W. Riel, Dynamic modelling and analysis of biochemical networks: mechanism-based models and model-based experiments,, Briefings in Bioinformatics, 7 (2006), 364. doi: 10.1093/bib/bbl040. Google Scholar [25] S. Rudeanu, "Boolean Functions and Equations,", North-Holland, (1974). Google Scholar [26] M. H. Stone, The theory of representation for Boolean algebras,, Transactions of American Mathematical Society, 40 (1936), 37. Google Scholar [27] T. Tamura and T. Akutsu, Algorithms for singleton attractor detection in planar and nonplanar AND/OR Boolean networks,, Math. Comput. Sci., 2 (2009), 401. doi: 10.1007/s11786-008-0063-5. Google Scholar [28] C. J. Tomlin and J. D. Aelrod, Biology by numbers: Mathematical modelling in developmental biology,, Nature Reviews Genetics, 8 (2007), 331. doi: 10.1038/nrg2098. Google Scholar [29] S-Q. Zhang, M. Hayashida, T. Akutsu, W-K. Ching and M. K. Ng, Algorithms for finding small attractors in Boolean networks,, EURASIP Journal on Bioinformatics and Systems Biology (2007)., (2007). doi: 10.1155/2007/20180. Google Scholar
 [1] Roberto Serra, Marco Villani, Alex Graudenzi, Annamaria Colacci, Stuart A. Kauffman. The simulation of gene knock-out in scale-free random Boolean models of genetic networks. Networks & Heterogeneous Media, 2008, 3 (2) : 333-343. doi: 10.3934/nhm.2008.3.333 [2] Martin Gugat, Falk M. Hante, Markus Hirsch-Dick, Günter Leugering. Stationary states in gas networks. Networks & Heterogeneous Media, 2015, 10 (2) : 295-320. doi: 10.3934/nhm.2015.10.295 [3] Yongwu Rong, Chen Zeng, Christina Evans, Hao Chen, Guanyu Wang. Topology and dynamics of boolean networks with strong inhibition. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1565-1575. doi: 10.3934/dcdss.2011.4.1565 [4] Ö. Uğur, G. W. Weber. Optimization and dynamics of gene-environment networks with intervals. Journal of Industrial & Management Optimization, 2007, 3 (2) : 357-379. doi: 10.3934/jimo.2007.3.357 [5] Sujit Nair, Naomi Ehrich Leonard. Stable synchronization of rigid body networks. Networks & Heterogeneous Media, 2007, 2 (4) : 597-626. doi: 10.3934/nhm.2007.2.597 [6] Oskar Weinberger, Peter Ashwin. From coupled networks of systems to networks of states in phase space. Discrete & Continuous Dynamical Systems - B, 2018, 23 (5) : 2021-2041. doi: 10.3934/dcdsb.2018193 [7] Kunwen Wen, Lifang Huang, Qiuying Li, Qi Wang, Jianshe Yu. The mean and noise of FPT modulated by promoter architecture in gene networks. Discrete & Continuous Dynamical Systems - S, 2019, 12 (7) : 2177-2194. doi: 10.3934/dcdss.2019140 [8] J. C. Artés, Jaume Llibre, J. C. Medrado. Nonexistence of limit cycles for a class of structurally stable quadratic vector fields. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 259-270. doi: 10.3934/dcds.2007.17.259 [9] Gershon Wolansky. Limit theorems for optimal mass transportation and applications to networks. Discrete & Continuous Dynamical Systems - A, 2011, 30 (1) : 365-374. doi: 10.3934/dcds.2011.30.365 [10] William Chad Young, Adrian E. Raftery, Ka Yee Yeung. A posterior probability approach for gene regulatory network inference in genetic perturbation data. Mathematical Biosciences & Engineering, 2016, 13 (6) : 1241-1251. doi: 10.3934/mbe.2016041 [11] Joo Sang Lee, Takashi Nishikawa, Adilson E. Motter. Why optimal states recruit fewer reactions in metabolic networks. Discrete & Continuous Dynamical Systems - A, 2012, 32 (8) : 2937-2950. doi: 10.3934/dcds.2012.32.2937 [12] Raoul-Martin Memmesheimer, Marc Timme. Stable and unstable periodic orbits in complex networks of spiking neurons with delays. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1555-1588. doi: 10.3934/dcds.2010.28.1555 [13] Erik Kropat, Silja Meyer-Nieberg, Gerhard-Wilhelm Weber. Computational networks and systems-homogenization of self-adjoint differential operators in variational form on periodic networks and micro-architectured systems. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 139-169. doi: 10.3934/naco.2017010 [14] Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 193-207. doi: 10.3934/naco.2014.4.193 [15] Gabriella Bretti, Maya Briani, Emiliano Cristiani. An easy-to-use algorithm for simulating traffic flow on networks: Numerical experiments. Discrete & Continuous Dynamical Systems - S, 2014, 7 (3) : 379-394. doi: 10.3934/dcdss.2014.7.379 [16] Maya Briani, Emiliano Cristiani. An easy-to-use algorithm for simulating traffic flow on networks: Theoretical study. Networks & Heterogeneous Media, 2014, 9 (3) : 519-552. doi: 10.3934/nhm.2014.9.519 [17] Vivi Rottschäfer. Multi-bump patterns by a normal form approach. Discrete & Continuous Dynamical Systems - B, 2001, 1 (3) : 363-386. doi: 10.3934/dcdsb.2001.1.363 [18] Todor Mitev, Georgi Popov. Gevrey normal form and effective stability of Lagrangian tori. Discrete & Continuous Dynamical Systems - S, 2010, 3 (4) : 643-666. doi: 10.3934/dcdss.2010.3.643 [19] Dario Bambusi, A. Carati, A. Ponno. The nonlinear Schrödinger equation as a resonant normal form. Discrete & Continuous Dynamical Systems - B, 2002, 2 (1) : 109-128. doi: 10.3934/dcdsb.2002.2.109 [20] Serap Ergün, Sirma Zeynep Alparslan Gök, Tuncay Aydoǧan, Gerhard Wilhelm Weber. Performance analysis of a cooperative flow game algorithm in ad hoc networks and a comparison to Dijkstra's algorithm. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1085-1100. doi: 10.3934/jimo.2018086

2018 Impact Factor: 0.545