betaFeedback

WorksAgricultural and Biological Sciences

On Hybrid Gene Regulatory Networks

Abstract

In this work, we study a class of hybrid dynamical systems called hybrid gene regulatory networks (HGRNs) which was proposed to model gene regulatory networks. In HGRNs, there exist well-behaved trajectories that reach a fixed point or converge to a limit cycle, as well as chaotic trajectories that behave non-periodic or indeterministic. In our work, we investigate these irregular behaviors of HGRNs and present theoretical results about the decidability of the reachability problem, the probability of indeterministic behavior of HGRNs, and chaos especially in 2-dimensional HGRNs.

Adrian Wurm and Honglu Sun

BTU Cottbus-Senftenberg, Lehrstuhl Theoretische Informatik, Platz der Deutschen Einheit 1, 03046 Cottbus, Germany, https://www.b-tu.de/ [email protected]

Nantes Université, École Centrale Nantes, CNRS, LS2N, UMR 6004, F-44000 Nantes, France

Introduction

Hybrid systems are dynamical systems that admit both continuous and discrete behavior. They were initially proposed to model the interactions between the discrete digital world and the continuous physical world [2]. In recent years, hybrid systems were also used in system biology to study biological networks [8, 10, 11].

In this work, we study a class of hybrid systems called hybrid gene regulatory networks (HGRN) [7, 9], which is an extension of Thomas’ discrete modeling framework [19, 20]. These hybrid systems were proposed to model gene regulatory networks, a framework to describe the regulation influences between genes.

Two widely used formalisms to study gene regulatory networks are discrete models (like Boolean networks [14]) and continuous models (differential equations [1, 6] and stochastic models [13]). The major advantage of HGRNs compared to discrete models is that they can provide and process temporal information of the systems. Compared to purely continuous models, the dynamical properties of HGRNs are easier to analyze, which makes them a more reasonable choice to apply on large and complex instances.

HGRNs are similar to piecewise-constant derivative systems (PCD systems) [4] which are a special case of hybrid automata [3]. The major difference between HGRNs and PCD systems, as for example in [4, 5, 17], is the existence of sliding modes, which means that when a trajectory reaches a black wall (a boundary of the discrete state which can be reached but cannot be crossed by trajectories), the trajectory does not end there but is instead forced to move along this black wall. There exist other methods to define the behavior of trajectories on a black wall [12, 16] which are different from the sliding modes in HGRNs.

One important research topic of dynamical models of gene regulatory networks is how to analyze the reachability of states, for instance, whether a trajectory starting in a certain state can reach another given state. These questions arise in cell reprogramming [15]. In [18], the reachability problem of HGRNs is investigated and methods are proposed to analyze the reachability of regular trajectories, meaning those that reach a fixed point or converge to a limit cycle.

In HGRNs however, there also exists so-called chaotic trajectories that cross an infinite sequence of discrete regions so that this sequence does not end up in a cycle. For now, our understanding of this irregular behaviour is quite limited. Further understanding of these trajectories can potentially lead to the development of new methods to analyze the reachability problem for them. In this work, we want to fill the gaps in this research field by investigating irregular behavior occuring in HGRNs. Our major contributions are:

  • We prove that the reachability problem for HGRNs is undecidable and that this enforces the existence of chaotic trajectories.

  • We prove that under reasonable conditions, the probability for a random trajectory to admit indeterminism tends to 1 as the dimension of the system tends to infinity.

  • We argue that in two-dimensional HGRNs, chaos is not possible without indeterminism, and conclude that the probability for a random two-dimensional HGRN to admit chaos with indeterminism is 0.

The paper is organized as follows: In § 2 we collect basic notions and recall the definition of HGRNs as well as their properties. In § 3 we prove that HGRNs are Turing-powerful and conclude that chaotic trajectories must exist. In § 4 we give some structural results on indeterminism and provide conditions as well as probability estimations for the bifurcation of trajectories. The paper ends with some open questions.

Preliminaries and Network Reachability Problems

We start by defining the problems we are interested in; here, we follow the definitions and notions of [18] for everything related to hybrid gene regulatory networks.

Intuitively, a HGRN is a an NN-dimensional rectangular cuboid/hyperrectangle with integer edge lengths decomposed into hypercubes with unit edge length. Each such hypercube dd is called a discrete state and is associated with a celerity cdc_d enforcing the direction in which a trajectory is allowed to move inside dd, so a trajectory may only change its direction in the moment of transition between two discrete states.

Definition 1 (Hybrid gene regulatory network (HGRN)). Let N∈NN \in\mathbb{N} and let ni∈Nn_i \in\mathbb{N} for each i∈{1,…,N}i \in\{1,\ldots,N\}. A hybrid gene regulatory network (HGRN) on NN genes with nin_i levels is a pair H=(E,c)\mathcal{H} = (E,c), where

E:={d∈NN∣∀i∈{1,2,…,N}:0≤di≤ni}E := \left\{d \in\mathbb{N}^{N} \mid\forall i \in\{1,2,\ldots,N\}: 0 \leq d_i \leq n_i\right\}

is called the set of discrete states, and c:E→RNc:E \to\mathbb{R}^{N} is called the celerity function.

Definition 2 (Hybrid state of HGRN). A hybrid state of a HGRN is a pair h=(π,d)h=(\pi,d) containing a fractional part π∈[0,1]N\pi\in[0,1]^N, and a discrete state d∈Ed \in E. EhE_h is the set of all hybrid states and EshE_{sh} is the set of all finite or infinite sequences of hybrid states:

Esh={(h0,h1,…,hm)∈(Eh)m+1∣m∈N∪{∞}}.E_{sh}=\left\{(h_0,h_1,\ldots,h_m)\in(E_h)^{m+1}\mid m\in\mathbb{N}\cup\{\infty\}\right\}.

Note that Eh=:Eh1⊆EshE_h=:E_h^1\subseteq E_{sh}.

Definition 3 (Boundary). A boundary of a discrete state dd is a set of hybrid states defined by e(i,π0,d):={(π,d)∈Eh∣πi=π0}e(i,\pi_0,d):=\{(\pi,d)\in E_h\mid\pi^i=\pi_0\}, where i∈{1,2,…,N}i\in\{1,2,\ldots,N\} and π0∈{0,1}\pi_0\in\{0,1\}.

Definition 4 (Hybrid trajectory). Let t0∈R+∪{∞}t_0\in\mathbb{R}^{+}\cup\{\infty\} and [0,t0][0,t_0] a time interval. For a function τ:[0,t0]→Esh\tau:[0,t_0]\to E_{sh}, we denote by abuse of notation by π:[0,t0]→Esh\pi:[0,t_0]\to E_{sh} the projection of τ\tau on the second component.

For τ(t)=h\tau(t)=h, we denote by dτ(t+)dt:=dπ(t+)dt\frac{d\tau(t^+)}{dt}:=\frac{d\pi(t^+)}{dt} the temporal derivative of the fractional part of τ\tau, dτ(t−)dt\frac{d\tau(t^-)}{dt} and dτ(t)dt\frac{d\tau(t)}{dt} are defined analogous.

We call τ\tau a hybrid trajectory, if for every time t∈[0,t0]t\in[0,t_0] with τ(t)=h\tau(t)=h and h=(h0,…,hm)∈Ehm+1h=(h_0,\ldots,h_m)\in E_h^{m+1} a sequence of m+1m+1 hybrid states hj=(πj,dj)h_j=(\pi_j,d_j), the following conditions are satisfied:

  • For t=0t=0 we have m=0m=0, and τ(0)∈Eh\tau(0)\in E_h is not on any boundary.

  • If h0h_0 does not belong to any boundary, then m=0m=0 and dτ(t)dt=c(d0)\frac{d\tau(t)}{dt}=c(d_0) for t>0t>0 and dτ(t+)dt=c(d0)\frac{d\tau(t^+)}{dt}=c(d_0) for t=0t=0.

  • If h0h_0 only belongs to one boundary ee, let ee be the upper boundary in the ithi^{\text{th}} dimension (the following is analogous when ee is the lower boundary). In case d0id_0^i is not the maximal discrete level of gene ii, let the discrete state on the other side of ee be noted as drd_r, where d0k=drkd_0^k=d_r^k for all k≠ik\ne i, and d0i+1=drid_0^i+1=d_r^i. There are four possible cases:

    • If c(d0)i=0c(d_0)^i=0, then m=0m=0 and the trajectory from the current state will slide along the boundary ee with speed dτ(t+)dt=dτ(t−)dt=c0\frac{d\tau(t^+)}{dt}=\frac{d\tau(t^-)}{dt}=c_0, which is then called a neutral boundary of d0d_0.

    • If c(d0)i>0c(d_0)^i>0, and either d0id_0^i is the maximal discrete level of the ithi^{\text{th}} gene, or d0id_0^i is not the maximal discrete level of the ithi^{\text{th}} gene but the ithi^{\text{th}} component of c(dr)c(d_r) is negative, then m=0m=0 and the trajectory from the current state will slide along the boundary ee, which is called an attractive boundary of d0d_0. We then have that dτ(t)kdt=c(d0)k\frac{d\tau(t)^k}{dt}=c(d_0)^k for all k≠ik\ne i, dτ(t+)dt=0\frac{d\tau(t^+)}{dt}=0 and dτ(t−)dt∈{0,c(d0)i}\frac{d\tau(t^-)}{dt}\in\{0,c(d_0)^i\}.

  • If c(d0)i>0c(d_0)^i > 0, d0id_0^i is not the maximal discrete level of the ithi^{\mathrm{th}} gene, and the ithi^{\mathrm{th}} component of crc_r is positive, then the trajectory from the current state instantly crosses the boundary ee and enter the discrete state drd_r. We then have m=1m=1 and τ(t)=((π0,d0),(π1,d1))\tau(t)=((\pi_0,d_0),(\pi_1,d_1)), where d1=drd_1=d_r, π0j=π1j\pi_0^j=\pi_1^j for all if j≠ij\ne i, and π1i=0\pi_1^i=0. Such a boundary is called an output boundary and the counterpart of d0d_0 is called an input boundary of drd_r. We then demand that dτ(t+)dt=c(dr)\frac{d\tau(t^+)}{dt}=c(d_r) and dτ(t−)dt=c(d0)\frac{d\tau(t^-)}{dt}=c(d_0).

  • If hh belongs to several boundaries, then the previous cases can be mixed:

    • If in these boundaries there is no output boundary, then the trajectory from the current state will exit all input boundaries and slide along all attractive or neutral boundaries.

    • If in these boundaries there is only one output boundary, then the trajectory from the current state will cross this output boundary.

    • If in these boundaries there are several output boundaries, then the trajectory from the current state can cross any of them, but can only cross one boundary at one time, which causes indeterministic behavior.

A hybrid trajectory τ\tau is called

  • finite, if t0≠∞t_0\ne\infty and the sequence of states that are reached is finite,

  • periodic, if it is defined on t0=∞t_0=\infty and ∃T,t1>0,∀t∈[t1,∞[,τ(t)=τ(t+T)\exists T,t_1>0,\forall t\in[t_1,\infty[,\tau(t)=\tau(t+T),

  • chaotic, if the sequence of discrete states that it passes is infinite and non-periodic, meaning it does not end up in a cycle and

  • regular, if it is not chaotic.

Definition 5 (Reachability Problem). The reachability problem for HGRNs is the following: Given a HGRN and two sets S,TS,T of hybrid states in form of linear inequalities, the question is whether there exists a trajectory τ\tau starting in a hybrid state s∈Ss\in S and reaching at some time tt a state f∈Ff\in F, meaning

∃τ∃s∈S,f∈F,t>0:τ(0)=s∧τ(t)=f.\exists\tau\exists s\in S,f\in F,t>0:\tau(0)=s\land\tau(t)=f.

If such a trajectory exists, we say that FF is reachable from TT.

Note the special cases that S,TS,T might contain only one hybrid state or that they may be a whole discrete state. It was shown in [18] that the reachability problem is decidable for regular trajectories.

Definition 6 (Area of attraction). Consider a subset AA of hybrid states of a HGRN. The area of attraction φ(A)\varphi(A) is the set of all hybrid states with the property that every trajectory starting in them will eventually intersect AA. The extended area of attraction Φ(A)\Phi(A) is the set of all hybrid states with the property that there exists a trajectory starting in them that will at some point intersect AA.

Example 1. Figure 1 is a sketch of a HGRN on three genes with levels n1=2,n2=4,n3=2n_1=2,n_2=4,n_3=2, the arrows indicate the velocities where an encircled circle indicates an upward movement and an encircled X a downward movement, missing arrows indicate that the velocity is the zero-vector. The left side of the figure illustrates level 1 of gene 3, the right side level 2.

Figure 1. Binary expansion

The network computes the binary expansion of a number in [0,1][0,1] in the following way: If a trajectory passes A=e(2,1,(1,2,1))A=e(2,1,(1,2,1)) (blue area), interpret its distance to the rightmost part A∩BA\cap B, B=e(1,1,(1,2,1))B=e(1,1,(1,2,1)) as its current value xx. If x<12x<\frac{1}{2}, the trajectory will enter the small circle of discrete states (1,2,1),(2,2,1),(2,1,1)(1,2,1),(2,2,1),(2,1,1) and (1,1,1)(1,1,1) and finally end up in AA again with value 2x2x. If x>12x>\frac{1}{2}, it will pass the big circle of discrete states (1,2,1)(1,2,1) (where 12\frac{1}{2} is subtracted from the value), (1,3,1),(1,3,2),(1,4,2)(1,3,1),(1,3,2),(1,4,2) (where its value is multiplied with two), (2,4,2),(2,3,2),(2,2,2),(2,1,1)(2,4,2),(2,3,2),(2,2,2),(2,1,1) and (1,1,1)(1,1,1) and again reach AA, this time with value 2(x−12)2(x-\frac{1}{2}). If one follows the trajectory and interprets the first case as 0 and the second case as 1, one obtains the binary expansion of the initial xx.

If for example we start in a=((316,316),(1,1,1))a=((\frac{3}{16},\frac{3}{16}),(1,1,1)), we obtain the trajectory drawn in red. It passes AA at value 38\frac{3}{8}, so it runs through the small circle and enters AA again at value 34\frac{3}{4}, therefore entering the big circle ending up in AA again at value 12\frac{1}{2}. So far, we obtained the binary expansion 0.01, but now the trajectory becomes indeterministic because the celerities allow a bifurcation at ((1,1),(1,2,1))((1,1),(1,2,1)). This corresponds to the fact that 38\frac{3}{8} has the two binary expansions 0.011 and 0.010\overline{1}$.

Observe that we obtain a periodic trajectory for every rational value xx and a chaotic trajectory for xx irrational.

Turing completeness and chaos

Turing-completeness was already shown for PCD systems in [4], a model related to HGRNs. We would now like to prove it for HGRNs, for they are more restrictive in the sense that they only allow a change of derivatives at integer coordinate changes and admit indeterminism with positive probability.

Theorem 1. HGRNsHGRNs are Turing powerful.

Proof. Let M=(Q,Σ,Γ,δ,q1,□,F)M = (Q, \Sigma, \Gamma, \delta, q_1, \square, F) be a deterministic Turing-Machine starting on an empty tape, Q={q1,…,qn}Q = \{q_1, \ldots, q_n\}, F={qn}F = \{q_n\}. Assume that all symbols are encoded in binary, so Σ=Γ={0,1}\Sigma= \Gamma= \{0,1\} and that the encoding of □\square consists only of zeroes. Also assume that for each two states qiq_i and qjq_j there are transitions in only one direction, either qi→qjq_i \to q_j or qj→qiq_j \to q_i but not both, a property that can be guaranteed by introducing auxiliary states. We construct an equivalent HGRN HH with the following genes:

  • One with two discrete levels storing the current value called GcG_c

  • Gℓ,1G_{\ell,1} with three discrete levels and Gℓ,2G_{\ell,2} with two discrete levels for the tape values left of the head, where the current value is stored as the binary expansion with the most significant bits corresponding to the values closest to the head in the fractional part of the upmost discrete state of Gℓ,1G_{\ell,1}.

  • Gr,1G_{r,1} and Gr,2G_{r,2} analogous for the tape values right of the head.

  • One called GiG_i for every qi∈Qq_i \in Q with two discrete levels each.

  • Two called GαG_\alpha and GβG_\beta with two discrete levels each, keeping track of the current calculation step as in Figure 2.

The whole network is therefore of shape [0,2]×[[0,3]×[0,2]]2×[0,2]n×[0,2]2[0,2] \times[[0,3] \times[0,2]]^2 \times[0,2]^n \times[0,2]^2 and our trajectory starts in ((0,0),[(2,0),(0,0)]2,(1,1),[(0,0)]n−1,(0,1),(0,0))((0,0),[(2,0),(0,0)]^2,(1,1),[(0,0)]^{n-1},(0,1),(0,0)).

Let (qi,a)→(qj,b,d)(q_i,a) \to(q_j,b,d) be a transition in δ\delta, without loss of generality d=rd=r stating that the head moves to the right (d=ℓd=\ell is analogous and d=nd=n is easily derived). We choose the celerities as follows:

Figure 2. Calculation step accounting

In the first calculation step α=β=0\alpha= \beta= 0 we put qjq_j into the upmost position. Note that we do not loose the information on which state we started in because we assumed that there is no transition from qjq_j to qiq_i.

The celerities describing how to update the left side tape start with making the bits less significant by one position because the head recedes by one position, which corresponds to dividing the numerical value of Gℓ,1G_{\ell,1} by two, see Figure 3, left. This is done in the first calculation step α=β=0\alpha= \beta= 0 along with adding half of bb to it, see Figure 3, middle, because bb is on the position left of the head after that transition. In the second calculation step α=0\alpha= 0, β=1\beta= 1, this value is then copied back from Gℓ,2G_{\ell,2} to the original position, see Figure 3, right, Gℓ,1G_{\ell,1}, both Gℓ,1G_{\ell,1} and Gℓ,2G_{\ell,2} remain inactive for the last two steps.

Figure 3. Left side tape update

The celerities describing how to update the right side tape work similar. We start by multiplying the value by two, see Figure 4 left, because each bit now becomes more significant by one position. This is done in the first calculation step α=β=0\alpha= \beta= 0, where we also catch the trajectory on the border between Gr,1=1G_{r,1} = 1 and Gr,1=2G_{r,1} = 2 if it is in Gr,2=1G_{r,2} = 1 and let it pass until the lower boundary of Gr,1=1G_{r,1} = 1 if Gr,1=2G_{r,1} = 2, in order to keep track of what our new current value GcG_c will be in the next Turing step.

Figure 4. Right side tape update

Note that if the initial value was 12\frac{1}{2}, we have an indeterminism when hitting the lower boundary of Gr,1=3G_{r,1} = 3 and the upper boundary of Gr,2=1G_{r,2} = 1. In the second calculation step α=0\alpha= 0, β=1\beta= 1, we therefore adjust the celerities to make sure that we end in Gr,2=2G_{r,2} = 2 whenever the initial value was greater than or equal 12\frac{1}{2}, see Figure 4 middle (the case that all positions on the right side tape are 1’s is not possible).

In the third and fourth calculation step α=1\alpha= 1, β=1\beta= 1 and α=1\alpha= 1, β=0\beta= 0, we pop the most significant bit of the right side tape to be the new GcG_c, which means that if the value of Gr,1G_{r,1} is greater than 1 we subtract 1 from Gr,1G_{r,1} and add move GcG_c to the upmost position, otherwise to the lowest, see Figure 4 right.

Note that we loose the information on whether we moved left or right, so we actually have the celerities of the fourth step on the right side of the tape for the left side of the tape as well. However, the left side is not effected by that because it stays in Gℓ,2=3G_{\ell,2}=3 from the end of step two on and therefore never enters a hypercube with non-zero celerities induced be the update of GcG_c.

In the fourth step we also bring GiG_i to the lowest possible point. By assumption of anti-symmetry, ii can still be distinguished from jj at that point without the knowledge of dd.

Corollary 1. The reachability problem for HGRNs is undecidable.

Proof. The halting problem can be reformulated as the reachability problem of state qnq_n.

Note that the trajectories that are obtained by the Turing machines that behave chaotic automatically lead to chaotic trajectories, for the sequence of reached states cannot have a repeating pattern.

Indeterminism

Most attempts to solve verification tasks such as the reachability problem become a lot more difficult as soon as trajectories are not regular any more. It is therefore desirable to estimate how likely a trajectory is to be chaotic or indeterministic.

Example 2. In opposition to what is claimed in [18], indeterminism will happen with non-zero probability in networks with at least 3 genes having at least two discrete levels each when all celerities and the starting point are chosen uniformly random in (0,1)(0,1). Figure 5 is a sketch of a HGRN with 3 Genes G1G_1, G2G_2 and G3G_3 with two levels 0 and 1 each that allows the indeterministic red trajectory starting in point aa in (0,0,0)(0,0,0).

Figure 5. Indeterminism with positive probability

The trajectory reaches the attractive boundary to discrete state 1 of G1G_1, slides along until it reaches the attractive boundary to discrete state 1 of G2G_2 and slides "upwards" along this intersection of discrete domains until it reaches the hybrid state ((1,1,1),(0,0,0))((1,1,1),(0,0,0)). The border to the discrete state 1 of G3G_3 is an output boundary, so it is crossed and the hybrid state ((1,1,0),(0,0,1))((1,1,0),(0,0,1)) is immediately reached. Now the boundaries to the discrete levels 1 of G1G_1 and G2G_2 both are output boundaries, so the trajectory may pass any of them, leading to indeterminism. Note that we did not rely on probability-zero-events; The probability of the celerity in the first hypercube to point into the middle in all three dimensions is (12)3(\frac{1}{2})^3, the first two reached boundaries are then attractive with probability 12\frac{1}{2} each as well as the third one being an output boundary and the two new boundaries after the crossing are output boundaries with probability 14\frac{1}{4} each. The accumulated probability is then 18⋅(12)2⋅12⋅142=(12)10\frac{1}{8}\cdot(\frac{1}{2})^2\cdot\frac{1}{2}\cdot\frac{1}{4}^2=(\frac{1}{2})^{10}. This probability significantly rises once we increase the size of the network, meaning the number of genes as well as their dimensions.

We can be more general:

Theorem 2. Let all celerities of a HGRN with nn genes and at least two discrete levels per gene as well as the starting point of a trajectory be randomly chosen by the uniform distribution in [0,1]n[0,1]^n. Then the probability for this trajectory to lead to indeterminism tends to 11 as nn tends to ∞\infty.

Proof. First, note that for each gene we have that an inner boundary is reached at some point with probability at least 12\frac{1}{2}. These events are independent, so it follows by the central limit theorem that the probability of at least one fourth of all genes reaching an inner boundary tends to 11. Each of these n4\frac{n}{4} boundaries is attractive with probability 12\frac{1}{2}, if we group them into n12\frac{n}{12} triples of boundaries, each triple starts with two attractive boundaries followed by an output boundary with probability 18\frac{1}{8} as in Example 2. The probability that after the crossing of such a third boundary, the two other boundaries become output boundaries is (12)2(\frac{1}{2})^2 each, so the accumulated probability for each triple to lead to indeterminism is at least 18⋅(12)2⋅(12)2=(12)7\frac{1}{8}\cdot(\frac{1}{2})^2\cdot(\frac{1}{2})^2=(\frac{1}{2})^7. The probability that none of the n12\frac{n}{12} triples leads to indeterminism is therefore at most (27−127)n12⟶n→∞0\left(\frac{2^7-1}{2^7}\right)^{\frac{n}{12}}\underset{n\to\infty}{\longrightarrow}0. ■

Note that Example 2 relied on the third dimension, for hitting two edges at the same time without sliding before is highly unlikely:

Theorem 3. Random HGRNs in two dimensions admit chaos only with probability 00.

Proof. Since a trajectory cannot cross itself, it is obvious that chaos can only be obtained by bifurcation.

A trajectory starts in the inner of a hypercube with probability 11. In order to bifurcate, it needs to reach two output boundaries at the same time, meaning it has to hit one of finitely many points. Reaching such an intersection point qq by sliding towards it along an attractive boundary will not lead to indeterminism at qq because the boundary which one is sliding along is not an output boundary. A point pp in a two-dimensional HGRN that has an area of attraction with non-zero measure must either have integer coordinates connected to an attractive boundary or be reachable from such a point, which is a zero-set.

The area of attraction of a point that admits two output boundaries is therefore one-dimensional with probability 11, meaning it is a zero-set. ■

Note that an indeterministic network such as in Example 2 inherently enables chaotic trajectories if both choices lead back into the area of attraction of the point aa at which the path was bifurcating, therefore forming two cycles T1,T2T_1,T_2 with the same starting point aa.

The idea is sketched in Figure 6 for two dimensions. Take an irrational number, for example π\pi, and when reaching aa for the nn-th time, follow the cycle TiT_i iff the nn-th position in the binary expansion of π\pi is ii. The picture shows indeterministic behavior in two dimensions, which only happens with probability zero, it is however obvious that this construction can be lifted into three dimensions using Example 2 as a gadget to obtain a similar chaotic path with positive probability.

Figure 6. Guaranteed indeterminism with positive probability

Figure 6 is also an example for a two-dimensional HGRN that leads to indeterminism independent by the starting point of the trajectory, and therefore to chaos, because every possible trajectory in N\mathcal{N} will at some point pass aa, meaning φ(a)=Φ(a)=N\varphi(a)=\Phi(a)=\mathcal{N}.

This kind of chaos differs from the chaos that makes HGRNs Turing-complete. It depends on the choices made on the way rather than the restrictions of the network, and another trajectory starting in the same point might be periodic. To examine more precisely how the reachability problem and the identification of chaos relate to those, from now on we call a chaotic path that reaches a certain point an infinite number of times recurrent, and otherwise say that its chaos is proper.

The proof of Theorem 1 relies on proper chaos, so reachability could still be decidable in recurrent chaos.

The following is a direct consequence of [4]:

Lemma 1. A two-dimensional HGRN never admits proper chaos.

We now want to define a property that most HGRNs of natural origin share:

Definition 7. For a HGRN N\mathcal{N} with two discrete levels for every gene and H=(V,E,ρ)H=(V,E,\rho) a complete weighted directed graph with V={1,…,N}V=\{1,\ldots,N\} the genes of N\mathcal{N} and ρ:E→Q\rho:E\to\mathbb{Q}, we say that N\mathcal{N} is induced by GG, iff for every α∈{0,1}N\alpha\in\{0,1\}^{N} we

have that celerities are the weighted sums over the incoming edges

c(α)j=∑i=1αi=1Nρ(i,j)−∑i=1αi=0Nρ(i,j)c(\alpha)_j = \sum_{\substack{i=1\\\alpha_i=1}}^{N} \rho(i,j) - \sum_{\substack{i=1\\\alpha_i=0}}^{N} \rho(i,j)

We call HH the influence graph of N\mathcal{N}.

We want to pose the question whether our problems become easier when inducedness is given. Note that induced HGRNs form a zero-set among all possible HGRNs.

Theorem 4. It can be decided whether a HGRN is induced or not in P. Moreover, the influence graph is unique and can be computed in polynomial time.

Proof. When given all celerity vectors, the decisional as well as the computational problem are linear equation systems on rational domains and therefore solved efficiently. It remains to show that there can only be one solution. Suppose there were two graphs H1H_1 and H2H_2 inducing the same HGRN, then for all dimensions i,j∈{1,…,n}i,j \in\{1,\ldots,n\} we have that

ρ1(i,j)=c([0]i−1,1,[0]n−i)j−c(0,…,0)j2=ρ2(i,j)\rho_1(i,j) = \frac{c([0]^{i-1},1,[0]^{n-i})_j-c(0,\ldots,0)_j}{2} = \rho_2(i,j)

which gives us uniqueness.

The constellation in Example 2 can be obtained by an induced HGRN with positive probability, for example by

Figure 7 (PDF p. 11).

Conclusion and Further Questions

We examined the reachability problem for HGRNs and showed in what way the size and dimension of the net influence chaos and indeterminism.

Further open questions are:

  1. Are induced HGRNs still Turing-powerful?

  2. Does Theorem 2 still hold for induced HGRNs?

3.) For HNH_{\mathcal{N}} the set of all possible trajectories in N\mathcal{N}, how do the sets Rt:={h(t)∣h∈HN}R_t := \{h(t) \mid h \in H_{\mathcal{N}}\} behave for large tt? With what probability and how fast do they approach a zero-set?

4.) Can these sets RtR_t be computed efficiently?

5.) Can HGRNs be expressed by induced HGRNs with the help of auxiliary dimensions?

Acknowledgment: We want to thank Klaus Meer for helpful discussion.

References

  1. [1]Sofia Almeida, Madalena Chaves, and Franck Delaunay. Control of synchronization ratios in clock/cell cycle coupling by growth factors and glucocorticoids. Royal Society Open Science, 7(2):192054, 2020.DOI
  2. [2]Rajeev Alur, Costas Courcoubetis, Thomas A Henzinger, and Pei-Hsin Ho. Hybrid automata: An algorithmic approach to the specification and verification of hybrid systems. In International Hybrid Systems Workshop, pages 209–229. Springer, 1991.
  3. [3]Rajeev Alur, Costas Courcoubetis, Thomas A Henzinger, and Pei-Hsin Ho. Hybrid automata: An algorithmic approach to the specification and verification of hybrid systems. Technical report, Cornell University, 1993.
  4. [4]Eugene Asarin, Oded Maler, and Amir Pnueli. Reachability analysis of dynamical systems having piecewise-constant derivatives. Theoretical Computer Science, 138(1):35–65, 1995.
  5. [5]Eugene Asarin, Venkatesh P Mysore, Amir Pnueli, and Gerardo Schneider. Low dimensional hybrid systems–decidable, undecidable, don’t know. Information and Computation, 211:138–159, 2012.
  6. [6]Debashis Barik, William T Baumann, Mark R Paul, Bela Novak, and John J Tyson. A model of yeast cell-cycle regulation based on multisite phosphorylation. Molecular systems biology, 6(1):405, 2010.DOI
  7. [7]Jonathan Behaegel, Jean-Paul Comet, Gilles Bernot, Emilien Cornillon, and Franck Delaunay. A hybrid model of cell cycle in mammals. Journal of bioinformatics and computational biology, 14(01):164001, 2016.DOI
  8. [8]Madalena Chaves and Miguel Preto. Hierarchy of models: From qualitative to quantitative analysis of circadian rhythms in cyanobacteria. Chaos: An Interdisciplinary Journal of Nonlinear Science, 23(2):025113, 2013.DOI
  9. [9]Emilien Cornillon, Jean-Paul Comet, Gilles Bernot, and Gilles Enée. Hybrid gene networks: a new framework and a software environment. advances in Systems and Synthetic Biology, 2016.
  10. [10]Etienne Farcot and Jean-Luc Gouzé. Periodic solutions of piecewise affine gene network models with non uniform decay rates: the case of a negative feedback loop. Acta Biotheoretica, 57(4):429–455, 2009.DOI
  11. [11]Elena Firippi and Madalena Chaves. Topology-induced dynamics in a network of synthetic oscillators with piecewise affine approximation. Chaos: An Interdisciplinary Journal of Nonlinear Science, 30(11):113128, 2020.DOI
  12. [12]Jean-Luc Gouzé and Tewfik Sari. A class of piecewise linear differential equations arising in biological models. Dynamical systems, 17(4):299–316, 2002.
  13. [13]Guy Karlebach and Ron Shamir. Modelling and analysis of gene regulatory networks. Nature reviews Molecular cell biology, 9(10):770–780, 2008.DOI
  14. [14]Stuart A Kauffman. Metabolic stability and epigenesis in randomly constructed genetic nets. Journal of theoretical biology, 22(3):437–467, 1969.pubmed.ncbi.nlm.nih.gov/5803332
  15. [15]Hugues Mandon, Cui Su, Stefan Haar, Jun Pang, and Loïc Paulevé. Sequential reprogramming of boolean networks made practical. In Computational Methods in Systems Biology: 17th International Conference, CMSB 2019, Trieste, Italy, September 18–20, 2019, Proceedings 17, pages 3–19. Springer, 2019.DOI
  16. [16]Erik Plahte and Sissel Kjøglum. Analysis and generic properties of gene regulatory networks with graded response functions. Physica D: Nonlinear Phenomena, 201(1-2):150–176, 2005.DOI
  17. [17]Andrei Sandler and Olga Tveretina. Deciding reachability for piecewise constant derivative systems on orientable manifolds. In Reachability Problems: 13th International Conference, RP 2019, Brussels, Belgium, September 11–13, 2019, Proceedings 13, pages 178–192. Springer, 2019.DOI
  18. [18]Honglu Sun, Maxime Folschette, and Morgan Magnin. Reachability analysis of a class of hybrid gene regulatory networks. In International Conference on Reachability Problems, pages 56–69. Springer, 2023.DOI
  19. [19]René Thomas. Boolean formalization of genetic control circuits. Journal of theoretical biology, 42(3):563–585, 1973.
  20. [20]René Thomas. Regulatory networks seen as asynchronous automata: a logical description. Journal of theoretical biology, 153(1):1–23, 1991.DOI

Paper details

vlnc:W_s6gc663x
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Agricultural and Biological Sciences

Not recorded for this paper

View statement
Looking for related papers…
Contents