Abstract
Analyzing all the deterministic dynamics of a Boolean regulatory network is a difficult problem since it grows exponentially with the number of nodes. In this paper, we present mathematical and computational tools for analyzing the complete deterministic dynamics of Boolean regulatory networks. For this, the notion of alliance is introduced, which is a subconfiguration of states that remains fixed regardless of the values of the other nodes. Also, equivalent classes are considered, which are sets of updating schedules which have the same dynamics. Using these techniques, we analyze two yeast cell cycle models. Results show the effectiveness of the proposed tools for analyzing update robustness as well as the discovery of new information related to the attractors of the yeast cell cycle models considering all the possible deterministic dynamics, which previously have only been studied considering the parallel updating scheme.
Similar content being viewed by others
References
Aracena, J., Goles, E., Moreira, A., & Salinas, L. (2009). On the robustness of update schedules in Boolean networks. Biosystems, 97, 1–8.
Aracena, J., Demongeot, J., Fanchon, E., & Montalva, M. (submitted). On the number of different dynamics in Boolean networks with deterministic update schedules. Preprint, Universidad de Concepción, Chile.
Davidich, M. I., & Bornholdt, S. (2008). Boolean network model predicts cell cycle sequence of fission yeast. PLoS ONE, 3(2), e1672.
Demongeot, J., Elena, A., & Sené, S. (2008). Robustness in regulatory networks: a multi-disciplinary approach. Acta Biotheor., 56(1–2), 27–49.
Demongeot, J., Amor, H. B., Elena, A., Gillois, P., Noual, M., & Sené, S. (2009). Robustness in regulatory interaction networks. A generic approach with applications at different levels: physiologic, metabolic and genetic. Int. J. Mol. Sci., 10, 4437–4473.
Elena, A. (2009). Robustesse des réseaux d’automates booléens à seuil aux modes ditération. Application à la modélisation des réseaux de régulation génétique. PhD thesis Université Joseph Fourier, Grenoble, France.
Fauré, A., Naldi, A., Chaouiya, C., & Thieffry, D. (2006). Dynamical analysis of a generic Boolean model for the control of the mammalian cell cycle. Bioinformatics, 22, e124–e131.
Gershenson, C. (2004). Updating schemes in random boolean networks: do they really matter? In J. Pollack, M. Bedau, P. Husbands, T. Ikegami, & R. A. Watson (Eds.), Proceedings of the ninth international conference on the simulation and synthesis of living systems (ALife IX), Boston, USA (pp. 238–243). Cambridge: MIT Press.
Goles, E., & Salinas, L. (2008). Comparison between parallel and serial dynamics of Boolean networks. Theor. Comput. Sci., 396, 247–253.
Goles, E., & Noual, M. (2012). Disjunctive networks and update schedules. Adv. Appl. Math., 48, 646–662.
Greil, F., Drossel, B., & Sattler, J. (2007). Critical Kauffman networks under deterministic asynchronous update. New J. Phys., 9, 373.
Irons, D. J. (2009). Logical analysis of the budding yeast cell cycle. J. Theor. Biol., 257, 543–559.
Kauffman, S. A. (1969). Metabolic stability and epigenesis in randomly constructed genetic nets. J. Theor. Biol., 22, 437–467.
Li, F., Long, T., Lu, Y., Ouyang, Q., & Tang, C. (2004). The yeast cell-cycle network is robustly designed. Proc. Natl. Acad. Sci. USA, 101, 4781–4786.
Mangla, K., Dill, D. L., & Horowitz, M. A. (2010). Timing robustness in the budding and fission yeast cell cycles. PLoS ONE, 5(2), e8906.
Mendoza, L., & Alvarez-Buylla, E. (1998). Dynamics of the genetic regulatory network for Arabidopsis thaliana flower morphogenesis. J. Theor. Biol., 193, 307–319.
Montalva, M. (2011). Feedback set problems and dynamical behavior in regulatory networks. PhD thesis Universidad de Concepción, Concepción, Chile.
Mortveit, H. S., & Reidys, C. (2004). Reduction of discrete dynamical systems over graphs. Adv. Complex Syst., 7, 1–20.
Novak, B., & Tayson, J. J. (2004). A model for restriction point control of the mammalian cell cycle. J. Theor. Biol., 230, 563–579.
Richard, A., Rossignol, G., Comet, J.-P., Bernot, G., Guespin-Michel, J., & Merieau, A. (2012). Boolean models of biosurfactants production in pseudomonas fluorescens. PLoS ONE, 7(1), e24651. doi:10.1371/journal.pone.0024651.
Robert, F. (1986). Discrete iterations. Berlin: Springer.
Ruz, G. A., & Goles, E. (in press). Learning gene regulatory networks using the bees algorithm. Neural Computing and Applications.
Ruz, G. A., & Goles, E. (2012). Reconstruction and update robustness of the mammalian cell cycle network. In Proceedings of IEEE symposium on computational intelligence in bioinformatics and computational biology (CIBCB 2012), San Diego, CA, USA, 9–12 May 2012 (pp. 397–403).
Serra, R., Villani, M., Barbieri, A., Kauffman, S. A., & Colacci, A. (2010). On the dynamics of random Boolean networks subject to noise: attractors, ergodic sets and cell types. J. Theor. Biol., 265, 185–193.
Acknowledgements
The authors would like to thank Conicyt-Chile under grant Fondecyt 1100003 (E.G.), Fondecyt 11110088 (G.A.R.), Fondecyt 3130466 (M.M.), Basal (Conicyt)-CMM (E.G. M.M.), and ANILLO ACT-88 (E.G., M.M., G.A.R.) for financially supporting this research. E. Goles would like to thank TIM3, CNRS, Sophia-Antipolis, France, where part of this work was conducted.
Author information
Authors and Affiliations
Corresponding author
Appendices
Appendix A: The Equivalence Classes Tools
Let G be a digraph and s an update schedule over V(G). Consider the label function lab s defined by
The pair (G,lab s ) is called update digraph (see Figs. 16, 5, and 6 as examples). In (Aracena et al. 2009) was defined equivalence classes [s] G of deterministic update schedules yielding the same update digraph, i.e.,
It was proven that two update schedules in the same class (i.e., two update schedules having the same update digraph) yield exactly the same dynamical behavior. The above implies that the number of equivalence classes of the interaction digraph in a network gives us the maximum number of possible different dynamics that can exist. From this arises the interest in developing enumeration algorithms for these classes. In this context, the following enumeration algorithm was developed in Aracena et al. (submitted) (see Algorithms 1, 2 and 3).
Notation and definitions:
-
A partial update schedule is an update schedule over the vertices of some G′⊆G. A block of s is the set B i ={v∈V(G′): s(v)=i}, 1≤i≤m. The number of blocks of s is denoted by nb(s) and s is denoted by s=(j∈B 1)(j∈B 2)⋯(j∈B nb(s)).
-
For \(X\subseteq V(G)\setminus\bigcup _{i=1}^{nb(s)}B_{i}\), the operation ∗ is defined as follows:
$$s*X=(j\in B_1)(j\in B_2)\cdots(j\in B_{nb(s)})(j\in X) $$where, ∅X=(j∈X).
-
For G=(V,A) a digraph and C,D⊆V we have that G (C,D)=(C∪D,A(G)∩((C∪D)×(C∪D))) and \(\mathit{lab}_{(C,D)}:A(G_{(C,D)})\longrightarrow\{\text {\textcircled {\scriptsize +}},\text {\textcircled {\scriptsize -}}\}\) is defined by
$$\mathit{lab}_{(C,D)}(u,v)= \begin{cases} \text {\textcircled {\scriptsize -}}, & u\in C\wedge v\in D,\\ \text {\textcircled {\scriptsize +}}, &\text{otherwise} \end{cases} $$
For more details, see (Aracena et al. submitted).
Appendix B: Example Using Alliances and the Equivalence Class Tools
Figure 15(a) is an example of a Boolean network that has 3 nodes with threshold Boolean functions. The idea is to illustrate how the notion of alliance and the mathematical tools for the enumeration of equivalence classes, in a given digraph, can be useful for knowing the type of attractors of the network as well as the different dynamics that can be obtained when it is updated in every deterministic way.
We begin by noting that x 3=H(−x 1+2)=1 is an alliance because −x 1+2≥1, regardless the value of x 1 and the update schedule used. Moreover, any of the 23=8 possible configurations will converge to another configuration such that necessarily x 3=1 (see Fig. 16). In particular, those belonging to some attractor (fixed point or limit cycle). Thus, to know all the possible attractors for this network it is sufficient to analyze the dynamics of the reduced network shown in Fig. 15(b).
Thus, the reduced network in Fig. 15(b) has T 2=3 update schedules, each one defining a different update digraph (update schedules and update digraphs are shown in Fig. 16(a), (b) and (c)). Moreover, these 3 update schedules generate 3 different dynamics: \(D^{al}_{1}\), \(D^{al}_{2}\), and \(D^{al}_{3}\) which are specified in dashed triangles inside of the 5 different dynamics associated with the original network: D 1,…,D 5. These are obtained in a similar way than the reduced network mentioned above (see Fig. 16).
Rights and permissions
About this article
Cite this article
Goles, E., Montalva, M. & Ruz, G.A. Deconstruction and Dynamical Robustness of Regulatory Networks: Application to the Yeast Cell Cycle Networks. Bull Math Biol 75, 939–966 (2013). https://doi.org/10.1007/s11538-012-9794-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11538-012-9794-1