Article Contents
Article Contents

# Dynamics of boolean networks

• 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.
Mathematics Subject Classification: Primary: 94C10; Secondary: 05C38.

 Citation:

•  [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-1345doi: 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: 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.