Abstract
Boolean networks (BNs) have been extensively used as mathematical models of genetic regulatory networks. The number of fixed points of a BN is a key feature of its dynamical behavior. Here, we study the maximum number of fixed points in a particular class of BNs called regulatory Boolean networks, where each interaction between the elements of the network is either an activation or an inhibition. We find relationships between the positive and negative cycles of the interaction graph and the number of fixed points of the network. As our main result, we exhibit an upper bound for the number of fixed points in terms of minimum cardinality of a set of vertices meeting all positive cycles of the network, which can be applied in the design of genetic regulatory networks.
Similar content being viewed by others
References
Anthony, M., 1987. Discrete Mathematics of Neural Networks: Selected Topics. Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics.
Akutsu, T., Kuhara, S., Maruyama, O., Miyano, S., 1998. A system for identifying Genetic Networks from gene expression patterns produced by gene disruptions and overexpressions. Genome Inform. 9, 151–60.
Aracena, J., 2001. Modelos matemáticos discretos asociados a los sistemas biológicos. Aplicación a las redes de regulación génica. PhD thesis, U. Chile & UJF, Santiago, Chile, & Grenoble, France.
Aracena, J., González, M., Zúñiga, A., Méndez, M., Cambiazo, V., 2006. Regulatory network for cell shape changes during Drosophila ventral furrow formation. J. Theor. Biol. 239, 49–2.
Bagley, R.J., Glass, L., 1996. Counting and classifying attractors in high dimensional dynamical systems. J. Theor. Biol. 183, 269–84.
Cartwright, D., Harary, H., 1956. Structural balance: a generalization of Heider’s theory. Psychol. Rev. 63, 277–93.
Cinquin, O., Demongeot, J., 2002. Positive and negative feedback: striking a balance between necessary antagonists. J. Theor. Biol. 216, 229–41.
Demongeot, J., Kaufmann, M., Thomas, R., 2000. Positive regulatory circuits and memory. C. R. Acad. Sci. 323, 69–0.
Glass, L., Kauffman, S.A., 1973. The logical analysis of continuous, non-linear biochemical control networks. J. Theor. Biol. 39, 103–29.
Harary, F., Norman, R., Cartwright, D., 1965. Structural models: An Introduction to the Theory of Directed Graphs. Wiley, New York.
Harris, S., Sawhill, B., Wuensche, A., Kauffman, S.A., 2002. A model of transcriptional regulatory networks based on biases in the observed regulation rules. Complexity 7, 23–0.
Huang, S., 1999. Gene expression profiling, genetic networks and cellular states: an integrating concept for tumorigenesis and drug discovery. J. Mol. Med. 77, 469–80.
Irons, D.J., 2006. Improving the efficiency of attractor cycle identification in Boolean networks. Physica D 217, 7–1.
Kauffman, S.A., 1969. Metabolic stability and epigenesis in randomly constructed genetics nets. J. Theor. Biol. 22, 437–67.
Kauffman, S.A., 1993. The Origins of Order, Self-Organization and Selection in Evolution. Oxford University Press, London.
Kauffman, S.A., Peterson, C., Samuelsson, B., Troein, C., 2003. Random boolean network models and the yeast transcriptional network. Proc. Natl. Acad. Sci. 100, 14796–4799.
Mochizuki, A., 2005. An analytical study of the number of steady states in gene regulatory networks. J. Theor. Biol. 236, 291–10.
Mendoza, L., Alvarez-Buylla, E., 1998. Dynamics of the genetic regulatory network for Arabidopsis Thaliana flower morphogenesis. J. Theor. Biol. 193, 307–19.
Milano, M., Roli, A., 2000. Solving the safistiablity problem through Boolean networks. In: Lecture Notes in Artificial Intelligence, vol. 1792, pp. 72–3.
Montalva, M., Aracena, J., Gajardo, A., 2008. On the complexity of feedback set problems in signed digraphs. ENDM 30, 249–54.
Nikolajewa, S., Friedel, M., Wilhelm, T., 2007. Boolean networks with biologically relevant rules show ordered behavior. BioSystems 90, 40–7.
Pal, R., Ivanov, I., Datta, A., Bittner, M., Dougherty, E., 2005. Generating Boolean networks with a prescribed attractor structure. Bioinformatics 21, 4021–025.
Samuelsson, B., Troein, C., 2003. Superpolynomial growth in the number of attractors in Kauffman networks. Phys. Rev. Lett. 90, 098701.
Sánchez, L., Thieffry, D., 2001. A logical analysis of the Drosophila Gap-gene system. J. Theor. Biol. 211, 115–41.
Szallasi, Z., Liang, S., 1998. Modeling the normal and neoplastic cell cycle with realistic boolean genetic networks: their application for understanding carcinogenesis and assessing therapeutic strategies. Proc. Pac. Symp. Biocomput. 3, 66–6.
Thomas, R., 1994. The role of feedback circuits: positive feedback circuits are a necessary condition for positive real eigenvalues of the Jacobian matrix. Ber. Bunsenges. Phys. Chem. 98, 1148–151.
Thomas, R., Richelle, J., 1988. Positive feedback loops and multistationarity. Discrete Appl. Math. 19, 381–96.
West, D., 1996. Introduction to Graph Theory. Prentice Hall, New York.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Aracena, J. Maximum Number of Fixed Points in Regulatory Boolean Networks. Bull. Math. Biol. 70, 1398–1409 (2008). https://doi.org/10.1007/s11538-008-9304-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11538-008-9304-7