Dynamics of boolean networks

Previous Article
DCDS-S Home
This Issue
Next Article
Turing instability in a coupled predator-prey model with different Holling type functional responses

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

Dynamics of boolean networks

Yi Ming Zou ^1,

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

Received March 2009 Revised October 2009 Published December 2010

Abstract
Related Papers

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.

Keywords: gene regulatory networks, Boolean networks, algorithm., limit cycles, stable states, disjunctive normal form.

Mathematics Subject Classification: Primary: 94C10; Secondary: 05C3.

Citation: Yi Ming Zou. Dynamics of boolean networks. Discrete and 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-18. doi: 10.1016/S0022-5193(03)00035-3.
[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-497. doi: 10.1016/j.matcom.2004.03.003.
[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), On-line ID97356.
[4]	G. Boole, "The Mathematical Analysis of Logic, Being an Essay Towards a Calculus of Deductive Reasoning," Macmillan, Barclay and Macmillan, Cambridge; George Bell, London, 1847. Reprints (1948, 1951), Basil Blackwell, Oxford.
[5]	G. Boole, "An Investigation of the Laws of Thought, on Which are Founded the Mathematical Theories of Logic and Probabilities," Macmillan, Barclay and Macmillan, Cambridge; Walton and Maberly, London, 1854. Reprint (1960), Dover, New York.
[6]	M. Brickenstein and A. Dreyer, PolyBoRi: A framework for Gröbner-basis computations with Boolean polynomials, J. Symbolic Comput., 44 (2009), 1326-1345 doi: 10.1016/j.jsc.2008.02.017.
[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-1635. arXiv:0801.1177.
[8]	O. Colón-Reyes, R. Laubenbacher and B. Pareigis, Boolean monomial dynamical systems, Annals of Combinatorics, 8 (2004), 425-439. arXiv:math/0403166v1.
[9]	M. I. Davidich and S. Bornholdt, Boolean network model predicts cell cycle sequence of fission yeast, PLoS ONE, 3 (2008), e1672.
[10]	E. Dubrova, M. Teslenko and A. Martinelli, Kauffman networks: Analysis and applications, Computer-Aided Design, IEEE/ACM International Conference (2005), 479-484, doi: 10.1109/ICCAD.2005.1560115.
[11]	E. D. Fabricius, "Modern Digital Design and Switching Theory," CRC Press 1992.
[12]	J. F. Groote and M. Keinänen, A sub-quadratic algorithm for conjunctive and disjunctive BESs, Theoretical aspects of computing-ICTAC 2005, 532-545, Lecture Notes in Comput. Sci., 3722, Springer, Berlin 2005.
[13]	R. A. Hernádez-Toledo, Linear finite dynamical systems, Communications in Algebra, 33 (2005), 2977-2989. doi: 10.1081/AGB-200066211.
[14]	A. Ilichinsky, "Cellular Automata: A Discrete Universe," World Scientific Publishing Company, 2001.
[15]	A. Jarrah, R. Laubenbacher, B. Stigler and M. Stillman, Reverse-engineering of polynomial dynamical systems, Adv. in Appl. Math., 39 (2007), 477-489. arXiv:q-bio/0605032v1.
[16]	A. Jarrah, B. Raposa and R. Laubenbacher, Nested canalyzing, unate cascade, and polynomial functions, Physica D, 233 (2007), 167-174. arXiv:q-bio/0606013v3.
[17]	A. Jarrah, R. Laubenbacher and A. Veliz-Cuba, The dynamics of conjunctive and disjunctive Boolean networks,, preprint available at: \arXiv{0805.0275v1}., ().
[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}., ().
[19]	S. Kauffman, C. Peterson, B. Samuelsson and C. Troein, Genetic networks with canalyzing Boolean rules are always stable, PNAS, 101 (2004), 17102-17107. doi: 10.1073/pnas.0407783101.
[20]	R. Laubenbacher and B. Stigler, A computational algebra approach to the reverse engineering of gene regulatory networks, J. Theor. Biol., 229 (2004), 523-537. arXiv:q-bio/0312026.
[21]	T. E. Malloy, J. Butner and G. C. Jensen, The emergence of dynamic form through phase relations in dynamic systems, Nonlinear Dynamics, Psychology, and Life Sciences, 12 (2008), 371-395.
[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-4025. doi: 10.1093/bioinformatics/bti664.
[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-206. doi: 10.1016/j.matcom.2003.11.005.
[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-374. doi: 10.1093/bib/bbl040.
[25]	S. Rudeanu, "Boolean Functions and Equations," North-Holland, Amsterdam, 1974.
[26]	M. H. Stone, The theory of representation for Boolean algebras, Transactions of American Mathematical Society, 40 (1936), 37-111.
[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-420. doi: 10.1007/s11786-008-0063-5.
[28]	C. J. Tomlin and J. D. Aelrod, Biology by numbers: Mathematical modelling in developmental biology, Nature Reviews Genetics, 8 (2007), 331-340. doi: 10.1038/nrg2098.
[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). doi: 10.1155/2007/20180.

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-18. doi: 10.1016/S0022-5193(03)00035-3.
[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-497. doi: 10.1016/j.matcom.2004.03.003.
[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), On-line ID97356.
[4]	G. Boole, "The Mathematical Analysis of Logic, Being an Essay Towards a Calculus of Deductive Reasoning," Macmillan, Barclay and Macmillan, Cambridge; George Bell, London, 1847. Reprints (1948, 1951), Basil Blackwell, Oxford.
[5]	G. Boole, "An Investigation of the Laws of Thought, on Which are Founded the Mathematical Theories of Logic and Probabilities," Macmillan, Barclay and Macmillan, Cambridge; Walton and Maberly, London, 1854. Reprint (1960), Dover, New York.
[6]	M. Brickenstein and A. Dreyer, PolyBoRi: A framework for Gröbner-basis computations with Boolean polynomials, J. Symbolic Comput., 44 (2009), 1326-1345 doi: 10.1016/j.jsc.2008.02.017.
[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-1635. arXiv:0801.1177.
[8]	O. Colón-Reyes, R. Laubenbacher and B. Pareigis, Boolean monomial dynamical systems, Annals of Combinatorics, 8 (2004), 425-439. arXiv:math/0403166v1.
[9]	M. I. Davidich and S. Bornholdt, Boolean network model predicts cell cycle sequence of fission yeast, PLoS ONE, 3 (2008), e1672.
[10]	E. Dubrova, M. Teslenko and A. Martinelli, Kauffman networks: Analysis and applications, Computer-Aided Design, IEEE/ACM International Conference (2005), 479-484, doi: 10.1109/ICCAD.2005.1560115.
[11]	E. D. Fabricius, "Modern Digital Design and Switching Theory," CRC Press 1992.
[12]	J. F. Groote and M. Keinänen, A sub-quadratic algorithm for conjunctive and disjunctive BESs, Theoretical aspects of computing-ICTAC 2005, 532-545, Lecture Notes in Comput. Sci., 3722, Springer, Berlin 2005.
[13]	R. A. Hernádez-Toledo, Linear finite dynamical systems, Communications in Algebra, 33 (2005), 2977-2989. doi: 10.1081/AGB-200066211.
[14]	A. Ilichinsky, "Cellular Automata: A Discrete Universe," World Scientific Publishing Company, 2001.
[15]	A. Jarrah, R. Laubenbacher, B. Stigler and M. Stillman, Reverse-engineering of polynomial dynamical systems, Adv. in Appl. Math., 39 (2007), 477-489. arXiv:q-bio/0605032v1.
[16]	A. Jarrah, B. Raposa and R. Laubenbacher, Nested canalyzing, unate cascade, and polynomial functions, Physica D, 233 (2007), 167-174. arXiv:q-bio/0606013v3.
[17]	A. Jarrah, R. Laubenbacher and A. Veliz-Cuba, The dynamics of conjunctive and disjunctive Boolean networks,, preprint available at: \arXiv{0805.0275v1}., ().
[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}., ().
[19]	S. Kauffman, C. Peterson, B. Samuelsson and C. Troein, Genetic networks with canalyzing Boolean rules are always stable, PNAS, 101 (2004), 17102-17107. doi: 10.1073/pnas.0407783101.
[20]	R. Laubenbacher and B. Stigler, A computational algebra approach to the reverse engineering of gene regulatory networks, J. Theor. Biol., 229 (2004), 523-537. arXiv:q-bio/0312026.
[21]	T. E. Malloy, J. Butner and G. C. Jensen, The emergence of dynamic form through phase relations in dynamic systems, Nonlinear Dynamics, Psychology, and Life Sciences, 12 (2008), 371-395.
[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-4025. doi: 10.1093/bioinformatics/bti664.
[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-206. doi: 10.1016/j.matcom.2003.11.005.
[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-374. doi: 10.1093/bib/bbl040.
[25]	S. Rudeanu, "Boolean Functions and Equations," North-Holland, Amsterdam, 1974.
[26]	M. H. Stone, The theory of representation for Boolean algebras, Transactions of American Mathematical Society, 40 (1936), 37-111.
[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-420. doi: 10.1007/s11786-008-0063-5.
[28]	C. J. Tomlin and J. D. Aelrod, Biology by numbers: Mathematical modelling in developmental biology, Nature Reviews Genetics, 8 (2007), 331-340. doi: 10.1038/nrg2098.
[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). doi: 10.1155/2007/20180.

[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 and 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 and Heterogeneous Media, 2015, 10 (2) : 295-320. doi: 10.3934/nhm.2015.10.295
[3]	Ö. Uğur, G. W. Weber. Optimization and dynamics of gene-environment networks with intervals. Journal of Industrial and Management Optimization, 2007, 3 (2) : 357-379. doi: 10.3934/jimo.2007.3.357
[4]	Erik Kropat, Gerhard-Wilhelm Weber, Erfan Babaee Tirkolaee. Foundations of semialgebraic gene-environment networks. Journal of Dynamics and Games, 2020, 7 (4) : 253-268. doi: 10.3934/jdg.2020018
[5]	Yongwu Rong, Chen Zeng, Christina Evans, Hao Chen, Guanyu Wang. Topology and dynamics of boolean networks with strong inhibition. Discrete and Continuous Dynamical Systems - S, 2011, 4 (6) : 1565-1575. doi: 10.3934/dcdss.2011.4.1565
[6]	Tiantian Mu, Jun-E Feng, Biao Wang. Pinning detectability of Boolean control networks with injection mode. Discrete and Continuous Dynamical Systems - S, 2022 doi: 10.3934/dcdss.2022089
[7]	Sujit Nair, Naomi Ehrich Leonard. Stable synchronization of rigid body networks. Networks and Heterogeneous Media, 2007, 2 (4) : 597-626. doi: 10.3934/nhm.2007.2.597
[8]	Kunwen Wen, Lifang Huang, Qiuying Li, Qi Wang, Jianshe Yu. The mean and noise of FPT modulated by promoter architecture in gene networks. Discrete and Continuous Dynamical Systems - S, 2019, 12 (7) : 2177-2194. doi: 10.3934/dcdss.2019140
[9]	Bernold Fiedler. Global Hopf bifurcation in networks with fast feedback cycles. Discrete and Continuous Dynamical Systems - S, 2021, 14 (1) : 177-203. doi: 10.3934/dcdss.2020344
[10]	Oskar Weinberger, Peter Ashwin. From coupled networks of systems to networks of states in phase space. Discrete and Continuous Dynamical Systems - B, 2018, 23 (5) : 2021-2041. doi: 10.3934/dcdsb.2018193
[11]	Sanmei Zhu, Jun-e Feng, Jianli Zhao. State feedback for set stabilization of Markovian jump Boolean control networks. Discrete and Continuous Dynamical Systems - S, 2021, 14 (4) : 1591-1605. doi: 10.3934/dcdss.2020413
[12]	Yvjing Yang, Yang Liu, Jungang Lou, Zhen Wang. Observability of switched Boolean control networks using algebraic forms. Discrete and Continuous Dynamical Systems - S, 2021, 14 (4) : 1519-1533. doi: 10.3934/dcdss.2020373
[13]	Jiayuan Yan, Ding-Xue Zhang, Bin Hu, Zhi-Hong Guan, Xin-Ming Cheng. State bounding for time-delay impulsive and switching genetic regulatory networks with exogenous disturbance. Discrete and Continuous Dynamical Systems - S, 2022, 15 (7) : 1749-1765. doi: 10.3934/dcdss.2022004
[14]	J. C. Artés, Jaume Llibre, J. C. Medrado. Nonexistence of limit cycles for a class of structurally stable quadratic vector fields. Discrete and Continuous Dynamical Systems, 2007, 17 (2) : 259-270. doi: 10.3934/dcds.2007.17.259
[15]	Gershon Wolansky. Limit theorems for optimal mass transportation and applications to networks. Discrete and Continuous Dynamical Systems, 2011, 30 (1) : 365-374. doi: 10.3934/dcds.2011.30.365
[16]	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
[17]	Joo Sang Lee, Takashi Nishikawa, Adilson E. Motter. Why optimal states recruit fewer reactions in metabolic networks. Discrete and Continuous Dynamical Systems, 2012, 32 (8) : 2937-2950. doi: 10.3934/dcds.2012.32.2937
[18]	Raoul-Martin Memmesheimer, Marc Timme. Stable and unstable periodic orbits in complex networks of spiking neurons with delays. Discrete and Continuous Dynamical Systems, 2010, 28 (4) : 1555-1588. doi: 10.3934/dcds.2010.28.1555
[19]	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 and Optimization, 2017, 7 (2) : 139-169. doi: 10.3934/naco.2017010
[20]	Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control and Optimization, 2014, 4 (3) : 193-207. doi: 10.3934/naco.2014.4.193

2020 Impact Factor: 2.425

Tools

Metrics

Other articles
by authors

on AIMS
Yi Ming Zou
on Google Scholar
Yi Ming Zou

[Back to Top]