PMCCPMCCPMCC

Search tips
Search criteria 

Advanced

 
Logo of plosonePLoS OneView this ArticleSubmit to PLoSGet E-mail AlertsContact UsPublic Library of Science (PLoS)
 
PLoS One. 2013; 8(7): e69626.
Published online 2013 July 26. doi:  10.1371/journal.pone.0069626
PMCID: PMC3724945

Majority Rules with Random Tie-Breaking in Boolean Gene Regulatory Networks

Jesus Gomez-Gardenes, Editor

Abstract

We consider threshold Boolean gene regulatory networks, where the update function of each gene is described as a majority rule evaluated among the regulators of that gene: it is turned ON when the sum of its regulator contributions is positive (activators contribute positively whereas repressors contribute negatively) and turned OFF when this sum is negative. In case of a tie (when contributions cancel each other out), it is often assumed that the gene keeps it current state. This framework has been successfully used to model cell cycle control in yeast. Moreover, several studies consider stochastic extensions to assess the robustness of such a model.

Here, we introduce a novel, natural stochastic extension of the majority rule. It consists in randomly choosing the next value of a gene only in case of a tie. Hence, the resulting model includes deterministic and probabilistic updates. We present variants of the majority rule, including alternate treatments of the tie situation. Impact of these variants on the corresponding dynamical behaviours is discussed. After a thorough study of a class of two-node networks, we illustrate the interest of our stochastic extension using a published cell cycle model. In particular, we demonstrate that steady state analysis can be rigorously performed and can lead to effective predictions; these relate for example to the identification of interactions whose addition would ensure that a specific state is absorbing.

Introduction

Cellular processes are driven by large and heterogeneous interaction networks that are being uncovered thanks to tremendous technological advances. In this context, a range of modelling frameworks has been deployed to represent and analyse biological networks, aiming at better understanding these complex systems [1], [2]. Among these frameworks, Boolean Genetic Regulatory Networks (GRN) introduced more than forty years ago provide a convenient qualitative formalism [3], [4], which has since been the subject of numerous theoretical studies and extensions [5], [6]. Boolean GRNs, including their generalisation to account for multi-valued variables [7], have proved useful for modelling and analysing regulatory and signalling networks for which precise quantitative data are often scarce (see e.g. [8][13] for this framework applied to cell cycle modelling).

Briefly, a Boolean GRN is defined by a signed, directed graph, where the nodes represent genes (or more generally regulatory components) and signed edges represent the regulatory interactions between these components: positive (resp. negative) edges denote activations (resp. inhibitions). Each node is associated with a Boolean variable that accounts for the expression state (ON/OFF) of the corresponding gene, and a logical function specifies the evolution of this variable, depending on the variables associated with the regulators of the gene. More precisely, at each time step, gene values are updated according to the results returned by their logical functions. There is a variety of Boolean GRN models that differ in their classes of logical functions (e.g. additive, canalizing, unrestricted), in their structural properties (e.g. fixed, bounded or unrestricted indegrees), or in their updating scheme (e.g. synchronous, asynchronous, block-sequential).

To define a model, in addition to the already challenging problem of identifying the wiring of the (signed) regulatory network, one has to specify the logical functions associated to the nodes. That is to say to specify how regulatory effects are combined. In this context, some authors choose to rely on functions uniquely defined from the regulatory structure [8], [10], [14]. In particular, in Boolean threshold networks, regulatory effects are assumed to be additive: each function is defined as a majority rule where the decision to activate a gene follows from the comparison of the sum of the (possibly weighted) contributions from the regulators to a specific threshold. Boolean threshold networks have been successfully used to model the control of cell cycle [8], [10]. Zañudo et al. have performed a thorough study of random Boolean threshold networks defined as a subset of the ensemble of Kauffman's random Boolean networks, where regulators and regulatory functions are randomly chosen [15]. Finally, it is worth noting that Boolean threshold networks originate from the McCulloch-Pitts neural model [16], which gave rise to countless studies and applications.

To account for the inherent stochasticity of regulation processes, stochastic versions of Boolean GRNs have been proposed in the literature [17][22]. Schlumevitch and colleagues define Probabilistic Boolean Networks, where a set of regulatory functions is assigned to each gene and, at each time step, one function is randomly chosen within this set [17]. This setting results in dynamics that can be represented as a Markov chain. Other authors propose to update each gene according to its regulatory function with a given probability [18][21]. Garg et al. discuss this model they call Stochasticity In Nodes (SIN), indicating that it can lead to noise overrepresentation. They propose an alternate model, called Stochasticity In Functions (SIF), that differently accounts for the stochasticity of the function failure: it associates different failure probability to different logical gates and stochasticity also depends on the state of the regulators [22]. We finally refer to [23] for a seminal discussion of the complete probabilistic version of such models in the context of neural networks.

Here, focussing on threshold Boolean networks, we propose that the majority rule is particularly suitable to combine deterministic and probabilistic updates. Indeed, the combined contribution of the regulators at a given time is not always conclusive to enable an unambiguous choice of the gene evolution. Hence, we propose a stochastic tie-breaking that associates a probability to the update value when positive effects countervail negative effects. Furthermore, various majority rule settings can be devised that are specified and discussed in this paper. We extensively study a class of two gene networks, considering different majority rule settings. We show that this simple motif gives rise to a wide variety of behaviours and that the regulatory structure plays a role in the degree of stochasticity exhibited by the dynamics. We further revisit the Li et al.'s deterministic Boolean threshold model of the budding yeast cell cycle [8]. Interestingly, several studies have considered stochastic versions of this model, with intent to explore the model robustness (e.g. [18], [24], [25]). Here, we illustrate the interest of our approach to tackle this question. In particular, we demonstrate that steady state analysis can be rigorously performed and lead to effective predictions; these relate to the identification of interactions whose addition would ensure that a specific state is an absorbing state.

Methods

Boolean Gene Regulatory Networks (GRN) are defined by a directed graph where the nodes represent the regulatory components (genes or their products) and the edges represent the regulatory interactions. We denote the nodes An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e001.jpg (An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e002.jpg, the number of nodes). Each node is associated with a level of expression (or of activity) referred to as An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e003.jpg for simplicity. This level may change in time, taking the value An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e004.jpg (ON) or An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e005.jpg (OFF). An edge from An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e006.jpg to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e007.jpg is denoted An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e008.jpg and is associated with a sign An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e009.jpg, which is positive for an activation An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e010.jpg or negative for a repression An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e011.jpg. The source of the edge An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e012.jpg is thus a regulator of gene An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e013.jpg. If An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e014.jpg does not regulate An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e015.jpg then An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e016.jpg.

The dynamics takes place in the configuration space An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e017.jpg (An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e018.jpg) and configuration An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e019.jpg is defined by the values of the An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e020.jpg nodes: An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e021.jpg.

The evolution of each node is defined by an updating rule, which depends on the regulators of that node and the time variable is discrete: An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e022.jpg. Note that there is an edge from An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e023.jpg to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e024.jpg if, for some fixed values of the other regulators of An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e025.jpg, changing the value of An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e026.jpg has an effect on the value of An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e027.jpg at the next time step: such regulatory interactions are said functional (e.g. [26]).

We first introduce the Majority Rule (MR) that, given the configuration of the system at time An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e028.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e029.jpg, defines the configuration at the next time An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e030.jpg:

equation image
(1)

Hence, in Equation 1, an activator (resp. a repressor) has a positive contribution if it is present (resp. absent). When the sum of the contributions is zero (i.e. there are as many positive and negative contributions), rather to arbitrarily opt for a value, the MR sets An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e032.jpg with probability An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e033.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e034.jpg with probability An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e035.jpg. A node is deterministic if its updating rule is deterministic for any configuration, and probabilistic if its updating rule is probabilistic for some configurations. Therefore, in the case of the MR, a node is deterministic if it has an odd in-degree (i.e. an odd number of regulators) and probabilistic if it has an even in-degree.

If there is at least one probabilistic node, the dynamics of the model can be represented by a finite Markov chain on the configuration space An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e036.jpg; otherwise, we have a deterministic dynamical system in An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e037.jpg. Extending the usual notion of absorbing chains [27], we say that the chain is absorbing if all ergodic sets are deterministic: either fixed points (i.e. configurations such that An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e038.jpg with probability one) or cycles (i.e. sets of configurations such that there exists a An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e039.jpg for which An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e040.jpg with probability one). Hence, with this definition, the set of absorbing states includes states that are members of deterministic cycles. It corresponds to the usual definition applied to a power of the transition matrix. Moreover, we will often refer to the terminology of the dynamical systems community by calling attractors the (minimal) ergodic sets of a chain, that are also defined as the terminal strongly connected components of the transition diagram.

For completeness, we also investigate two variants of the MR. The first variant, referred to as Inertial Majority Rule (IMR), considers the current state of a probabilistic node to define its next value in the case of equal number of positive and negative contributions:

equation image
(2)

We designate this rule inertial because its deterministic version (when An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e042.jpg) specifies that nodes keep their current values when activations and repressions cancel each other out. It is worth noting that this rule amounts to adding a functional self-activation on each node: when the sum of the contributions from all other regulators is zero, it is the value of the proper node that determines its next level.

In the next MR variant, referred to as Null Majority Rule (NMR), the nodes take values An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e043.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e044.jpg. Hence the configuration space is An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e045.jpg and we denote An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e046.jpg the level of the An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e047.jpgth node, to distinguish from An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e048.jpg, which takes values An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e049.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e050.jpg:

equation image
(3)

Hence, under the NMR, when the level of a regulator is zero, it plays no role in the regulatory function. As a consequence, whatever the sign of the interaction (activation or inhibition), the absence of a regulator results to the same (lack of) contribution in contrast to the MR, where e.g. the absence of a repressor has a positive contribution. Importantly, whatever their in-degree, all nodes are probabilistic.

These two variants of the majority rule can be combined in an Inertial Null Majority Rule (INMR) as in the model of the cell cycle control in yeast specified by Li et al. [8] (see below, the section devoted to the yeast cell cycle model).

Because the evolution of any node only depends on its regulators, it will be convenient to focus on structures that we call modules, which are composed by one node An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e052.jpg and its incoming interactions.

Finally, it is worth noting that the majority rules defined above are special cases of the regulatory functions considered in threshold Boolean networks, where the sums of contributions include interaction weights An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e053.jpg (An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e054.jpg) and compare to activation thresholds An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e055.jpg [15]. Here, all interaction weights are set to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e056.jpg, and all thresholds are zero.

Results

Two-node Gene Regulatory Networks

Here, we consider connected Gene Regulatory Networks (GRNs) encompassing two nodes An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e057.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e058.jpg. There are three classes of such two-node GRNs that include respectively two, three and four interactions. The first class contains three elementary cross-regulatory circuits; two circuits are positive circuits (i.e. the product of the interaction signs is positive) and one circuit is negative with a node activating its repressor. There are indeed two such circuits which are equivalent up to exchanging node labels: An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e059.jpg activates An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e060.jpg, which inhibits An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e061.jpg or An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e062.jpg inhibits An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e063.jpg, which activates An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e064.jpg. In these models, both nodes are deterministic under the Majority Rule (MR). The second class encompasses the networks made by cross-interactions and a single self-interaction (six such networks, up to exchanging node labels). Under the MR, the self-regulated node is probabilistic, whereas the other node is deterministic. These models give rise to: 1) bi-stable dynamics (when both circuits are positive), 2) an absorbing period-2 cycle (when the cross-regulatory circuit is positive and the self-regulation is negative) and 3) combination of cycles over the four configurations (when the cross-regulatory circuit is negative).

We choose to thoroughly study the third class, for which both nodes are probabilistic. We thus consider all the GRNs defined by cross-interactions between nodes An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e065.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e066.jpg, which are both self-regulated (for convenience, we use free variables An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e067.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e068.jpg such that An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e069.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e070.jpg). We start by considering the MR. Then, we point out the differences with the inertial and null MR variants (IMR and NMR).

We denote by An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e071.jpg the module where An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e072.jpg is self-regulated (with sign An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e073.jpg) and is regulated by the node An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e074.jpg (with sign An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e075.jpg); there are four modules of this type. We are thus interested in the networks that result from the composition (denoted An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e076.jpg) of two such modules.

In what follows, the Markov transition matrices An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e077.jpg are An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e078.jpg matrices with entries corresponding to configurations An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e079.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e080.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e081.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e082.jpg (in this order, which facilitates the description of the rotation that transforms one model into another, see below).

Figure 1 summarises the dynamical rules for the four modules, considering the MR as defined by Equation 1. There are 16 models corresponding to the different combinations of two modules. Notice that a row rotation (modulo 4, from top to bottom) transforms each module (column) into the next one. Denoting by An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e083.jpg this transformation and arbitrarily denoting by An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e084.jpg the An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e085.jpg module, we refer to the remaining modules as indicated in Figure 1: An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e086.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e087.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e088.jpg (An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e089.jpg).

Figure 1
The four modules and their evolutions for the majority rule (MR).

We first observe a node symmetry that relates An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e096.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e097.jpg by exchanging An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e098.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e099.jpg. Referring to the relation between the two modules that define a two-node GRN, we partition the set of the models An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e100.jpg in two subsets: eight models are said in phase (IP), when An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e101.jpg, that is when the probabilistic choices are located in the same row in Figure 1; the remaining eight models are out of phase (OP), when An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e102.jpg. In the former case (IP), the Markov matrix has two rows with four probabilistic entries each combining the two parameters (An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e103.jpg) and two rows with a deterministic entry (i.e. with probability one). This defines 10 transitions in the corresponding dynamical diagrams. Whereas in the later case (OP), each row has two probabilistic entries (either An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e104.jpg or An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e105.jpg), giving rise to eight transitions in the dynamical diagrams.

We search for other symmetries to reduce the case studies of our two-node models. From a mathematical standpoint, which does not always fit the functional perspective, two models are equivalent when their Markov matrices are the same up to a renaming of the state space and a bijective correspondence of the parameters An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e106.jpg. Clearly, a necessary condition for this equivalence is that the diagonal elements of the matrices are the same up to parameter exchanges. In particular, an IP model cannot be isomorphic to an OP model. By inspection of the diagonal entries of each model and elementary computations, we end up with a complete classification of all the models.

There are eight IP models grouped into three isomorphic classes, IP1, IP2 and IP3. They are characterised by the existence of two deterministic transitions whose specific locations govern the dynamics of the model. There are also eight OP models grouped into three isomorphic classes, OP1, OP2 and OP3. Contrary to the IP models, all the transitions are probabilistic and depend on only one of the parameters (An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e107.jpg or An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e108.jpg), allowing a complete flexibility of the mean visit times associated to each connected component of the dynamical graph.

Model class IP1

It includes the two models An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e109.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e110.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e111.jpg (i.e. An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e112.jpg) and 0An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e113.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e114.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e115.jpg (i.e. An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e116.jpg). From the structural symmetry point of view, this class contains the models with self-activations and symmetrical cross-interactions (i.e. positive two-node circuits). The transition matrix of An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e117.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e118.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e119.jpg is:

equation image
(4)

The model An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e121.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e122.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e123.jpg together with its dynamics depending on the values of the parameters An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e124.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e125.jpg are depicted in Figure 2. The transition matrix of 0An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e126.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e127.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e128.jpg can be deduced from the matrix of An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e129.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e130.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e131.jpg by permuting the entries An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e132.jpg and changing An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e133.jpg to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e134.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e135.jpg to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e136.jpg:

equation image
(5)
Figure 2
The dynamics of the IP1 model An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e147.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e148.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e149.jpg.

Therefore the dynamics of An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e138.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e139.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e140.jpg is isomorphic to that of 0An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e141.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e142.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e143.jpg. These models are self-symmetric by node symmetry. The two deterministic transitions (i.e. with probability one) are loops on single states (i.e. diagonal elements in the transition matrix). In other words, the corresponding Markov chains are absorbing with two fixed point attractors. The fundamental matrix is [27]:

equation image
(6)

where the first entry is for An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e145.jpg and the second for An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e146.jpg.

Recall that the fundamental matrix An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e150.jpg of an absorbing chain is defined as the inverse of the matrix An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e151.jpg, where An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e152.jpg is the sub-matrix of the transition matrix An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e153.jpg restricted to the set of transient states [27]. Entry An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e154.jpg of the fundamental matrix has a nice probabilistic interpretation: it corresponds to the mean time spent by the process in configuration An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e155.jpg if it starts in An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e156.jpg. Note that this value is finite because An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e157.jpg is defined on the transient states. Relying on our extended notion of absorbing chains, when ergodic sets are deterministic cycles, we can similarly define a fundamental matrix and use the same rationale by simply considering a power of An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e158.jpg instead of An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e159.jpg.

Therefore, starting in the configuration An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e160.jpg (or An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e161.jpg), for typical values of the parameters around An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e162.jpg (An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e163.jpg), the mean time spent by the process in one of the transient configurations is of order one (actually An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e164.jpg). It diverges when the parameters tend to opposite extreme values (An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e165.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e166.jpg) or (An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e167.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e168.jpg), where at the limit, a third fixed point appears. Instead, when both parameters are close to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e169.jpg or An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e170.jpg, the dynamics still encompasses two absorbing configurations, while expected times to reach these configurations tend to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e171.jpg or An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e172.jpg.

When An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e173.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e174.jpg are fixed to their extreme values (An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e175.jpg or An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e176.jpg), the system is deterministic, and the rules governing the evolution of the nodes can be defined by means of logical connectors. Here,

  • An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e177.jpg corresponds to an AND rule on both nodes (the presence of the two activators is required to reach level An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e178.jpg);
  • An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e179.jpg corresponds to an OR rule on both nodes (the presence of at least one activator is required to reach level An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e180.jpg);
  • An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e181.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e182.jpg corresponds to an OR rule on node An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e183.jpg and an AND rule on node An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e184.jpg;
  • An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e185.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e186.jpg corresponds to an AND rule on node An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e187.jpg and an OR rule on node An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e188.jpg.

A remarkable feature of this type of models is its ability to continuously exchanging two logical connectors by weighting the respective probabilities of implementation. For instance when An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e189.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e190.jpg is the probability to activate the dynamical connection corresponding to an OR rule on node An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e191.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e192.jpg is the probability corresponding to an AND rule. This is clearly illustrated in the dynamical graphs in Figure 2. In this sense, we can say that the border of the parameter domain constitutes a continuous family of Stochasticity In Functions models (SIF) following the definition in [22]. The whole parameter domain can thus be seen as a generalisation of these stochastic models, also corresponding to the probabilistic Boolean networks proposed by Schmulevich et al. [17].

In fact, by a theorem on random map realisations of Markov chains (see [28], chapter 1.2), our two-node models can be realised as random walks on the set of the dynamical graphs of the four extreme models (i.e. for which the parameters An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e193.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e194.jpg equal An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e195.jpg or An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e196.jpg). Let us denote these dynamical graphs by An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e197.jpg (for An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e198.jpg), An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e199.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e200.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e201.jpg (see Figure 2). Notice that, in the dynamics of these deterministic models, any configuration has a unique outgoing transition. At each time step, one extreme model is randomly and independently selected and the next configuration is chosen according to the (unique) transition leaving the current configuration of the corresponding dynamical graph. An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e202.jpg is taken with probability An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e203.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e204.jpg with probability An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e205.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e206.jpg is taken with probability An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e207.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e208.jpg with probability An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e209.jpg. This random walk has exactly the same probabilistic transitions as the original IP1 model depicted in Figure 2.

Model class IP2

It includes the two models An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e210.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e211.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e212.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e213.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e214.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e215.jpg. From the structural symmetry point of view, this class contains the models with self-inhibitions and symmetrical cross-interactions (i.e. positive two-node circuits).

The model An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e216.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e217.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e218.jpg is changed into An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e219.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e220.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e221.jpg by permuting the entries An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e222.jpg and changing An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e223.jpg to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e224.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e225.jpg to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e226.jpg. The two models are also self-symmetric by node symmetry. Because the two deterministic arrows (i.e. with probability An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e227.jpg) interchange two states, the corresponding Markov chains are absorbing with a unique attractor, a period-2 cycle (see Figure 3). Therefore, regardless the initial configuration, all the realisations end up in this cycle, with probability one.

Figure 3
The dynamics of the IP2 model An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e228.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e229.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e230.jpg.

Because An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e231.jpg, the transient dynamics of An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e232.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e233.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e234.jpg and of An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e235.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e236.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e237.jpg are identical and the analysis of the parameter space follows along the same lines as for the previous class.

Model class IP3

It includes four models: An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e238.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e239.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e240.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e241.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e242.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e243.jpg, and their homologous node symmetric An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e244.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e245.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e246.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e247.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e248.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e249.jpg. From the structural symmetry point of view, this class contains all the models asymmetrical with respect either to the self-interaction or to the cross-interactions. By permuting the entries: An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e250.jpg and by changing An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e251.jpg to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e252.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e253.jpg to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e254.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e255.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e256.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e257.jpg is changed in An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e258.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e259.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e260.jpg. Notice that an IP2 model cannot be isomorphic to an IP3 model, even if they share the same diagonal elements. This is because, in the IP2 class, the deterministic arrows deal with two states while in the IP3 class, four states are concerned and this property is invariant by isomorphism of the state space. IP3 models define regular chains (the four states constitute a unique ergodic set, unless the parameters take extreme values), but the presence of the two deterministic transitions put an extra weight on the correspondent target states.

Figure 4 shows that there are many cycles, giving rise to oscillations that can visit any configuration in any order and with different return times. The mean return times to each configuration An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e261.jpg, kind of a mean period of the oscillations, can be computed from the invariant probability distribution and reads:

equation image
(7)

We recall that An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e263.jpg, the mean time taken by a regular chain that starts at An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e264.jpg to return to its starting point (the mean return time at An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e265.jpg), is given by the inverse of the An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e266.jpgth component of the limiting probability vector (see [27], Theorem 4.4.5). It is also possible to compute this value using the fundamental matrix of the process ([27], Theorem 4.4.7). Note that, for a regular Markov chain, the definition of the fundamental matrix slightly differs from that of an absorbing chain (see [27], Definition 4.3.2).

Figure 4
The dynamics of the IP3 model An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e267.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e268.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e269.jpg.

In Figure 5, the values of the mean return times An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e270.jpg are depicted as functions of An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e271.jpg, for An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e272.jpg. Not surprisingly, due to the deterministic transitions, the mean return time to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e273.jpg (resp. An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e274.jpg) is always larger than that to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e275.jpg (resp. An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e276.jpg). When An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e277.jpg tends to an extreme value, the system turns into an absorbing chain and the return times of the transient configurations diverge. As for the other IP models, the extreme cases correspond to models where rules are defined by means of logical connectors. Hence, Figure 5 is a further illustration of a continuous parameter swap between different logical rules.

Figure 5
Mean return times of the IP3 model An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e278.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e279.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e280.jpg as a function of An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e281.jpg, with An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e282.jpg fixed to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e283.jpg.

Model class OP1

It includes An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e289.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e290.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e291.jpg and its node symmetric counterpart An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e292.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e293.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e294.jpg. From the structural symmetry point of view, the class contains all the models with self-activations and asymmetrical cross-interactions. OP1 models are the probabilistic counterpart of the negative circuits studied in [29]: the dynamics is built on a fundamental period-4 cycle combined with fluctuating sojourns in each configuration. The transition matrix An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e295.jpg is:

equation image
(8)

Figure 6 illustrates the relevant features of the dynamics of this model. Notice that, by changing the parameters, it is possible to modulate the time spent in each configuration and therefore the mean period of the oscillations. This observation is corroborated by the computation of the mean return times:

equation image
(9)
Figure 6
The dynamics of the OP1 model An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e298.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e299.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e300.jpg.

For extreme values of the parameters, the system is bistable.

Model class OP2

It includes the two models An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e301.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e302.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e303.jpg and its node symmetric counterpart An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e304.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e305.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e306.jpg. From the structural symmetry point of view, the class contains all the models with self-inhibitions and asymmetrical cross-interactions (negative circuits between the two nodes).

Figure 7 shows the existence of synchronous transitions where both nodes change simultaneously their values, inducing various period-2, 3 and 4 cycles. Combinations of these cycles lead to oscillations of any order. The extreme cases display four deterministic periodic dynamics, each including one synchronous transition that involves simultaneous updates of the two nodes. The analytical expressions of the mean return times are:

equation image
(10)
Figure 7
The dynamics of the OP2 model An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e311.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e312.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e313.jpg.

The set of equations (10) fully supports the idea of continuous parametric transitions among these dynamics: while the probability of a period-3 cycle increases as parameters tend to their extreme values (An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e308.jpg or An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e309.jpg), for intermediate parameter values, higher values of An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e310.jpg indicate that the period-4 orbits become prominent.

Model class OP3

It includes four models, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e314.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e315.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e316.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e317.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e318.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e319.jpg and their node symmetric counterparts. From the structural symmetry point of view, the class contains all the models with self asymmetrical interactions and symmetrical cross-interactions. By permuting the entries: An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e320.jpg and changing An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e321.jpg to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e322.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e323.jpg to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e324.jpg, model An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e325.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e326.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e327.jpg is changed into An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e328.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e329.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e330.jpg. The dynamics of these models alternate chains of period-1 to 4 cycles. It may thus be viewed as a transition between OP1 and OP2 models.

Figure 8 exhibits the dynamical properties of this model. In particular, in the extreme cases, we observe the existence of deterministic fixed points possibly combined with a period-2 cycle.

Figure 8
The dynamics of the OP3 model An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e331.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e332.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e333.jpg.

The existence of oscillations of any period is also shown in Figure 8 and Equation (11) points to a large variety of time scales of the oscillations when parameters are changed:

equation image
(11)

Two Majority Rule variants

Here, we briefly analyse the cases of the two variants previously introduced: the Inertial Majority Rule (IMR) and the Null Majority Rule (NRM).

The Inertial Majority Rule

This rule defines that, whenever activations and repressions cancel each other out, the next level of a node depends on its current level (Equation (2)). For our two-node models under the IMR, we can define the same isomorphism classes as those of the MR. From Figure 9, one can observe that the symmetry for the IMR is slightly different from that of the MR. There are two types of probabilistic choices, introducing a row reflection An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e335.jpg besides the rotation An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e336.jpg to relate the modules. For example, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e337.jpg evolution in Figure 9 is obtained by rotating module An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e338.jpg rows (transforming An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e339.jpg into An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e340.jpg). As a consequence, the isomorphism between models under the IMR relies on a different parameter change when compared to the MR: An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e341.jpg is changed to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e342.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e343.jpg to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e344.jpg. However, IMR and MR have exactly the same model classes and similar dynamics. Only differences regarding transition probabilities arise for the models combining an even and an odd module, i.e. an even and an odd column of Figure 1 (for the MR model) and Figure 9 (for the corresponding IMR model). For instance, in the case of the OP3 model An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e345.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e346.jpgAn external file that holds a picture, illustration, etc.
Object name is pone.0069626.e347.jpg, defined by the third and fourth columns of Figures 1 and and9,9, the two loop transition probabilities are different for the MR (namely An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e348.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e349.jpg), whereas they are identical for the IMR (namely An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e350.jpg). The probabilities of the transitions connecting configurations An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e351.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e352.jpg similarly differ between the MR and the IMR. The reason for this clearly appears in the Figures 1 and and99 where the probabilistic choices are identical in both columns for the MR whereas they are opposite for the IMR.

Figure 9
The four modules and their evolutions for the Inertial Majority Rule (IMR).

The Null Majority Rule

The majority determined under the NMR is quite different as compared to that of the MR and the IMR (see Equation (3)). Indeed, a node whose level is An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e365.jpg has no contribution in the updating decision of its targets. Still, one can define a bijection between both representations. In any configuration, let An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e366.jpg denote the (global) contribution of the regulators targeting node An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e367.jpg (i.e. An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e368.jpg). We have:

equation image
(12)

Note that the very same change of variables was defined by F. Robert, coming up with two equivalent formulations for threshold networks [30]. However, to ensure equal dynamics, the threshold functions and the thresholds were accordingly modified. Here, our purpose is different and amounts to revising the semantics of repression contributions (therefore the zero threshold is maintained for all the nodes).

The modules An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e370.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e371.jpg are identical under the MR and NMR because, in these cases, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e372.jpg (see Figure 10). As a consequence, the four NMR models built with these modules have the very same dynamics as their MR counterparts. Moreover, considering the NMR, if at a given time, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e373.jpg, then An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e374.jpg and the sixteen models have the same probabilistic updating for this configuration. Finally, it is easy to check that starting at time An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e375.jpg from the remaining configurations An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e376.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e377.jpg or An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e378.jpg, the updating process leads to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e379.jpg in the module An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e380.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e381.jpg in An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e382.jpg. From these observations, it turns out that NMR models have more deterministic transitions than their MR analogs. Not surprisingly, there are thus more absorbing models under the NMR than under the MR. This is a remarkable difference from the biological perspective since under the NMR, in eleven out of sixteen models, the dynamics converge to a fixed point or a small cycle. Hence the NMR displays robust, restricted behaviours. Moreover, changes in parameters values only impact times for convergence to attractors whose identities are conserved. In contrast, the MR is more flexible, leading to models with a larger variety of behaviours.

Figure 10
The four modules and their evolutions for the null majority rule (NMR).

Finally, with the INMR that results from the combination of the inertial and null majority rules, the module evolutions are similar to those defined in Figure 10, except that for configuration An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e390.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e391.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e392.jpg are interchanged (i.e. for all the modules, value An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e393.jpg is chosen with probability An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e394.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e395.jpg with probability An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e396.jpg).

The yeast cell cycle network revisited

The original model

The eukaryotic cell cycle defines a series of phases undergone by cells that divide, giving rise to daughter cells. G1 is a growing phase, known as gap 1 phase, followed by the S phase of DNA synthesis and chromosome replication. Then, after the gap phase G2, the M phase proceeds with the separation of the chromosomes and culminates with cell division. In [8], Li et al define a Boolean Gene Regulatory Network that encompasses the main regulators of the cell cycle progression in the budding yeast. The network supporting this model is depicted in Figure 11. The authors use a deterministic Inertial Null Majority Rule, hence the 11 variables An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e397.jpg take values An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e398.jpg or An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e399.jpg, and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e400.jpg when An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e401.jpg with probability An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e402.jpg. Interestingly, Davidich and Bornhold's Boolean model of the fission yeast cell cycle uses the very same rule [10]. Recently, Fauré and Thieffry describe and compare logical models of the molecular networks controlling the cell cycle in different eukaryotic organisms [11].

Figure 11
The yeast cell cycle model as defined in [8].

Cyclin Cln3 is known to be crucial for the cell commitment to S phase, i.e. for the cell cycle progression. In this model, Cln3 (An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e407.jpg) thus acts as an input of the network (possibly stimulated by a start signal). As a key feature, the model has a fixed point denoted An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e408.jpg, which corresponds to the G1 phase and that attracts most of the trajectories, considering all possible initial conditions. There are other six fixed points in the model, but those have a rather restricted basin of attraction and no meaningful biological counterparts. Moreover, starting from the state An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e409.jpg, and artificially switching Cln3 ON, the model follows a trajectory matching the cell cycle progression until reaching back the state An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e410.jpg.

Li et al considered the large size of the basin of attraction of the biological fixed point An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e411.jpg as a good indication of the robustness of the network to perform its function. This is confirmed by showing that the size of this basin of attraction is mostly preserved under perturbations that randomly remove or introduce a regulatory interaction. In [25], Stoll et al. propose another type of perturbations: 1) shuffling the wiring yet keeping the connectivity at each node or 2) removing one to several regulatory interactions. Using Li et al.'s model as a case study, they consider the size distribution of the basins of attraction and distance to a reference attractor as useful measures to assess impact of these perturbations. Zhang and colleagues assess the effect of stochasticity on the Li et al. model by turning it to a probabilistic model where all transitions in the configuration space are made possible [18].

In the framework of the present work, it is natural to consider the model described above as an extreme case of its stochastic version and to study the robustness of the dynamical behaviour faced to perturbations in the probability parameter space.

Therefore, we consider the stochastic version of this model under the Inertial Null Majority Rule: when An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e412.jpg (the sum of the contributions is zero) we have An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e413.jpg with probability An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e414.jpg, otherwise An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e415.jpg with probability An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e416.jpg. As for the two-node models under the NMR, all the modules are probabilistic. In particular, when all the node values equal zero (see Figure 10). In the configuration An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e417.jpg, all genes are inactive but An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e418.jpg (which negatively regulates An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e419.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e420.jpg) and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e421.jpg (which negatively regulates An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e422.jpg). We have thus that An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e423.jpg, hence An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e424.jpg is stable in An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e425.jpg, similarly for An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e426.jpg. Consequently, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e427.jpg is not absorbing, except if An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e428.jpg. When these parameters are closed to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e429.jpg, the system may be steady in An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e430.jpg long enough to match the biological situation, but it will eventually (after a finite time, with probability An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e431.jpg) leave An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e432.jpg, following a trajectory different from the cycle described in [8].

In the deterministic case, the INMR favours the existence of steady states including those with active genes whose regulators are all inactive; as discussed in [15], the fact that a node keeps its current value when the sum of the contributions is zero leads to frozen nodes. As already mentioned, the inertial rule amounts to add a self-activation on every node. It is worth mentioning that the self-inhibitions of the model (see Figure 11) are not functional (see [26]), they merely cancel out these self-activations, which are hidden in Li et al.'s model. In other words, for nodes that are only positively regulated, the NMR is applied.

In contrast to the deterministic INMR, the stochastic model does not display such a stability. The aforementioned property of the inertial deterministic rule that generates frozen nodes does not hold anymore. In particular, when regulators are absent, activations and inhibitions are not discriminated, giving rise to a large number of probabilistic configurations. This is the main reason why An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e433.jpg, together with the other steady configurations of the INMR model, are not robust to the stochastic extension and are not absorbing states.

The model revised, considering the stochastic MR

We now consider Li et al.'s model under the stochastic MR as defined by Equation (1). Node values are thus set to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e434.jpg or An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e435.jpg (and denoted by An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e436.jpg rather than An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e437.jpg). We recall that when the sum of its input contributions equals zero (An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e438.jpg), An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e439.jpg takes the value An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e440.jpg with probability An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e441.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e442.jpg with probability An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e443.jpg.

In order to analyse the dynamical features of the model, in particular regarding its steady states, we take advantage of the combination of deterministic and probabilistic operation modes. As we shall see, the deterministic part of the dynamics imposes strict restrictions that are worth to inspect prior to follow up the study. We describe the strategy in some detail because it can be easily generalised and thus used to study any model under the same rule.

Recall that a configuration of the module An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e444.jpg includes the values of all the regulators An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e445.jpg of An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e446.jpg. Beside the input node An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e447.jpg, the yeast cell-cycle network has five deterministic modules, i.e. with odd in-degree, the remaining five being probabilistic. For a probabilistic module An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e448.jpg, only configurations such that An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e449.jpg have a probabilistic outcome. An absorbing configuration An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e450.jpg, i.e for which An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e451.jpg, the element of the transition matrix equals An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e452.jpg, verifies:

equation image

We first search for the steady configurations of the deterministic modules (they strongly restrict the number of candidates of absorbing configurations). Among the 32 configurations of the five deterministic nodes, we easily end up with only two candidates. All the other 30 configurations are discarded because they are not steady for at least one deterministic module. These two remaining configurations, steady for all the five deterministic modules, are An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e454.jpg = (An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e455.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e456.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e457.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e458.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e459.jpg) and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e460.jpg = (An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e461.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e462.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e463.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e464.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e465.jpg). The former matches the biological fixed point An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e466.jpg for the five deterministic modules, and the latter corresponds to its mirror image. Notice that the existence of these two solutions is a consequence of the correspondent symmetry of the MR (An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e467.jpg versus An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e468.jpg).

We then look for all the possible extensions to the remaining six probabilistic nodes of these two solutions. The number of such extensions may be reduced if the values of the deterministic regulators of a probabilistic module determine the value of the corresponding node. Because An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e469.jpg implies that An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e470.jpg, which is not compatible with An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e471.jpg, we conclude that An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e472.jpg has no steady extensions.

Let us now explore the possible steady extensions of An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e473.jpg. Recall that An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e474.jpg in An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e475.jpg. Clearly, from the already known inputs of module An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e476.jpg (that are An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e477.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e478.jpg), it follows that An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e479.jpg. Looking now to the five known values for module An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e480.jpg (i.e An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e481.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e482.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e483.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e484.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e485.jpg itself), we conclude that An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e486.jpg, which in turn implies An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e487.jpg. It remains to investigate An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e488.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e489.jpg. In order to have An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e490.jpg with non-zero probability (in fact An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e491.jpg) we should have An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e492.jpg. For module An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e493.jpg, we have An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e494.jpg with probability An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e495.jpg. On the other hand, in order to be consistent with the values already fixed for module An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e496.jpg, we need to set An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e497.jpg, which is the case with probability An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e498.jpg. Therefore An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e499.jpg is steady with probability An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e500.jpg. Remarkably, this analysis shows that the only steady configuration is An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e501.jpg, even if it is not absorbing; no other configuration remains steady with a non-zero probability.

This encouraging result naturally leads us to search for minimal changes in the interaction network that would turn An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e502.jpg into an absorbing configuration. The first simple modification consists in eliminating the self-inhibition of An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e503.jpg, making this module deterministic with the proper outcome. Note that, because the MR accounts for the absence of a regulator, we could safely clean up the model by discarding the self-inhibitions of An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e504.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e505.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e506.jpg, An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e507.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e508.jpg. These were artificially added in the original model to ensure self-degradation of components that are not subject to other inhibition, under the INRM, and their elimination does not modify the results presented here. It remains the drawback of modules An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e509.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e510.jpg. They can be fixed with probability one either by adding a positive interaction from a node whose values is An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e511.jpg in the configuration An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e512.jpg, or by adding a negative interaction from a node whose value is An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e513.jpg in An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e514.jpg. Interestingly, a modification that fulfils these constraints was mentioned by Fauré and Thieffry who propose to account for biological data suggesting that Cln1/2 and Clb5/6 positively their own transcription factors [11]. Adding these positive interactions from An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e515.jpg to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e516.jpg (Cln1/2 to SBF) and from An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e517.jpg to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e518.jpg (Clb5/6 to MBF), An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e519.jpg is the only steady configuration that turns out to be absorbing, that is to say to have a maximal robustness in the Markov chain context.

A subsequent question arises that concerns the existence of other absorbing trajectories in this modified model. By generating the state transition diagram of the corresponding Markov chain, we could verify that, when An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e520.jpg, the An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e521.jpg state is the unique attractor and thus, as mentioned above, for An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e522.jpg, it is easy to deduce that the unique attractor is An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e523.jpg, the mirror state of An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e524.jpg. Hence, with probability An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e525.jpg, the system will reach either An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e526.jpg or An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e527.jpg, depending on the value of the input node An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e528.jpg. We have thus a full characterisation of the asymptotical behaviour of the model.

In this section, the cell cycle model of Li et al. has been used to illustrate the interest of our stochastic majority rule. Detailed biological interpretation of the model properties and further study to assess transient behaviours go beyond the scope of this paper.

Discussion

In this work, we have presented a stochastic extension of threshold Boolean networks that includes both deterministic and probabilistic rules. In contrast to other studies where all transitions are made stochastic (e.g. [18]), a probabilistic choice is made only when the sum of the contributions equals the threshold (often set to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e529.jpg), otherwise, the update is deterministic. This is rather natural from the biological view point. Indeed, it is reasonable to assign a probability to the update choice when regulatory effects cancel each others.

The originality of this model lies in the coexistence of deterministic and probabilistic nodes (or modules) in the same gene network; the former have a deterministic outcome for any input configuration, while the latter have probabilistic choice in certain configurations. This natural ambivalence open new interesting dynamical characteristics, yet avoiding a useless combinatorial explosion of trajectories. This point allows a rigorous analysis of certain dynamical properties of the model. In particular, we have shown how all the steady configurations may be identified and their properties modified in agreement with biological observations. More specific features of the dynamics, as for instance the mean sojourn and return times, can be studied in this formalism, allowing an almost complete description of the dynamical properties of the models.

We have introduced the majority rule (MR) as a convenient setting, compared to the null (inertial) majority rule: variables taking values An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e530.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e531.jpg amount to consider that the absence of a regulator has an effect opposite to that observed when the regulator is present. When variables take values An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e532.jpg and An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e533.jpg, the absence of a regulator is not accounted for in the rule. This has serious consequences: if a node is exclusively subject to inhibitions, there is no configuration for which its value is updated to An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e534.jpg, except under the inertial majority rule. The inertial majority rule introduces a self-activation on all the nodes and, for this reason, Li et al. as Davidich and Bornholdt, have introduced self-inhibitions on genes that are not negatively regulated otherwise [8], [10].

By thoroughly exploring the properties of simple two-node motifs, we could demonstrate the variety of the behaviours induced by our stochastic extension. Its application to Li et al.'s model indicates that it can be used to propose modifications of the model: here, we have shown that to turn the biological state An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e535.jpg into an absorbing state, one needs to add specific regulatory arcs to the network.

As shortly demonstrated for the cell cycle model, a systematic, efficient method to search for steady (absorbing) states should be relatively easy to implement. Moreover, this method can provide useful indications for model revision in order to ensure that a given state is absorbing. To search for other steady complex behaviours of the revised model, we have generated the corresponding transition diagram. Noticeably, we have verified that An external file that holds a picture, illustration, etc.
Object name is pone.0069626.e536.jpg and its mirror states are the sole ergodic states. Future work would focus on a more detailed analysis of the properties of the model such as the nature of the transient dynamics, e.g. providing measures on mean return times.

Extension of the present work also includes the consideration of non-zero thresholds in the majority rule. Importantly, the stochastic extension presented here applies for integer thresholds (considering integer interaction weights); indeed, threshold real values avoid the case of equality in the sum of the regulatory contributions [15]. Note however that, in this case, the probabilistic alternative may be considered as a consequence of uncertainty when gene expression is too close to the theoretical threshold, specially due to local inhomogeneities of protein concentrations.

Funding Statement

This work was partially supported by the Fundação de Ciência e Tecnologia (PTDC/EIA-CCO/099229/2008). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript. No additional external funding received for this study.

References

1. de Jong H (2002) Modeling and simulation of genetic regulatory systems: a literature review. J Comput Biol 1: 67–103. [PubMed]
2. Fisher J, Henzinger T (2007) Executable cell biology. Nat Biotechnol 25: 1239–1249. [PubMed]
3. Kauffman SA (1969) Metabolic stability and epigenesis in randomly constructed genetic nets. J Theor Biol 22: 437–67. [PubMed]
4. Thomas R (1973) Boolean formalization of genetic control circuits. J Theor Biol 42: 563–85. [PubMed]
5. Bornholdt S (2008) Boolean network models of cellular regulation: prospects and limitations. J R Soc Interface 5 Suppl 1: S85–94. [PMC free article] [PubMed]
6. Glass L, Siegelmann HT (2010) Logical and symbolic analysis of robust biological dynamics. Curr Opin Genet Dev 20: 644–9. [PubMed]
7. Thomas R, D'Ari R (1990) Biological feedback. Boca Raton: CRC Press.
8. Li F, Long T, Lu Y, Ouyang Q, Tang C (2004) The yeast cell-cycle network is robustly designed. Proc Natl Acad Sci U S A 101: 4781–6. [PubMed]
9. 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: 124–131. [PubMed]
10. Davidich MI, Bornholdt S (2008) Boolean network model predicts cell cycle sequence of fission yeast. PLoS One 3: e1672. [PMC free article] [PubMed]
11. Fauré A, Thieffry D (2009) Logical modelling of cell cycle control in eukaryotes: a comparative study. Mol Biosyst 5: 1569–81. [PubMed]
12. Fauré A, Naldi A, Lopez F, Chaouiya C, Ciliberto A, et al. (2009) Modular logical modelling of the budding yeast cell cycle. Mol Biosyst 5: 1787–96. [PubMed]
13. Irons DJ (2009) Logical analysis of the budding yeast cell cycle. J Theor Biol 257: 543–559. [PubMed]
14. Mendoza L, Xenarios I (2006) A method for the generation of standardized qualitative dynamical systems of regulatory networks. Theor Biol Med Model 3: 13. [PMC free article] [PubMed]
15. Zañudo J, Aldana M, Martínez-Mekler G (2011) Boolean threshold networks: Virtues and limitations for biological modeling. In: Niiranen S, Ribeiro A, editors, Information Processing and Biological Systems, Springer Berlin Heidelberg, volume 11 of Intelligent Systems Reference Library. pp. 113–151.
16. McCulloch WS, Pitts W (1943) A logical calculus of the ideas immanent in nervous activity. Bulletin of Mathematical Biophysics 5: 115–133. [PubMed]
17. Shmulevich I, Dougherty ER, Kim S, Zhang W (2002) Probabilistic boolean networks: a rule-based uncertainty model for gene regulatory networks. Bioinformatics 18: 261–74. [PubMed]
18. Zhang Y, Qian M, Ouyang Q, Deng M, Li F, et al. (2006) Stochastic model of yeast cell-cycle network. Physica D: Nonlinear Phenomena 219: 35–39.
19. Lee WB, Huang JY (2009) Robustness and topology of the yeast cell cycle boolean network. FEBS Lett 583: 927–32. [PubMed]
20. Alvarez-Buylla ER, Chaos A, Aldana M, Benítez M, Cortes-Poza Y, et al. (2008) Floral morphogenesis: stochastic explorations of a gene network epigenetic landscape. PLoS One 3: e3626. [PMC free article] [PubMed]
21. Murrugarra D, Veliz-Cuba A, Aguilar B, Arat S, Laubenbacher R (2012) Modeling stochasticity and variability in gene regulatory networks. EURASIP J Bioinform Syst Biol 2012: 5. [PMC free article] [PubMed]
22. Garg A, Mohanram K, Di Cara A, De Micheli G, Xenarios I (2009) Modeling stochasticity and robustness in gene regulatory networks. Bioinformatics 25: i101–9. [PMC free article] [PubMed]
23. Hopfield JJ (1982) Neural networks and physical systems with emergent collective computational abilities. Proc Natl Acad Sci U S A 79: 2554–8. [PubMed]
24. Braunewell S, Bornholdt S (2007) Superstability of the yeast cell-cycle dynamics: ensuring causality in the presence of biochemical stochasticity. J Theor Biol 245: 638–43. [PubMed]
25. Stoll G, Rougemont J, Naef F (2007) Representing perturbed dynamics in biological network models. Phys Rev E 76: 011917. [PubMed]
26. Remy E, Ruet P (2008) From minimal signed circuits to the dynamics of boolean regulatory networks. Bioinformatics 24: i220–6. [PubMed]
27. Kemeny JG, Snell JL (1976) Finite Markov chains. New York: Springer-Verlag.
28. Levin DA, Peres Y, Wilmer EL (2009) Markov chains and mixing times. Providence, R.I.: American Mathematical Society.
29. Coutinho R, Fernandez B, Lima R, Meyroneinc A (2006) Discrete time piecewise affine models of genetic regulatory networks. J Math Biol 52: 524–70. [PubMed]
30. Robert F (1995) Les systèmes dynamiques discrets, volume 19. Berlin: Springer.

Articles from PLoS ONE are provided here courtesy of Public Library of Science