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.

[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.

[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).

[4]

G. Boole, "The Mathematical Analysis of Logic, Being an Essay Towards a Calculus of Deductive Reasoning,", Macmillan, (1847).

[5]

G. Boole, "An Investigation of the Laws of Thought, on Which are Founded the Mathematical Theories of Logic and Probabilities,", Macmillan, (1960).

[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.

[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.

[8]

O. Colón-Reyes, R. Laubenbacher and B. Pareigis, Boolean monomial dynamical systems,, Annals of Combinatorics, 8 (2004), 425.

[9]

M. I. Davidich and S. Bornholdt, Boolean network model predicts cell cycle sequence of fission yeast,, PLoS ONE, 3 (2008).

[10]

E. Dubrova, M. Teslenko and A. Martinelli, Kauffman networks: Analysis and applications,, Computer-Aided Design, (2005), 479. doi: 10.1109/ICCAD.2005.1560115.

[11]

E. D. Fabricius, "Modern Digital Design and Switching Theory,", CRC Press 1992., (1992).

[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.

[13]

R. A. Hernádez-Toledo, Linear finite dynamical systems,, Communications in Algebra, 33 (2005), 2977. 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.

[16]

A. Jarrah, B. Raposa and R. Laubenbacher, Nested canalyzing, unate cascade, and polynomial functions,, Physica D, 233 (2007), 167.

[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. 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.

[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.

[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.

[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.

[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.

[25]

S. Rudeanu, "Boolean Functions and Equations,", North-Holland, (1974).

[26]

M. H. Stone, The theory of representation for Boolean algebras,, Transactions of American Mathematical Society, 40 (1936), 37.

[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.

[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.

[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.

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.

[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.

[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).

[4]

G. Boole, "The Mathematical Analysis of Logic, Being an Essay Towards a Calculus of Deductive Reasoning,", Macmillan, (1847).

[5]

G. Boole, "An Investigation of the Laws of Thought, on Which are Founded the Mathematical Theories of Logic and Probabilities,", Macmillan, (1960).

[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.

[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.

[8]

O. Colón-Reyes, R. Laubenbacher and B. Pareigis, Boolean monomial dynamical systems,, Annals of Combinatorics, 8 (2004), 425.

[9]

M. I. Davidich and S. Bornholdt, Boolean network model predicts cell cycle sequence of fission yeast,, PLoS ONE, 3 (2008).

[10]

E. Dubrova, M. Teslenko and A. Martinelli, Kauffman networks: Analysis and applications,, Computer-Aided Design, (2005), 479. doi: 10.1109/ICCAD.2005.1560115.

[11]

E. D. Fabricius, "Modern Digital Design and Switching Theory,", CRC Press 1992., (1992).

[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.

[13]

R. A. Hernádez-Toledo, Linear finite dynamical systems,, Communications in Algebra, 33 (2005), 2977. 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.

[16]

A. Jarrah, B. Raposa and R. Laubenbacher, Nested canalyzing, unate cascade, and polynomial functions,, Physica D, 233 (2007), 167.

[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. 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.

[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.

[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.

[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.

[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.

[25]

S. Rudeanu, "Boolean Functions and Equations,", North-Holland, (1974).

[26]

M. H. Stone, The theory of representation for Boolean algebras,, Transactions of American Mathematical Society, 40 (1936), 37.

[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.

[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.

[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.

[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

2017 Impact Factor: 0.561

Metrics

  • PDF downloads (6)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]