Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

In Systems Biology, modelers develop more and more reaction models to describe the biochemical reactions underlying cell processes. This approach is promoted by reaction-model exchange formats such as SBML [18] and by the subsequent creation of large reaction-based model repositories such as BioModels [25], without prejudging of their interpretation by differential equations, Markov chains, Petri nets, or boolean transition systems [12].

Modelers can also work, however, with a simpler formalism of influence systems to merely describe the positive and negative influences between molecular species, without fixing their implementation with biochemical reactions. In particular, boolean influence systems have been popularized in the 70’s by Glass, Kauffman [15] and Thomas [30, 31] to reason about gene regulatory networks, represented by ordinary graphs between genes given with a boolean transition table which defines their synchronous or asynchronous boolean transition semantics. Necessary conditions for multi-stability (cell differentiation) and oscillations (homeostasis) have been given in terms of positive or negative circuits in the influence graph [27, 29]. Several tools such as GINsim [22], GNA [4] or Griffin [28], use these properties and powerful graph-theoretic and model-checking techniques to automate reasoning about the boolean state transition graph, compute attractors and verify various reachability and path properties. The representation of boolean influence systems by Petri nets was described in [6] but leads to complicated encodings. It is also worth mentioning that influence systems with spatial information have been nicely developed in [7] as a formalism particularly suitable for describing natural algorithms in life sciences and social dynamics.

In Systems Biology, modelers often reason with both kinds of formalisms, and may find it useful to use and maintain an influence model in the process of building a reaction model, for instance in order to reduce it while preserving the essential influence circuits [23]. One reason is that it is easier to visualize influence systems, rather than reaction systems for which complicated graphical conventions such as SBGN [26] have been developed. While it is clear that the influence graph is an abstraction of the reaction hypergraph [12], and perhaps more surprisingly that the Jacobian influence system derived from the differential semantics of a reaction system is largely independent of the kinetics [13], influence models are mostly used for their graphical representation and their boolean semantics, but more rarely as a modeling paradigm for systems biology with quantitative semantics using differential equations, or stochastic semantics.

In this paper, we introduce a formalism of influence systems with forces, which we put in parallel with reaction systems with kinetics, in order to develop a similar hierarchy of boolean, discrete, stochastic and differential semantics for influence systems, similarly to what is done for reasoning about programs in the framework of abstract interpretation [10, 12]. We show that the expressive power of influence systems is the same as that of reaction systems under the differential semantics, but is weaker under the other interpretations, in the sense that some formal discrete behaviours of reaction systems cannot be expressed by influence systems. This approach provides an influence model with a hierarchy of possible interpretations related by precise abstraction relationships, so that, for instance, if a behavior is not possible in the boolean semantics, it is surely not possible in the stochastic semantics whatever the influence forces are.

This leads us to consider a positive boolean semantics which we compare to the asynchronous semantics of gene regulatory networks à la Thomas. We study the monotonicity properties of the positive boolean semantics and derive from them an efficient algorithm to compute attractors. These concepts are illustrated with models from the literature.

2 Preliminaries on Reaction Systems with Kinetics

In this article, unless explicitly noted, we will denote by capital letters (e.g. S) sets or multisets, by bold letters (e.g., \({\varvec{x}}\)) vectors and by small roman or Greek letters elements of those sets or vectors (e.g. real numbers, functions). For a multiset M, let \(\text {Set}(M)\) denote the set obtained from the support of M, and brackets like M(i) denote the multiplicity in the multiset (usually the stoichiometry). \(\ge \) will denote the pointwise order for vectors, multisets and sets (i.e. inclusion).

2.1 Syntax

We recall here definitions from [11, 13] for directed reactions with inhibitors:

Definition 1

A reaction over molecular species \(S = \{x_1,\dots ,x_s\}\) is a quadruple (R, M, P, f), also noted \(f \mathbin {\text { for}}R / M \Rightarrow P\), where R is a multiset of reactants, M a set of inhibitors, P a multiset of products, all composed of elements of S, and \(f:\mathbb {R}^s\rightarrow \mathbb {R}\), called kinetic expression, is a mathematical function over molecular species concentrations. A reaction system is a finite set of reactions.

It is worth noting that a molecular species in a reaction can be both a reactant and a product (i.e. a catalyst), or both a reactant and an inhibitor (e.g. Botts–Morales enzymes [19]). Such molecular species are not distinguished in SBML and both are called reaction modifiers. Unlike SBML, we find it useful to consider only directed reactions (reversible reactions being represented here by two reactions) and to enforce the following compatibility conditions between the kinetic expression and the structure of a reaction.

Definition 2

([11, 13]). A reaction (R, M, P, f) over molecular species \(\{x_1,\dots ,x_s\}\) is well formed if the following conditions hold:

  1. 1.

    \(f(x_1,\dots ,x_s)\) is a partially differentiable function, non-negative on \(\mathbb {R}_+^s\);

  2. 2.

    \(x_i\in R\) if and only if \({\partial {f}}/ {\partial x_i}({\varvec{x}})>0\) for some value \({\varvec{x}}\in \mathbb {R}_+^s\);

  3. 3.

    \(x_i\in M\) if and only if \({\partial {f}}/ {\partial x_i}({\varvec{x}})<0\) for some value \({\varvec{x}}\in \mathbb {R}_+^s\).

A reaction system is well formed if all its reactions are well formed.

Example 1

The classical prey-predator model of Lotka–Volterra can be represented by the following well-formed reaction system (without reaction inhibitors) between a proliferating prey A and a predator B:

figure a

2.2 Hierarchy of Semantics

As detailed in [12], a reaction system can be interpreted with different formalisms that are formally related by abstraction relationships in the framework of abstract interpretation [10] and form a hierarchy of semantics. We simply recall here the definitions of the different semantics of a reaction system.

The differential semantics corresponds to the association of an Ordinary Differential Equation (ODE) system with the reactions in the usual way:

$$\begin{aligned} \frac{dx_j}{dt} = \sum _{(R_i, M_i, P_i, f_i)}(P_i(j) - R_i(j))\times f_i \end{aligned}$$

It is worth noting that in this interpretation, the inhibitors are supposed to decrease the reaction rate but do not prevent the reaction from proceeding with effects on the products and reactants. For instance, in Example 2, we get the classical Lotka–Volterra equations \(dB/dt = k1*A*B-k3*B\), \(dA/dt = k2*A-k1*A*B\), and the well-known oscillations between the concentrations of the prey and the predator.

The stochastic semantics for reaction systems defines transitions between discrete states describing numbers of each molecule, i.e. vectors \({\varvec{x}}\) of \(\mathbb {N}^s\). A transition is enabled if there are enough reactants, and the reaction propensity is defined by the kinetics:

$$\forall (R_i, M_i, P_i, f_i), {{\varvec{x}}}\longrightarrow _S^{f_i}{{\varvec{x}}'} \text { with propensity } f_i\text { if } {{\varvec{x}}}\ge R_i, {{\varvec{x}}'} = {{\varvec{x}}} - R_i + P_i$$

Transition probabilities between discrete states are obtained through normalization of the propensities of all enabled reactions, and the time of next reaction can be computed from the rates à la Gillespie [14]. In this interpretation, the inhibitors are supposed to decrease the reaction propensity but do not prevent the reaction from occurring. They are thus ignored here by the stochastic transition conditions as in the differential semantics. In Example 1, the stochastic interpretation can exhibit some oscillations similar to the differential interpretation, and (almost surely) the extinction of the predator.

The discrete, or Petri Net, semantics is similar but ignores the kinetics and is thus a trivial abstraction of the stochastic semantics by a forgetful functor:

$$\forall (R_i, M_i, P_i, f_i), {{\varvec{x}}}\longrightarrow _D{{\varvec{x}}'}\text { if } {{\varvec{x}}}\ge R_i, {{\varvec{x}}'} = {{\varvec{x}}} - R_i + P_i$$

The boolean semantics is similar to the discrete one but on boolean vectors x of \(\mathbb {B}^s\), obtained by the “zero, non-zero” abstraction of integers. With this abstraction, when the number of a molecule is decremented, it can still remain present, or become absent. It is thus necessary to take into account all the possible complete consumption or not of the reactants in order to obtain a correct boolean abstraction of the discrete and stochastic semantics [12]. The boolean transition system \(\longrightarrow _B\) is thus defined by:

\(\forall (R_i, M_i, P_i, f_i), \forall C\in \mathcal{P}(\text {Set}(R_i)), {{\varvec{x}}}\longrightarrow _B{{\varvec{x}}'}\) if \({{\varvec{x}}}\supseteq \text {Set}(R_i), {{\varvec{x}}'} = {{\varvec{x}}} \setminus C \cup \text {Set}(P_i)\)

It is worth remarking that in Example 2 under this boolean interpretation, one can observe either the stable coexistence of the prey and the predator, or the extinction of the predator with or without the preceding extinction of the prey.

As proven in [12], the last three of these semantics are related by successive Galois connections, which means that if a behaviour is not possible in the boolean semantics, it is not possible in the stochastic semantics whatever the reaction kinetics are. On the other hand, the first differential semantics is not an abstraction but rather a limit of the first one for high number of molecules, as shown for instance in [14].

It is worth noticing that the set of inhibitors of a reaction is just a syntactical annotation which has not been used to define the different semantics of the hierarchy. One can also consider a boolean semantics with negation where the set of inhibitors of a reaction is seen as a conjunction of negative conditions for the transition (disjunctions can be represented with several reactions). The boolean with negation transition system \(\longrightarrow _{BN}\) is then defined by:

figure b

However, this strict interpretation of inhibitors by negations restricts the set of possible boolean transitions and is not compatible with the differential semantics, since in that interpretation an inhibitor may just slightly decrease the rate of a reaction without preventing it from proceeding.

2.3 Influence Graph of a Reaction System

Here we recall two definitions of the influence graph associated with a reaction system, and their equivalence under general assumptions [11, 13]. The first definition is based on the Jacobian matrix J formed of the partial derivatives \(J_{ij} = {\partial \dot{x_i}}/ {\partial x_j}\), where \(\dot{x_i}\) is defined by the differential semantics.

Definition 3

The differential influence graph associated with a reaction system is the graph having for vertices the molecular species, and for edge-set the following two kinds of edges:

figure c

Definition 4

The syntactical influence graph associated with a reaction system M is the graph having for vertices the molecular species, and for edges the following set of positive and negative influences:

figure d

The syntactical graph is trivial to compute, in linear time, by browsing the syntax of the rules. Both definitions are equivalent under general assumptions:

Theorem 1

([11, 13]). For any well-formed reaction system such that the syntactical influence graph contains no conflict (i.e. no pair of the form \(A\rightarrow ^+ B\) and \(A\rightarrow ^- B\)), the syntactical and differential influence graphs are identical.

3 Influence Systems with Forces

Reaction systems allow the description of mechanistic models of cell processes, but modelers can also work with a simpler formalism of influence systems to merely describe the positive and negative influences between molecular species, without fixing their implementation with biochemical reactions. In this section, we propose a syntax for influence systems with forces which allows us to define a hierarchy of differential, stochastic, discrete and positive boolean semantics, similarly to reaction systems. We then focus on different boolean semantics, and compare them to Thomas’s setting for gene regulatory networks.

3.1 Syntax

The idea is to syntactically distinguish conjunctive from disjunctive conditions by writing influences with several sources for representing a conjunction of conditions, while the different influences on a same target express a disjunction of conditions. These syntactical conventions are a particular case of the concept of multiplexes introduced in [5] restricted here to disjunctive normal forms.

Definition 5

Given \(S = \{x_1,\dots ,x_s\}\) a set of species, an influence system I is a set of quintuples \((P, N, t, \sigma , f)\) called influences, where \(P\subset S\) is called the positive sources of the influence, \(N\subset S\) the negative sources, \(t\in S\) is the target, sign \(\sigma \in \{+,-\}\) is the sign of the influence, and f is a real-valued mathematical function of \(\mathbb {R}^s\), called the force of the influence.

Influences of sign \(+\) will be called positive influences and those of sign −, negative influences. In addition, we distinguish the positive sources from the negative sources in an influence (positive or negative), in order to annotate the fact that in the differential semantics, the source increases or decreases the force of the influence, and in the boolean semantics with negation whether the source or the negation of the source is a condition for a change in the target.

For practical reasons we provide an ASCII syntax for influence systems which is used in BiochamFootnote 1 v4: they will be written as sequences of lines, where each set is written as a comma-separated sequence of the corresponding species, where the sign is represented as an arrow separating sources from the target, for positive influences, and for negative influences, and where the positive and negative sources are separated by a that can be omitted if there is no negative source.

Let us now define the concept of well-formed influence systems similarly to the above Definition 2 for reaction systems, with a particular condition for the target of a negative influence, as follows:

Definition 6

An influence \((P, N, t, \sigma , f)\) over molecular species \(\{x_1,\dots ,x_s\}\) is well formed if the following conditions hold:

  1. 1.

    \(f(x_1,\dots ,x_s)\) is a partially differentiable function, non-negative on \(\mathbb {R}_+^s\);

  2. 2.

    \(x_i\in P\) if and only if \(\sigma = +\) (resp. −) and \({\partial {f}}/ {\partial x_i}({\varvec{x}})>0\) (resp. \(<0\)) for some value \({\varvec{x}}\in \mathbb {R}_+^s\);

  3. 3.

    \(x_i\in N\) if and only if \(\sigma = +\) (resp. −) and \({\partial {f}}/ {\partial x_i}({\varvec{x}})<0\) (resp. \(>0\)) for some value \({\varvec{x}}\in \mathbb {R}_+^s\);

  4. 4.

    \(t\in P\) if \(\sigma =-\).

An influence system is well formed if all its influences are well formed.

Example 2

The prey-predator model of Lotka–Volterra of Example 1 can also be represented by the following well-formed influence system

figure e

composed of four influences with positive sources only, \((\{A, B\}, \emptyset , A, -, k1*A*B)\), \((\{A, B\}, \emptyset , B, +, k1*A*B)\), \((\{A\}, \emptyset , A, +, k2*A)\) and \((\{B\}, \emptyset , B, -, k3*B)\).

3.2 Hierarchy of Semantics

Given a set of species \(S= \{x_1,\dots ,x_s\}\) and an influence system I over S, the differential semantics associates the following ODE system with I:

$$ \frac{dx_k}{dt} = \sum _{(P_i, N_i, x_k, +, f_i) \in I}f_i - \sum _{(P_j, N_j, x_k, -, f_j) \in I}f_j $$

Intuitively, it adds up all the forces of the positive influences on \(x_k\) and subtracts all forces of negative influences on \(x_k\) in the derivative of \(x_k\) over time. For instance, in Example 2, we get the same equations as for Example 1.

It is worth noticing that the negative sources in a well-formed influence decrease the force of the influence but do not disable it. Consequently, we define similarly the stochastic semantics of an influence system with forces, by a transition system, noted \(\longrightarrow _S\), between discrete states, i.e. vectors \({\varvec{x}}\) of \(\mathbb {N}^s\), with the condition that the positive sources are present in sufficient number, with a transition propensity defined by the force, and the target updated as follows:

$$\forall (P_i, N_i, A_i, \sigma _i, f_i), {{\varvec{x}}}\longrightarrow _S^{f_i}{{\varvec{x}}'} \text { with propensity}f_i\text { if }\, {{\varvec{x}}}\ge P_i, {{\varvec{x}}'} = {{\varvec{x}}}\ \sigma _i\ A_i$$

Transition probabilities between discrete states are obtained through normalization of the propensities of all enabled transitions, and the time of next reaction can also be given à la Gillespie [14]. In this interpretation, the negative sources are supposed to decrease the influence propensity but do not prevent the influence from proceeding. They are thus ignored here by the stochastic transition conditions.

The discrete (or Petri Net) semantics simply ignores the forces:

$$\forall (P_i, N_i, A_i, \sigma _i, f_i), {{\varvec{x}}}\longrightarrow _D{{\varvec{x}}'}\text { if } {{\varvec{x}}}\ge P_i, {{\varvec{x}}'} = {{\varvec{x}}}\ \sigma _i\ A_i$$

The positive boolean semantics is defined on boolean vectors x of \(\mathbb {B}^s\), by the “zero, non-zero” abstraction of integers of the discrete semantics. Unlike reaction systems, this boolean semantics associates one transition with one influence:

$$\forall (P_i, N_i, A_i, \sigma _i, f_i), {{\varvec{x}}}\longrightarrow _B{{\varvec{x}}'}\text { if }{{\varvec{x}}}\ge P_i, {{\varvec{x}}'} = {{\varvec{x}}}\ \sigma _i\ A_i$$

This boolean semantics is positive in the sense that it ignores the negative sources of an influence and contains no negation in the influence enabling condition. In Example 2 we get the same boolean transitions as in Example 1, although in general one can expect to get more transitions (as shown below in Sect. 3.4).

With these definitions, one can obtain as in [12], a hierarchy of semantics related by simple abstraction relationships (Galois connections in the framework of abstract interpretation [10]) which allows us to state, for instance, that if a behaviour is not possible in the positive boolean semantics, it is also not possible in the discrete or stochastic semantics for any forces.

3.3 Influence Graph of an Influence System

One can define the differential influence graph of an influence system as in Definition 3 for reaction systems, and get a similar equivalence result with the following

Definition 7

The syntactical influence graph associated with an influence system M is the graph having for vertices the molecular species, and for edges the following set of positive and negative influences:

figure f

Proposition 1

For a well-formed influence system such that the syntactical influence graph contains no conflict, the syntactical and differential influence graphs are identical.

Proof

Recall that \(\dot{x_B} = \sum _{(P_i, N_i, x_B, +, f_i) \in I}f_i - \sum _{(P_j, N_j, x_B, -, f_j) \in I}f_j\)

Hence \(\frac{\partial \dot{x_B}}{\partial x_A} = \sum _{(P_i, N_i, x_B, +, f_i) \in I}\frac{\partial f_i}{\partial x_A} - \sum _{(P_j, N_j, x_B, -, f_j) \in I}\frac{\partial f_j}{\partial x_A}\)

Since the SIG does not have any conflict, \(A\rightarrow ^+B\) is in the SIG (a similar reasoning can be made for \(A\rightarrow ^-B\)) iff

\( \frac{\partial \dot{x_B}}{\partial x_A} = \sum _{(P_i, N_i, x_B, +, f_i) \in I, A\in P_i, A\not \in N_i}\frac{\partial f_i}{\partial x_A} - \sum _{(P_j, N_j, x_B, -, f_j) \in I, A\not \in P_j, A\in N_j}\frac{\partial f_j}{\partial x_A} \)

Now, since the influence system is well formed, all terms of the left-hand sum are non-negative (\(A\not \in N_i\)) and strictly positive for some points \({\varvec{x}}_i\) and all terms of the right-hand sum are non-positive (\(A\not \in P_j\)) and strictly negative for some\({\varvec{x}}_j\).

We have that \(A\rightarrow ^+B\) in the SIG iff the above sum has at least one term, which is equivalent to the existence of some \({\varvec{x}}\) in the state space where one of the terms above is non-null, and therefore \(\frac{\partial \dot{x_B}}{\partial x_A} >0\), i.e., \(A\rightarrow ^+B\) is in the DIG.   \(\square \)

3.4 Expressive Power Compared to Reaction Systems

Theorem 2

Any (well-formed) influence system with forces can be represented by a (well-formed) reaction system with kinetics, with the same boolean, discrete, stochastic and differential semantics.

Proof

Let us represent a positive influence \(f \mathbin {\text { for}}P/N \rightarrow t\) by a catalytic synthesis reaction \(f \mathbin {\text { for}}P/N\Rightarrow P+t\).

Similarly, let us represent a negative influence , by an active degradation reaction \(f \mathbin {\text { for}}P+t/N\Rightarrow P\).

It is straightforward to verify that the boolean, discrete, stochastic as well as differential semantics recalled and defined above are the same.

Furthermore, the well-formedness condition is preserved. Indeed, this property only depends on the forces/kinetic expressions and on the reactants/inhibitors, which do not change through that transformation thanks to the condition that in well-formed influence systems. In addition, \(t \in P\) in the case of the negative influence.    \(\square \)

This theorem shows that an influence system can be simulated by a reaction system for the different semantics. The converse does not hold for the boolean semantics, for instance. Indeed, let us consider boolean semantics of the reaction \(C\Rightarrow A+B\) (the kinetics is omitted). We have a transition from the state \((A,B,C)=(0,0,1)\) to (1, 1, 0) which is obviously not possible in an influence system since only one variable can change in one transition. However, the converse holds for the differential semantics:

Theorem 3

Under the differential semantics, (well-formed) influence and reaction systems have the same expressive power.

Proof

For each reaction (R, M, P, f) of a given reaction system, let us add the following influences:

$$\begin{aligned} (\text {Set}(R), \text {Set}(M), x_i, +, (P(i) - R(i))\times f) \text { when } P(i) - R(i) > 0\\ (\text {Set}(R), \text {Set}(M), x_i, -, (R(i) - P(i))\times f) \text { when } P(i) - R(i) < 0 \end{aligned}$$

The associated ODE system collects all \((P_i - R_i)\times f\) exactly as in the differential semantics of the original reaction system. Furthermore, it is easy to check that these influences are well formed since the original reaction is well formed and the force is only a positive integer multiplied by the original kinetic expression.    \(\square \)

This theorem shows that as far as the differential semantics is concerned, the influence systems have the same expressive power as reaction systems and there is no theoretical reason to develop a reaction model. This does not mean that there is a canonical reaction system associated with an influence system. Generally, different implementations with reactions are possible without changing the differential semantics. They represent extra information that is irrelevant to the analysis or simulation of the differential equations, but could lead to different stochastic simulations, for instance.

3.5 Boolean Semantics with Negation

One can also consider a boolean semantics with negation for influence systems, where the negative sources are interpreted as negations in the enabling condition. Formally, the boolean with negation semantics of an influence system is then defined by the following transition system:

$$\forall (P_i, N_i, A_i, \sigma _i, f_i), {{\varvec{x}}}\longrightarrow _B{{\varvec{x}}'}\text { if }{{\varvec{x}}}\ge P_i,\ {{\varvec{x}}}\cap N_i=\emptyset ,\ {{\varvec{x}}'} = {{\varvec{x}}}\ \sigma _i\ A_i$$

This interpretation allows us to represent more boolean transition semantics. Let us call a unitary transition system, a transition system that updates at most one variable of \({\varvec{x}}\) in each transition. It is worth remarking that in this case, the state transition graph lives on a hypercube (e.g. Fig. 2 of Sect. 5).

Proposition 2

Any unitary boolean transition system can be represented by an influence system under the boolean semantics with negation.

Proof

It is sufficient to notice that since a unitary boolean transition \(s \longrightarrow _{ BN } s'\) changes at most one species, say \(x_i\), from s to \(s'\), it can be represented by either a positive influence, \((P,N,x_i,+)\), if \(s'(x_i)=1\), or a negative influence, \((P,N,x_i,-)\), if \(s'(x_i)=0\), with \(P=\{x \mid s(x)=1\}\) and \(N=\{x \mid s(x)=0\}\).    \(\square \)

Let us call a positive boolean transition system one that contains no negation in the conditions for enabling a transition, i.e. if a transition is enabled when \(s(x_i)=0\) then it is also enabled when \(s(x_i)=1\).

Corollary 1

Any unitary positive boolean transition system can be represented by an influence system under the positive boolean semantics.

Proof

In the influence system associated by Proposition 2 with a positive unitary transition system, any influence that has negative sources is doubled by a counterpart influence where such sources are positive (by definition of positive boolean transition system). Therefore, in the associated influence system, the negative sources can be simply ignored, as done by the positive boolean semantics.    \(\square \)

3.6 Functional Boolean Semantics with Negation à la Thomas

The boolean semantics defined by René Thomas originally for gene networks [31], is functional, in the sense that the next boolean state \({{\varvec{x}}}'\) is defined by a boolean function \(\phi ({\varvec{x}})\), not a relation. In this setting, the synchronous semantics is deterministic, and the non-deterministic asynchronous semantics is obtained by interleaving, by considering all the possible transitions that change the boolean value of exactly one of the genes at a time. A truly non-deterministic influence system such as \(\{(A,\emptyset ,B,+,f),\ (A,\emptyset , B,-,g)\}\), for which the transition relation is not a function, cannot be represented. Thomas’s setting excludes self-loops in the state transition graph and all steady states are stable (i.e. terminal states):

Proposition 3

The boolean transition systems definable by Thomas’s regulatory networks are the unitary boolean transition systems without self-loops.

Proof

A Thomas’s transition graph is necessarily unitary and without self-loops since each transition changes the boolean value of exactly (not at most) one variable at a time. The converse follows from Proposition 2 by excluding the possibility of having self-loop transitions which change no variable.    \(\square \)

This restriction to transition functions is even more striking in Thomas’s multilevel setting, where the above system can (in the discrete semantics) have transitions from (1, 1) both to (1, 0) and to (1, 2). That would necessitate the corresponding logical parameter for B to be at the same time \(<1\) and \(>1\). It is worth noting that despite this restriction, the logical formalism of Thomas is successfully used in a wide variety of models [16, 17, 24, 32] in systems biology.

4 Properties of the Positive Boolean Semantics

In this section, we focus on the positive boolean semantics of influence systems and study its properties. Recall that \(\le \) denotes the pointwise order on \(\{0,1\}\) coordinates of vectors representing states.

Proposition 4

(Monotonicity). The positive boolean semantics of influence systems is monotonic: let I be an influence system over \(S=\{x_1,\dots ,x_s\}\) and \(v_1, v_2\) be two boolean states, i.e., vectors of \(\mathbb {B}^s\)

figure g

Proof

One can simply notice that since there are no negations in the enabling conditions, any influence that is enabled in \(v_1\) is also enabled in \(v_2\).   \(\square \)

It is worth noticing that this monotonicity property for transitions is fundamentally different from that of monotone dynamical systems [3] which are deterministic, and therefore impose the monotonicity property on the unique image of \(v_1\) and \(v_2\). In our setting, Proposition 4 states that there exists some \(v'_2\ge v'_1\), but the existence of negative influences in the system permits that some other images of \(v_2\) might not be greater than \(v'_1\). Nevertheless, we have

Proposition 5

(Greatest element). Let C be a Terminal Strongly Connected Component (TSCC) of the state transition graph of a positive influence system, then C has a greatest element: \(\exists v_0\in C, \forall v\in C, v\le v_0\).

Proof

Let us prove this proposition by contradiction: assume that there are two incomparable maximal elements \(v_1\) and \(v_2\) in C. Since C is strongly connected there is a path from \(v_1\) to \(v_2\) and along that path a state \(v_3\) and its successor in the path \(v_4\) such that \(v_3\le v_1\) and \(v_4\not \le v_1\), as \(v_2\not \le v_1\). Now, using Proposition 4 we get that \(v_1\longrightarrow v'_1\) with \(v_4\le v'_1\) and \(v'_1\in C\) since C is terminal. However \(v'_1\) is either greater or less than \(v_1\) since it is the result of applying a single influence. If \(v_1 < v'_1\) we have a contradiction as we supposed \(v_1\) maximal. If \(v'_1\le v_1\) we get \(v_4\le v_1\) by transitivity and that is also contradictory.    \(\square \)

Corollary 2

To enumerate the attractors, i.e., TSCCs, of a positive influence system, it is enough to check the strongly connected components (SCCs) of states that have no strictly increasing transition.

Proof

This is an immediate consequence of Proposition 5 as each TSCC can be represented by its greatest element which has no strictly increasing transition.    \(\square \)

Notice that stable states are a particular case with no strictly decreasing transition either. Moreover, any strictly decreasing transition should be “reversible” for the SCC to be a TSCC. This allows us to rule out potential TSCC candidates without exploring their whole SCC in Algorithm 1 (implementation available in Biocham v4).

figure h

Proposition 6

Given an influence system, there is at least one TSCC of the original influence system in each TSCC of its positive semantics.

Proof

The positive semantics only adds transitions by enabling more influences, it can therefore only merge TSCCs.    \(\square \)

This result suggests finding complex attractors of non-positive systems, such as logical models à la Thomas [27, 29], by enumerating the greatest elements of the TSCCs of their positive boolean semantics, and then looking for attractors of the original system. This approach provides an over-approximation of the attractors and is complementary to recent works which provide lower-bounds on their number [20].

5 Examples

5.1 Influence Model of p53/Mdm2 DNA Damage Repair System [1]

The p53/Mdm2 DNA damage repair system is an interesting oscillatory system which has been first modeled in [8] by a reaction system with differential equations, and then in [1, 2] by simplified influence systems with discrete and differential semantics respectively.

Fig. 1.
figure 1

Left: Influence graph displayed in Fig. 4 of [1], without the activation multi-levels. The dashed influences are those added in our second version of the model. Right: Biocham v4 session for computing the TSCC in both influence systems.

Full size image

We illustrate here the search for TSCCs with two versions of the influence model of [1]. In the first model, we simply transcribe the graph of Fig. 4 of the authors as a boolean influence system. We therefore ignore the multi-level aspect they developed. In the second model, we add some activations on p53 and DNA-damage, and an inhibition on cytoplasmic Mdm2, in order to take into account some basal state of the model. The influence systems and the computed TSCCs are listed in the Biocham session depicted in Fig. 1.

Our algorithm shows that there is in each case a single complex attractor (i.e. not marked as stable or not terminal), accordingly to [1], and four stable steady states in the first case. Note that in [2], this influence model was further extended with differential and stochastic dynamics which could be represented in our setting by influence forces.

5.2 Influence Model of the Mammalian Circadian Clock [9]

A good example of the use of logical models à la Thomas is the recent paper by Comet et al. [9] studying different variants of small models of the circadian rhythms in mammals. A direct import in Biocham v4 of the logical model of Sect. 5 of [9] gives the following influence system with negative sources:

figure i

The positive semantics of this system is close to the original boolean semantics with negation à la Thomas of the model. They both have a single TSCC: the vector (1, 1, 1) that is found by the command list_tscc_candidates as sole candidate. Furthermore, only a few state transitions become reversible in the positive boolean semantics, while they are irreversible in the original boolean semantics with negation à la Thomas of the model, as depicted in Fig. 2.

Fig. 2.
figure 2

State transition graphs of the model under, Left: the boolean semantics with negation à la Thomas, similar to Fig. 7 of [9], Right: the positive boolean semantics, where some state transitions have become reversible.

Full size image

The approximation introduced by the positive boolean semantics can be explained by quantitative dynamics considerations. For instance, when G is on, the transcription leading to the PER-CRY complexes is stimulated, however [9] explains that these complexes can only migrate to the nucleus in absence of light. This absence cannot be checked in a positive semantics model, however the consensus mechanistic process is rather thought to be a modulation of PER transcription by light (see for instance [21] for the mammalian case). Being purely quantitative, it is not easy to take into account such a regulation in a boolean model except with the reversible activation of PC when G is on, whether L is on or not. This is what happens in our positive model as can be seen in the right panel of Fig. 2, and it is similar to what happens for the light in the original model.

The same reasoning explains the reversible inactivation of G when PC is active. Indeed there is a basal synthesis of G that cannot check, in a positive setting, that PC is inactive in order to activate the genes. Once again, the mechanistic process is a quantitative inhibition of the CLOCK-BMAL1 complexes by PER-CRY and a conservative boolean approximation of that process is reflected by the reversible activation of G in presence of PC.

In [9], the authors also restrict the possible behaviours by introducing delays for the boolean transitions which could be considered as a further expansion of the formalism.

6 Discussion

In this paper, we hope to have clarified some differences between influence systems and reaction systems, and especially some subtle discrepancies between the precise boolean semantics that have been considered in the literature. As far as the modeling of one biological system is concerned, the modeler can work with one formalism and one tool to answer the questions about their model. Nevertheless, as soon as different modeling tools are to be used, or the model has to be communicated and reused for another purpose, understanding and mastering these discrepancies in the semantics of the interactions become crucial.

We have shown that, for influence systems and reaction systems with inhibitors, one can obtain a hierarchy of semantics which goes from the concrete stochastic semantics to a discrete Petri net, and then a positive boolean semantics in which the inhibitors of the reactions or influences are just ignored. This is consistent with the fact that the inhibitors decrease the rate or force in the quantitative semantics, but do not really prevent the reaction or influence from proceeding. This convention thus ensures that all discrete behaviours are approximated when we go up in the abstractions of the hierarchy of semantics, and that if a behaviour is not possible in the positive boolean semantics (which can be checked by model-checking methods for instance) it is not possible in the stochastic semantics for any forces. Furthermore, we have shown that in the positive boolean semantics, the monotonicity of the transition relation allows us to enumerate the complex attractors more efficiently by restricting the search to the greatest elements candidates.

On the other hand, the boolean semantics à la Thomas of influence systems, interprets inhibitors as negations, and contains a restriction on the definition of the transition relation by a function, not a relation, which limits the sources of non-determinism. We have shown that the boolean semantics with negation leads to a more expressive formalism in which any unitary boolean transition system can be encoded, but does not correspond to an abstraction of the stochastic semantics, unless the stochastic transitions interprets inhibitors as negative conditions which does not correspond to the differential semantics. With the functional restriction, we have proven that each TSCC in the positive semantics contains at least one TSCC of the semantics à la Thomas, and thus that our algorithm can be used to prune the search space in this setting also.

We have also shown that reaction systems and influence systems have the same expressive power under the differential semantics. This means that, as far as the differential equations are concerned, the details given in the reactant-product structure of a reaction system are not necessary, and that the same differential equations can be derived from an influence system with forces. Several reaction systems can be associated with an influence system with the same differential semantics. This leaves open the design of canonical forms for reaction systems, and computer tools for automatically maintaining the implementation of an influence system by a reaction system.