Comparing Boolean and Piecewise Affine Differential Models for Genetic Networks

Abstract

Multi-level discrete models of genetic networks, or the more general piecewise affine differential models, provide qualitative information on the dynamics of the system, based on a small number of parameters (such as synthesis and degradation rates). Boolean models also provide qualitative information, but are based simply on the structure of interconnections. To explore the relationship between the two formalisms, a piecewise affine differential model and a Boolean model are compared, for the carbon starvation response network in E. coli. The asymptotic dynamics of both models are shown to be quite similar. This study suggests new tools for analysis and reduction of biological networks.

Appendix

1.1 Discrete (multi-level) and Boolean

We now sketch an intuitive algorithm that always provides a biologically feasible model consistent with the multi-level one. Our construction is based on the hypotheses H1 and H2, stated in Sect. 2.1.

Given a discrete model $\Upsigma_d=(\Upomega_d,F_{d})$, with variables V = (V ₁, ..., V _M ) and state space $\Upomega_d=\{0,1,\ldots,d_1\}\times\cdots\times\{0,1,\ldots,d_M\}$ let F _d (V) denote the synchronous successor of V and V[t + 1] = F _d,asyn(V[t]) represent the asynchronous dynamics, where F _d,asyn(V) takes values in the set (Eq. 1).

Assume that each of the M discrete variables has d _m (m = 1, …, M) levels and define: D = (d ₁, …, d _M ), n = d ₁ + ⋯ + d _M and set $\Upomega=\{0,1\}^n$. Then define a function $\varphi_D:\Upomega_d\to\Upomega$, such that:

$$ \varphi_D(V)=(V_{1,1},\ldots,V_{1,d_1},\ldots,V_{M,1},\ldots,V_{M,d_M}), $$

(10)

where V _m,k are defined as in (Eq. 2). It is clear that the function is injective, but $\varphi_D(\Upomega_d)$ is strictly contained in $\Upomega$. Namely, those elements of $\Upomega$ that would satisfy V _m,k < V _m,k+1 for some m and some 1 ≤ k ≤ d _m do not have a pre-image in $\Upomega_d$. In fact, such combinations are biologically meaningless, in view of the interpretation of (Eq. 2). Moreover, when constructing the Boolean rules for the extended system, one naturally wishes to avoid transitions to these unfeasible states, in order to obtain a biologically significant model. Define the sets of permissible and forbidden states of $\Upomega$, associated with D:

$$ \begin{aligned} S_{D,p} &=& \{X\in\Upomega: \ (\forall\ 1\leq m\leq M)(\forall\ 1\leq k\leq d_m),\ X_{m,k}\geq X_{m,k+1} \}\\ S_{D,f} &=&\{X\in\Upomega: \ (\exists\ 1\leq\bar{m}\leq M)(\exists\ 1\leq\bar{k}\leq d_{\bar{m}}),\ X_{\bar{m},\bar{k}}< X_{\bar{m},\bar{k}+1}\}, \end{aligned} $$

where the n coordinates of vector $X\in\Upomega$ are labelled in M groups of length d _m :

$$ X=(X_{1,1},\ldots,X_{1,d_1},\ldots,X_{M,1},\ldots,X_{M,d_M}). $$

(11)

Note that: $S_{D,p} = \varphi_D(\Upomega_d)$ and $S_{D,f} =\Upomega\setminus S_{D,p},$ in view of H2. Then φ _D is a bijection between $\Upomega_d$ and S _D,p, so it is possible to define a (partial) inverse function:

$$ \varphi_{D,p}^{-1}:S_{D,p}\to\Upomega_d, \qquad \varphi_{D,p}^{-1}(X)=(V_1,\ldots,V_M), $$

where $V_m=\sum_{k} X_{m,k}$. An algorithm for generating a Boolean model $\Upsigma_b=(D,\Upomega,F_{b})$ associated to $\Upsigma_d$ is then as follows:

• 1. Generate the state space: $\Upomega=\{0,1\}^n$ with $n=d_1+\cdots+d_M$, and label the coordinates of $X\in\Upomega$ according to (11);

• 2. Translate the discrete value table F _d (V) into a Boolean value table F _b (X), for each X ∈ S _D,p:

  $$ F_{b}(X):=\varphi_D(F_{d}(V)) =\varphi_D(F_{d}(\varphi_{D,p}^{-1}(X))) $$

  (note that this assigns values to X ∈ S _D,p only);

• 3. Complete the table F _b by assigning any function $\psi:\Upomega\to\Upomega$ to the Boolean states X ∈ S _D,f:

  $$ F_{b}(X)= \left\{\begin{array}{lll} \varphi_D(F_{d}(\varphi_{D,p}^{-1}(X))), & X\in S_{D,p}\\ \psi(X), & X\in S_{D,f}; \end{array} \right. $$

• 4. Obtain Boolean logical rules from the (now full) synchronous truth table F _b .

Note that step 3 can be viewed as the identification of a n-dimensional Boolean map, verifying certain constraints (on the set S _D,p) and with some degrees of freedom (on the set S _D,f). Thus the map $F_{b}:\Upomega\to\Upomega$ is not necessarily unique. To construct this map, one can use a reverse engineering algorithm, to find a function $\psi$ according to some suitable criteria (for instance, REVEAL by Liang et al. (1998) will find a function $\psi$ with minimal node connectivity). In any case, the values of F _b (S _D,f) will not affect the dynamics of the biologically relevant part of the Boolean model. Lemma 1 shows that the Boolean model thus obtained is well defined and biologically consistent with the discrete model, in the sense that no forbidden state will be a successor of a permissible state. Forbidden states can succeed one another or go into a permissible state. (Grey rows in Table 3).

Table 3 Multi-level model and Boolean rules for cya (Y) (synchronous maps F _d and F _b )

For the Boolean model $\Upsigma_b=(D,\Upomega,F_{b})$, one can also define an asynchronous dynamics from F _b , by updating only one Boolean variable at a time, $X[t+1] =F_{b,asyn}(X[t])$. Note that synchronous and asynchronous dynamics have the same equilibrium points: X ⁺ = F _b (X) = X implies X[t + 1] = X[t] for all t.

Lemma 1

Suppose$\Upsigma_d$is a multi-level system that satisfies H1. The Boolean system$\Upsigma_b=(D,\Upomega,F_{b})$, constructed according to H2 and points 1 to 3, allows only transitions fromS_D,porS_D,fintoS_D,por fromS_D,finto itself (for both synchronous and asynchronous updating strategies).

Proof

Given any X ∈ S _D,p, we want to show that $X^+=F_{b}(X)\in S_{D,p}$. By definition of F _b , $\varphi_D$ and $\varphi_{D,p}^{-1}$ we have:

$$ F_{b}(X)=\varphi_D(F_{d}(\varphi_{D,p}^{-1}(X)))=\varphi_D(F_{d}(V))=\varphi_D(V^+), $$

for some $V\in\Upomega_d$. By assumption H2, it follows that φ _D (V ⁺) ∈ S _D,p.

The forbidden states can remain in S _D,f or switch to S _D,p since, given any X ∈ S _D,f, we have X ⁺ = F _b (X) = ψ(X) and $\psi(X)\in\Upomega=S_{D,p}\cup S_{D,f}.$ To see that the asynchronous updating strategy also prevents transitions from S _D,p to S _D,f, consider X ∈ S _D,p and any asynchronous transition, Y = F _b,asyn(X). If X is an equilibrium point then immediately Y = X ∈ S _D,p. Otherwise, since X is of the form (10), it can be written as: $X=({\bf 1}_{ p_1},{\bf 0}_{d_1-p_1};\ldots;{\bf 1}_{p_M},{\bf 0}_{d_M-p_M}),$ where ${\bf 1}_{p}$ (resp., ${\bf 0}_{p}$) is a vector of length p with all coordinates equal to 1 (resp., 0). Its synchronous successor is $X^+=({\bf 1}_{p^+_1},{\bf 0}_{d_1-p^+_1};\ldots;{\bf 1}_{p^+_M},{\bf 0}_{d_M-p^+_M}),$ where $p^+_i\in\{p_i-1,p_i,p_i+1\},\;{\rm for \; all}\;i=1,\ldots,M$. Since X is not an equilibrium point, then there exists k ∈ {1,d _M } such that $p_k^+\neq p_k$. In any asynchronous successor, only one p _i can change at a time. Therefore, there exists exactly one index 1 ≤ k ≤ M such that $p^+_k=p_k\pm1$: $Y=({\bf 1}_{p_1},{\bf 0}_{d_1-p_1};\ldots;{\bf 1}_{p^+_k}, {\bf 0}_{d_1-p^+_k};\ldots;{\bf 1}_{p_M},{\bf 0}_{d_M-p_M}).$ Therefore, it is clear that Y ∈ S _D,p. $\square$

1.2 Multi-level and Boolean state transition tables for cya

To illustrate the construction of the Boolean rules from the piecewise affine model, we now give the complete tables for the variable cya. The rules for the other variables can be similarly obtained (the full tables can be found in the Supplementary Material). The left panel in Table 3 shows the multi-level model rules for cya, in the cases U = 0 or U = 1. The columns C and Y contain the multi-level states corresponding to the (continuous) variables x _c and x _y , obtained by application of (Eq. 3). The column Y ⁺ shows the synchronous state transition, computed according to (Eq. 4). Columns $Y_1^+$ and $Y_2^+$ depict the states of the Boolean variables corresponding to Y ⁺, computed according to hypotheses H1 and H2.

The right panel in Table 3 shows the Boolean variables corresponding to C and Y in the first four columns, and the synchronous Boolean updates in the columns $Y_1^+$ and $Y_2^+$. As explained in the text, there are Boolean state combinations which have no biological meaning: these are the rows highlighted in grey and represent the forbidden states in S _D,f. The corresponding entries in columns $Y_1^+$ and $Y_2^+$ are filled following points 1 to 3, in Appendix 1. Therefore, according to Lemma 1, there are no transitions to forbidden states.

The Boolean rules for cya can be now read from the columns C _i , Y _i , and $Y_i^+$:

$$ \begin{aligned} Y_1^+ &=& 1\\ Y_2^+ &=& (\overline{U} \wedge Y_1) \vee (U \wedge [(Y_1 \wedge(\overline{C_1}\vee\overline{C_2})) \vee ((Y_1\wedge\overline{Y_2})\wedge C_1 \wedge C_2) ]) \end{aligned} $$