Skip to main content
Log in

Deconstruction and Dynamical Robustness of Regulatory Networks: Application to the Yeast Cell Cycle Networks

  • Original Article
  • Published:
Bulletin of Mathematical Biology Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14

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.

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Demongeot, J., Elena, A., & Sené, S. (2008). Robustness in regulatory networks: a multi-disciplinary approach. Acta Biotheor., 56(1–2), 27–49.

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Google Scholar 

  • Goles, E., & Salinas, L. (2008). Comparison between parallel and serial dynamics of Boolean networks. Theor. Comput. Sci., 396, 247–253.

    Article  MathSciNet  MATH  Google Scholar 

  • Goles, E., & Noual, M. (2012). Disjunctive networks and update schedules. Adv. Appl. Math., 48, 646–662.

    Article  MathSciNet  MATH  Google Scholar 

  • Greil, F., Drossel, B., & Sattler, J. (2007). Critical Kauffman networks under deterministic asynchronous update. New J. Phys., 9, 373.

    Article  Google Scholar 

  • Irons, D. J. (2009). Logical analysis of the budding yeast cell cycle. J. Theor. Biol., 257, 543–559.

    Article  MathSciNet  Google Scholar 

  • Kauffman, S. A. (1969). Metabolic stability and epigenesis in randomly constructed genetic nets. J. Theor. Biol., 22, 437–467.

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  • Mangla, K., Dill, D. L., & Horowitz, M. A. (2010). Timing robustness in the budding and fission yeast cell cycles. PLoS ONE, 5(2), e8906.

    Article  Google Scholar 

  • Mendoza, L., & Alvarez-Buylla, E. (1998). Dynamics of the genetic regulatory network for Arabidopsis thaliana flower morphogenesis. J. Theor. Biol., 193, 307–319.

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • Novak, B., & Tayson, J. J. (2004). A model for restriction point control of the mammalian cell cycle. J. Theor. Biol., 230, 563–579.

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Robert, F. (1986). Discrete iterations. Berlin: Springer.

    Book  MATH  Google Scholar 

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

    Chapter  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

Download references

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

Authors

Corresponding author

Correspondence to Gonzalo A. Ruz.

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

$$\forall(j,i)\in A(G),\quad \mathit{lab}_s(j,i)= \begin{cases} \text {\textcircled {\scriptsize +}}&\text{if } s(j)\geq s(i),\\ \text {\textcircled {\scriptsize -}}&\text{if } s(j)< s(i). \end{cases} $$

The pair (G,lab s ) is called update digraph (see Figs. 165, 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.,

$$[s]_{G}=\{s' \text{ update schedule: } (G,\mathit{lab}_s)=(G,\mathit{lab}_{s'})\} $$

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

Algorithm 1
figure 15

EqClass(G)

Algorithm 2
figure 16

DigraphUD(s,A,B)

Algorithm 3
figure 17

MoveTest(C,D)

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 ={vV(G′): s(v)=i}, 1≤im. The number of blocks of s is denoted by nb(s) and s is denoted by s=(jB 1)(jB 2)⋯(jB 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=(jX).

  • For G=(V,A) a digraph and C,DV we have that G (C,D)=(CD,A(G)∩((CD)×(CD))) 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.

Fig. 15
figure 18

(a) A BN of 3 nodes with threshold Boolean functions defined as x 1, x 2, x 3, and thresholds θ=0, θ=1, and θ=−2, respectively. Dotted lines represent negative interactions (weight=−1) while the others are positive interactions (weight=1). (b) The BN of (a) is reduced after considering the alliance x 3=1. Note that the effect of x 3=1 over x 2 is equivalent to write x 2=H(x 1x 2) while x 1 remains the same

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

Fig. 16
figure 19

In (a), (b) and (c) are specified the update schedules, its associated update digraphs and its dynamics (shown in dashed triangles and denoted by \(D^{al}_{1}\), \(D^{al}_{2}\) and \(D^{al}_{3}\) respectively) inside of the different dynamics of the original network: D 1,…,D 5

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

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11538-012-9794-1

Keywords

Navigation