Network topology and interaction logic determine states it supports

Abstract

In this review paper we summarize a recent progress on the problem of describing range of dynamics supported by a network. We show that there is natural connection between network models consisting of collections of multivalued monotone boolean functions and ordinary differential equations models. We show how to construct such collections and use them to answer questions about prevalence of cellular phenotypes that correspond to equilibria of network models.

Introduction

The goal of this review paper is to describe recent progress on describing capacity of regulatory networks to exhibit different phenotypes in different conditions. In several types of models of regulatory networks we associate different phenotypes to equilibria admitted by the model. Other dynamical phenotypes like cell cycle progression and circadian rhythm can be also investigated by the approach we describe^1,2, but will be not discussed here.

This work relies on several papers in specialized mathematical^3,4 and theoretical computer science⁵ literature that were firmly rooted in problem of parameterization of ordinary differential equations (ODE) network models. The recent realization of the connection between monotone boolean functions and parameterization of switching ODEs^5,6 facilitated successful applications to study of steady states in developmental networks^7,8. The goal of this review is to provide a concise and accessible entry point to the DSGRN approach for the systems biology audience with emphasis on description of steady states in monotone boolean models of developmental networks.

One of our motivations is analysis of developmental networks that determine cell’s fate. Here equilibria of the model represent differentiated cell types and presence of multiple stable equilibria (multistability) suggests that different developmental pathways may lead to different cell types. In such networks it is important to understand what types of multistability are possible, which include the number of coexisting stable equilibria, their prevalence under changing conditions and the types of equilibria that are able to co-exist. When we will use boolean description, the type of the equilibrium is determined by which genes are expressed high, and which ones are expressed at low levels.

Networks are qualitative models of pairwise interactions/influences between nodes which can represent mRNA, protein concentrations, or even different conformations of proteins if they have differential impact on other network nodes. The pairwise interactions are directed from one node to another and may model transcriptional regulation, post-translational modifications like phosphorylation, ubiquitination as well as conformational changes.

Behavior of any network that include feedback loops where a sequence of nodes influence each other in a circular fashion is very difficult to understand without a mathematical model. This is especially true for larger networks. We will concentrate here on two seemingly very different types of models, boolean models and ordinary differential equations models (ODE). Boolean models describe state of each node as “active" and assign to this state value 1, or inactive, and assign to this state value 0. In closely related multivalued boolean models a state of each node i is described by a set of integers X_i = {0, 1, …, t} expressing level to which the node is able to activate some, but not all, downstream nodes. To each node i we associate a boolean update function g_i, which describes the state of the node i as a function of its inputs. Boolean functions that respect the type of network interactions (activating vs. repressing) are called monotone boolean functions (MBF). Dynamics of these models consists of regular updates of the state of each node i. Synchronous update updates all nodes at the same time, while asynchronous update updates nodes one at the time. While synchronous update leads to a deterministic dynamics, the implied presence of a clock that synchronizes the update schedule makes it biologically unrealistic. Since in the asynchronous update the future state depends on the order of nodes that are being updated, this update is represented by a multivalued map where states can evolve differently based on which node is updated first. Although boolean networks are often presented as “parameter free" models, different choices of the boolean update functions that are compatible with the same network may lead to different types of dynamics and different types of equilibria supported by the network.

In contrast to boolean models, ODE models describe evolution of state in continuous time. Regulatory network models often use monotone sigmoid Hill functions to describe network interactions. Specification of each Hill nonlinearity typically requires four parameters and these parameters are difficult to obtain experimentally. In addition, these biological parameters are fundamentally different than the parameters of physics models that are the gold standard of scientific modeling. Mass of an object is a parameter that is independent on the model used; any model attempting to describe motion will need to have this parameter present. Since network ODE models are not derived from first principles, changing a nonlinearity from a Hill function to, say, a polynomial, necessitates re-fitting of all the parameters. Thus, the values of the parameters are model dependent. It is therefore difficult to justify spending experimental effort and resources on measuring precise parameter values at which the network operates. Perhaps it is more realistic to try to establish a range for each parameter. However, even if he ranges are successfully established describing all dynamics of an ODE system across ranges of parameter values is a very difficult problem.

One approach to approximate such description is sampling the parameter space, simulating each resulting ODE system and collect statistical data about the behavior across the samples. However, since the number of parameters for even a small network is very high, such sampling is always sparse. In addition, there is no theory that would guarantee that certain sample size is sufficient to sample all possible behaviors, or even a high proportion of all behaviors. This is partially a consequence of the fact that the set of all possible behaviors for ODE is uncountable, preventing its probabilistic description. Along these lines, Randomized Circuit Perturbation (RACIPE)⁹ is a sampling approach that judiciously tries to sample predominantly biologically relevant parameters.

In this review, we describe an alternative approach, DSGRN (Dynamic Signatures Generated by Regulatory Networks)^3,5,10). DSGRN associates to a network an ODE model with piece-wise constant monotone nonlinearities consistent with the network structure. Since the nonlinearities only assume finite number of values, there are two important simplifications compared to a general ODE model. First, the ODE solutions in the phase space can be described by a finite state transition graph (STG) and second, the continuous parameter space can be decomposed to finite number of domains such that for all parameters in a domain the STG, and hence the dynamics defined by STG, is the same. This turns analysis of an ODE system with its continuum phase space and continuum parameter space into a finite combinatorial problem. In addition, the piecewise constant nonlinearities can be perturbed to Hill function models, ramp function models or any other sigmoid nonlinearities and theoretical results guarantee that the analysis of the combinatorial dynamics is valid for nearby continuum models¹¹.

Numerical investigation comparing the repertoire of equilibria, prevalence of bistability and multistability described DSGRN and the same repertoire described using RACIPE⁹ was done in ref. ¹² for two networks: toggle switch¹³ and toggle triad (Fig. 1a). Since the RACIPE simulates Hill models with finite value of Hill coefficient n, the paper¹² examined how large the value of n should be for RACIPE and DSGRN results to agree. Surprisingly, DSGRN predicts RACIPE results even for relatively small values of n. Since the DSGRN analysis is computationally many orders of magnitude faster than sampling and simulation of RACIPE, this suggests that DSGRN may be a valuable tool for the first pass analysis of the range of behaviors that the network is able to support.

Fig. 1: Toggle triad network analysis.

a Toggle triad network (b) Set of possible update boolean functions $f:{{\mathbb{B}}}^{2}\to \{0,1\}$ where f = g ∘ B. Left column: input values u are all possible values of pair of boolean variables X and Y. Second column; values of function B(u). Columns 3–8: Collection of all possible monotone boolean functions $g:{{\mathbb{B}}}^{2}\to \{0,1\}$: function 0 and the 1 function are constant; function X (Y) repeats the values of input X (Y) and functions ∧ (∨) are logical AND (OR) respectively. c The partially ordered set of all MBFs $g:{{\mathbb{B}}}^{2}\to \{0,1\}$; neighboring functions differ by exactly one values.

Importantly, DSGRN approach bridges the divide between boolean models and ODE models. It can be shown⁵, that each parameter domain of a switching ODE is described by a collection of monotone boolean maps (MBF). Coarse STG dynamics of any ODE parameterized by a parameter from such a domain agrees with the dynamics of the asynchronous update of a particular multivalued monotone boolean map (mMBF). This bridge between boolean models and ODE model suggests description of potential network dynamics by enumerating all multivalued monotone Boolean functions compatible with the network and, for each such choice, describing its set of equilibria. This approach is limited by the exponential growth of number of mMBFs compatible with a network as a function of the number of its nodes and edges. We describe potential ways to address this curse of dimensionality by focusing of particular small subsets of MBFs that seem to represent the behavior of the entire set.

Example: (Toggle triad)

Before we describe our approach in detail, we illustrate it on a simple example. Consider toggle triad network in Fig. 1a. with three nodes a, b, c and pair of repressive edges between any two nodes, This network was anayzed in refs. ^7,14 as a network responsible for Th1/Th2/Th17 immune cell differentiation.

We assume each node can be either active of inactive and these are represented as boolean states in ${\mathbb{B}}=\{0,1\}$. Each node receives two inputs and the state of each node is updated by a monotone boolean function $f:{{\mathbb{B}}}^{2}\to {\mathbb{B}}$. In Fig. 1b, we list all such functions. In the first column we list all potential values of boolean inputs X and Y. Assume for the moment that these represent states of nodes a, b respectively. Since all edges of the network are repressive, second column lists the values that are transmitted by the edges to their target c. The update function f_c takes this pair of boolean values and produces the new state of node c. Therefore f_c is a composition of the map B which reverses the boolean inputs and which depends on the fact that both edges are repressive, and the second map g which takes this reversed input to its final value. There are six choices for a monotone boolean function g listed in the last six columns. These choices only depend on the fact that the node c has two inputs, but not on whether these are activating or repressing—that information is encoded in the map B. The potential functions g are the constant functions 0 and 1; function X (Y) that repeats the values of the input X (Y) and functions ∧ (∨), which are logical AND (OR), respectively. This set of functions can be organized as a partially ordered set (poset) in Fig. 1c where two functions are connected by an edge when they differ in exactly one output.

All possible MBF that are consistent with the toggle triad are triples f = (f_a, f_b, f_c). Therefore there are 6³ = 216 boolean network models.

We investigate how many of these models support a constant equilibria (000) and (111), how many support equilibrium (001) where only one gene is active and two are suppressed and how many support equilibrium (110) where two genes are active and one is suppressed. Because of the symmetry, the number of functions f supporting (001) and the number supporting (010) (as well as (100)), is the same. The key observation is that an equilibrium Q = (uvw) is supported by f = (f_a, f_b, f_c) if, and only if,

$${f}_{a}(Q)=u,\quad {f}_{b}(Q)=v,\quad {f}_{c}(Q)=w.$$

(1)

With this in mind, a direct inspection of table in Fig. 1 shows that (000) is an equilibrium when

$${f}_{a}(00)=0,\quad {f}_{b}(00)=0,\,{\rm{and}}\quad {f}_{c}(00)=0.$$

There is only a single combination of functions, f = (0, 0, 0), that satisfies these conditions. Therefore the phenotype (000) has prevalence 1/216 in toggle triad. Similarly, the equilibrium (111) is only supported by the parameter (1, 1, 1) and has prevalence 1/216. We conclude that both constant phenotypes are rare in toggle triad.

Now we count number of boolean networks that support equilibrium (001). This requires

$${f}_{a}(01)=0,\quad {f}_{b}(01)=0,\,\quad {f}_{c}(00)=1.$$

The first and the second conditions are satisfied by any functions f_a, f_b ∈ {0, ∧, Y} and the third condition by by f_c ∈ {∧, X, Y, ∨, 1}. Therefore there are 3 × 3 × 5 = 45 parameters supporting this equilibrium. Similar calculation shows that also (110) is supported by 45 boolean networks, as would be expected from the symmetry considerations. We conclude that toggle triad supports mixed phenotypes, where one gene, or two genes are active with prevalence 45/216. This is higher than the prevalence of constant phenotypes. These results agree with ref. ¹⁴ which found using RACIPE sampling that the constant equilibria are negligible phenotype and most of the monostable dynamics shows convergence to either singly activated (100) or doubly activated (110) types of equilibria.

We close the introduction with a comment on non-degenerate boolean functions which we return to later in the text. Among the six MBFs in Fig. 1b the constant functions 0, 1 are considered degenerate, as their output does not depend on the input values. Further, if we assume that the network edges have been experimentally determined, there must be conditions at which these edges influence the state of the target node. Under this assumption, function g(XY) = X is also degenerate, since the input Y does not influence the result; the same is true for the function g(XY) = Y. Therefore the only non-degenerate functions g(XY) = X ∧ Y and g(XY) = X ∨ Y. The concept of non-degenerate monotone boolean functions allows us, for larger networks, to restrict our attention to only essential boolean networks f where each component function is non-degenerate. Note that there are only 8 essential boolean networks out of 216 boolean networks; none of these support constant equilibria (000), (111), but 2/8 support mixed equilibria (001) and (110).

Astute reader certainly notices that there are six mixed equilibria (100), (010), (001), (110), (101), (011) each of which is supported by two out of eight essential networks. This is only possible when some of the essential networks support bistability or multistability. This is indeed the case, and we postpone the computation of prevalence of bistability and multistability to the “Multistability in toggle triad”.

The paper is organized as follows. “Ensemble of multivalued monotone boolean functions compatible with the network” is devoted to theoretical description of DSGRN methodology that builds a collection of all multivalued monotone boolean functions compatible with network structure and organizes it into parameter graph ${\mathsf{PG}}$. Each node of the parameter graph gives rise to potentially different dynamics captured by a state transition graph (STG); the long term behavior of STG dynamics is captured by a Morse graph. Theoretical developments are illustrated along the way on a E2F-Rb network responsible for commitment to the S-phase during the mammalian cell cycle. In “Essential boolean parameters” we use our methodology to analyze three networks: E2F-Rb network and two networks implied in immune commitment networks: toggle triad and toggle tetrahedron. We conclude by the “Discussion” section and leave the description of connection between the parameter graph ${\mathsf{PG}}$ and the ODE network models to “Connecting parameter graph PG to ODE models”.

Ensemble of multivalued monotone boolean functions compatible with the network

In addition to the toggle triad example in the introduction we will illustrate our methods on a network that plays central role in transition from G1 to S phase in cell cycle in eukaryots. A mammalian network (Fig. 2a) was studied by ref. ¹⁵ and then further analyzed by refs. ^1,16. The essential elements of this network is a family of E2F transcription factors which are sequestered in a heterodimer by Rb in non-proliferating cells in G1 phase. Release of E2F by phosphorylation of Rb results in initiation of S phase of the cell cycle. The principal controls of Rb are cyclin/kinase complexes CycD/Cdk4,6 and CycE/Cdk2. The initial phosphorylation of Rb releases E2F, which up-regulates the kinase CycE/Cdk2, which then completes the phosphorylation of Rb and finishes the release of E2F^{1,15,16,17,18,19}. In Fig. 2a the node Rb represents complex E2F-Rb and node E2F a free E2F that is able to act as a transcription factor. Interestingly, the mammalian network and the yeast S. cerevisiae (Fig. 2b) network have identical structure in spite of the fact that individual genes having limited homology^20,21. The central dynamical feature of both of these networks is ability to exhibit bistability between an On state where E2F is high, Rb low and CycE high, and an Off state where E2F is low, Rb high, and CycE is low.

Fig. 2: G1/S restriction point network.

a G1/S restriction point network in mammalian cells (b) START network in yeast (c) Reduced network example.

In Fig. 2c, we depict a simplified network where we removed the activating self-edge on E2F. We ask whether this simplified network still supports required bistability, and, if so, what is the prevalence of this phenotype.

A regulatory network RN = (V, E, δ) is a directed graph with nodes V, directed edges E, and an edge sign function δ: E → { − 1, 1}. We denote an edge from node v_i to node v_j without indicating its sign by v_i⊸v_j. The edge v_i⊸v_j is activating if ${\delta }_{i}^{j}=1$ and repressing if ${\delta }_{i}^{j}=-1$. Graphically, an activating edge is denoted by v_i → v_j and a repressing edge by ${v_i}\dashv{v_j}$. The sources and targets of a node u are given by

$${\mathbf{S}(v_i)}:=\{{v_k}\in {V}|{v_k}\multimap{v_i}\in {E}\}\quad{\mathbf{T}(v_i)}:=\{{v_j}\in{V}|{v_i}\multimap{v_j}\in{E}\},$$

respectively.

In our simplified example in Fig. 2c we have T(v₃) = {v₁, v₂} and S(v₃) = {v₂}.

Parameters

In this section, we want to define the set of boolean functions that are compatible with the network RN. Consider the toggle triad example where we associated a boolean update function f_a to node a. Node a is a source of two edges to b and c. In real regulatory network, the chemical concentration x_a at node a will likely affect b and c at different levels, which we think of as different thresholds. Therefore the state of node a should have more than two states 0 (inactive) and 1 (active); it should at least have states 0 (does not activate neither b nor c), 1 (activates one but not the other), and 2 (activates both b and c). This leads naturally to considering multivalued monotone boolean networks where the state of a node v_i is one of the integers X_i = {0, 1…, t_i}, where t_i:= ∣T(v_i)∣ denote the number of target nodes of v_i. Since each edge v_i → v_j is associated with a threshold, this integer represents number of thresholds that get activated by the state of v_i.

This extension to multilevel boolean networks enlarges the set of functions that are compatible with RN. Instead of calling all such collections “ multilevel monotone boolean networks", we will simply call them DSGRN parameters of RN, or just parameters of RN. Because of different activation thresholds, the dynamics of the network may change when the order of thresholds changes. Even the same collection of multilevel monotone boolean functions, different order of activation of downstream edges may lead to different dynamics. Therefore such orders must be included in the description of the parameters of the network.

An order parameter for node v_i is a bijection θ_i: T(v_i) → {1, …, t_i} which defines an ordering of the out-edges of v_i. The set of order parameters for v_i is denoted by Θ(v_i). The set of all order parameters is given by ${\rm{\Theta }}:={\prod }_{{v}_{i}\in V}{\rm{\Theta }}({v}_{i})$.

For the network in Fig. 2c, since ∣T(v₁)∣ = ∣T(v₂)∣ = 1 and we have X₁ = X₂ = {0, 1} there is a single order parameter in both Θ(v₁) = {θ₁} and Θ(v₂) = {θ₂}. Since ∣T(v₃)∣ = 2, we have X₃ = {0, 1, 2} and ${\rm{\Theta }}({v}_{3})=\{{\theta }_{3}^{1},{\theta }_{3}^{2}\}$ where

$${\theta }_{3}^{1}({v}_{1})=1,\quad {\theta }_{3}^{1}({v}_{2})=2\qquad {\rm{and}}\qquad {\theta }_{3}^{2}({v}_{1})=2,\quad {\theta }_{3}^{2}({v}_{2})=1.$$

(2)

The collection of all order parameters Θ has two elements $({\theta }_{1},{\theta }_{2},{\theta }_{3}^{1})$ and $({\theta }_{1},{\theta }_{2},{\theta }_{3}^{2})$. We note that if ∣T(v₃)∣ = k the collection Θ(v₃) will have k! permutations ${\theta }_{3}^{1},\ldots ,{\theta }_{3}^{k!}$.

Let ${\mathbb{B}}:=(\{0,1\};0\left. < 1\right\})$ be a two element set with natural order 0 ≺ 1 and let ${{\mathbb{B}}}^{n}$ be a partially ordered set (poset) of n vectors with elements in ${\mathbb{B}}$ with order induced component-wise by <. ${{\mathbb{B}}}^{n}$ is in fact a Boolean lattice. Similarly, the

$${\mathcal{C}}:=\prod _{{v}_{i}\in V}{X}_{i}.$$

is a Boolean lattice of integer vectors with partial order ≺ induced component-wise by <. That is, a ≺ b if for every i the i-th component satisfies a_i ≤ b_i.

While the assumption that each v_i activates downstream nodes v_j ∈ T(v_i) at different thresholds leads to considering the set of states ${\mathcal{C}}$, the activation of a particular node v_j ∈ T(v_i) by v_i only happens at a single threshold. This leads to definition of the following function that associates to each state $c\in {\mathcal{C}}$ the information on which targets it actually activates and which ones it does not. The state $c={({c}_{i})}_{{v}_{i}\in V}$ produces an input to a node v_j via the input map

$${B}^{j}:{\mathcal{C}}\to \prod _{i\in V}{{\mathbb{B}}}^{| {\bf{S}}({v}_{j})| },\qquad {B}^{j}:={({B}_{i}^{j})}_{{v}_{i}\in {\bf{S}}({v}_{j})}$$

where

$${B}_{i}^{j}(c):=\left\{\begin{array}{ll}0,\quad \quad &{\rm{if}}\,{c}_{i} < {\theta }_{i}({v}_{j})\,{\rm{and}}\,{\delta }_{i}^{j}=1\,{\rm{or}}\,{c}_{i}\ge {\theta }_{i}({v}_{j})\,{\rm{and}}\,{\delta }_{i}^{j}=-1\\ 1,\quad \quad &{\rm{if}}\,{c}_{i}\ge {\theta }_{i}({v}_{j})\,{\rm{and}}\,{\delta }_{i}^{j}=1\,{\rm{or}}\,{c}_{i} < {\theta }_{i}({v}_{j})\,{\rm{and}}\,{\delta }_{i}^{j}=-1\end{array}\right..$$

(3)

Note that for activating edge v_i → v_j, if c_i is below (above) the activating threshold θ_i(v_j) then the input from v_i to v_j is 0 (1). This assignment is reversed if the edge is repressing. Function $B={({B}^{j})}_{j\in V}$ depends on the structure of the network through functions ${\delta }_{i}^{j}$, the number of inputs to each node and logic parameter θ.

The function B associates to each $c\in {\mathcal{C}}$ and each node v_j ∈ V its boolean input vector which is an element of ${{\mathbb{B}}}^{| {\bf{S}}({v}_{j})| }$. Whether a particular boolean input activates an output edge v_j⊸v_i connecting v_j to v_i ∈ T(v_j) or not, is determined by a logic parameter at node v_j that we define next. Logic parameters capture all potential patterns of combinatorial activation, where only some combinations of input nodes activate an output edge. In addition, these patterns may vary from one output edge of v_j to the next.

Definition 1.1

A function $g:{{\mathbb{B}}}^{n}\to [0,1,\ldots ,k]$ is a positive multivalued monotone Boolean function (mMBF) if b¹ ≺ b² implies g(b¹)≤g(b²). When k = 1 the function g is positive monotone Boolean function (MBF).

A logic parameter for node v_i is a positive boolean mMBF

$${g}_{i}:{{\mathbb{B}}}^{| {\bf{S}}({v}_{i})| }\to {X}_{i}.$$

A collection $g:={({g}_{i})}_{{v}_{i}\in V}$ is a logic parameter. The set of all logic parameters for node v_i is denoted ${\mathcal{L}}({v}_{i})$, while the set of all logic parameters is ${\mathcal{L}}:={\prod }_{{v}_{i}\in V}\,{\mathcal{L}}({v}_{i})$.

Definition 1.2

Consider two logical parameters $g,h\in {\mathcal{L}}({v}_{i})$, where $g,h:{{\mathbb{B}}}^{n}\to {X}_{i}$. We say g ≺ h if g(b)≤h(b) for all $b\in {{\mathbb{B}}}^{n}$. With this ordering the set of logic parameters $({\mathcal{L}}({v}_{i}),\prec )$ is a partially ordered set.

We describe the set of logic parameters for the network in Fig. 2c. At node v₁ since S(v₁) = v₃ and X₁ = {0, 1}, the set of logic parameters is the set of all MBFs ${g}_{1}:{\mathbb{B}}\to {X}_{1}$. Two of these functions are constant: we denote by 0 the zero function and by 1 the one function. The third function, which we denote by Id maps 0 to 0 and 1 to 1 see Fig. 3a. These functions form a poset shown in Fig. 4a.

Fig. 3: Logic parameters for the restriction point network.

a Three logic parameters ${g}_{1}\in {\mathcal{L}}({v}_{1})$; b Six logic parameters ${g}_{3}\in {\mathcal{L}}({v}_{3})$.

Fig. 4: Logic parameter graphs.

a Logic parameter graph ${\mathcal{L}}({v}_{1})$ consists of MBFs ${g}_{1}:{\mathbb{B}}\to \{0,1\}$; b logic parameter graph ${\mathcal{L}}({v}_{3})$ consists of mMBFs ${g}_{3}:{\mathbb{B}}\to \{0,1,2\}$ written as sums of two ordered functions (2-chains) from (a); c poset of MBFs with three inputs X, Y, Z, where α = (X ∧ Y) ∨ (X ∧ Z) ∨ (Y ∧ Z). Blue circles indicate non-degenerate MBFs.

Consider v₂. Since S(v₂) = {v₁, v₂} and X₂ = {0, 1}, the set ${\mathcal{L}}({v}_{2})$ is the set of MBFs that map ${g}_{2}:{{\mathbb{B}}}^{2}\to {X}_{2}$. There are 6 such functions which we denote by 0, ∧, X, Y, ∨, 1. These were depicted in Fig. 1b, c.

Finally, consider the node v₃. Since S(v₃) = {v₂} and the set X₃ = {0, 1, 2}, the logical parameters are multivalued monotone boolean functions ${g}_{3}:{\mathbb{B}}\to {X}_{3}$. It can be shown^5,6, that there are 6 such mMBFs that correspond to ordered pairs (2-chains) in the poset of MBFs from ${\mathbb{B}}$ to ${\mathbb{B}}$. Therefore the functions g₃ are sums f + g of pairs of functions f ≺ g in the set f, g ∈ {0, Id, 1} in Fig. 3a. We list these function using the sum notation in Fig. 3b; the poset structure of these functions is in Fig. 4b.

The set of all parameters is the product of logic and order parameters ${\mathcal{P}}:={\mathcal{L}}\times {\rm{\Theta }}$. We call ${\mathcal{P}}({v}_{i}):={\mathcal{L}}({v}_{i})\times {\rm{\Theta }}({v}_{i})$ the set of parameters for node v_i; the set of all parameters is the product ${\mathcal{P}}={\prod }_{{v}_{i}\in V}{\mathcal{P}}({v}_{i})$.

We have seen that the set of logical parameters has an additional structure of a partially ordered set, or a graph. In our example, the poset ${\mathcal{L}}({v}_{1})$ is in Fig. 4a, poset for ${\mathcal{L}}({v}_{2})$ is in Fig. 1c, and ${\mathcal{L}}({v}_{3})$ is in Fig. 1c. We will call this organization of the set of DSGRN parameters ${\mathcal{P}}$ a parameter graph ${\mathsf{PG}}$ of network ${\mathsf{RN}}$. The following section shows the construction of ${\mathsf{PG}}$ by defining adjacency between elements of ${\mathcal{P}}$.

Parameter graph

The parameter graph ${\mathsf{PG}}$ has nodes and edges. The set of nodes is the set of DSGRN parameters ${\mathcal{P}}$. The undirected edges will connect adjacent nodes. Two parameter nodes for a node v_i, $({g}_{i},{\theta }_{i}),({\hat{g}}_{i},{\hat{\theta }}_{i})\in {\mathcal{P}}({v}_{i})$ are adjacent if exactly one of the following conditions is satisfied.

• Order adjacency: ${g}_{i}={\hat{g}}_{i}$ and the values of the order parameters θ_i and ${\hat{\theta }}_{i}$ are exchanged on a single pair of neighboring entries on which the logic parameters agree.

• Logical adjacency: ${\theta }_{i}={\hat{\theta }}_{i}$ and the logic parameters g_i and ${\hat{g}}_{i}$ differ by 1 in a single input i.e., there exists exactly one $d\in {{\mathbb{B}}}^{| {\bf{S}}({v}_{i})| }$ such that ${g}_{i}(d)={\hat{g}}_{i}(d)\pm 1$.

The factor graph for node v_i is the undirected graph ${\mathsf{PG}}({v}_{i}):=({\mathcal{P}}({v}_{i}),{\mathcal{E}}({v}_{i}))$ whose nodes are parameter nodes for v_i and whose edges are given by adjacency. The parameter graph ${\mathsf{PG}}:=({\mathcal{P}},{\mathcal{E}})$ is the Cartesian product ${\mathsf{PG}}:={\prod }_{{v}_{i}\in V}{\mathsf{PG}}({v}_{i})$. That is, there is an edge $({p}^{1},{p}^{2})\in {\mathcal{E}}$ if and only if there is a unique v_i ∈ V such that $({p}_{i}^{1},{p}_{i}^{2})\in {\mathcal{E}}({v}_{i})$ and ${p}_{i}^{1}={p}_{i}^{2}$ otherwise.

We return to our example in Fig. 2c. Since the set of order parameters Θ(v₁) and Θ(v₂) have both only one element, the factor graph ${\mathsf{PG}}({v}_{1})\cong {\mathcal{L}}({v}_{1})$ is isomorphic to the poset of logic parameters ${\mathcal{L}}({v}_{1})$ in Fig. 4a and factor graph ${\mathsf{PG}}({v}_{2})\cong {\mathcal{L}}({v}_{2})$ is isomorphic to the poset of logic parameters ${\mathcal{L}}({v}_{2})$ in Fig. 1c. The factor graph ${\mathsf{PG}}({v}_{3})$ consists of two copies of the poset of logic parameters ${\mathcal{L}}({v}_{3})$ in Fig. 4b, where one copy has order parameter ${\theta }_{3}^{1}$ and the copy has order ${\theta }_{3}^{2}$, see (2). The two copies are connected between pairs of nodes 0 + 0, Id + Id and 1 + 1 where the change from ${\theta }_{3}^{1}$ to ${\theta }_{3}^{2}$ satisfies oder adjacency condition.

In Fig. 4c we show a logic factor graph for a network node with three inputs and one output, which consists of 20 monotone boolean functions. The number of MBFs, with n inputs, called n-th Dedekind number, increases rapidly with the number of inputs. The 9th Dedekind number has been only recently computed²².

Essential parameters

There are two types of subsets of the logical parameters that are of special interest. First, we may only be interested in those logical parameters at which the associated multivalued monotone boolean function is non-degenerate. The definition below directly generalizes the concept of non-degenerate MBF^23,24.

Definition 1.3

A variable b_k is an essential variable of a multivalued monotone Boolean function f if there is at least one b ∈ Bⁿ such that $f{| }_{{b}_{k} = 0}\,\ne\, f{| }_{{b}_{k} = 1}$. An MBF is said to be non-degenerate if all variables are essential.

Definition 1.4

A parameter p ∈ PG of network ${\mathsf{RN}}$ is essential if the corresponding logic parameter g is a non-degenerate mMBF.

This agrees with the definition of essential parameter nodes given in refs. ^2,5,25. All non-degenerate mMBFs in ${\mathcal{L}}({v}_{1})$ and ${\mathcal{L}}({v}_{2})$ are in blue circles in Fig. 4.

Boolean parameters

Another special subset of logical parameters are those that represent MBF rather than mMBF. Consider those parameters $p=(g,\theta )\in {\mathsf{PG}}$ where the range of every mMBF g_i consists of only two values 0 and t_i, i.e., the lowest possible value and the highest possible value. This can be interpreted as each input either does not activate any target nodes or it activates all target nodes. Since such mMBF has only two values, it can be represented as a MBF ${\tilde{g}}_{i}$. We call such parameters boolean parameters since the function $\tilde{g}=({\tilde{g}}_{1},{\tilde{g}}_{2},\ldots ,{\tilde{g}}_{n})$, as a map from ${{\mathbb{B}}}^{n}\to {{\mathbb{B}}}^{n}$, represents a traditional boolean system where states 0 and 1 are assigned to each variable.

In Fig. 4a, c, all parameters are boolean since the range of all functions is {0, 1}. In Fig. 4b there are three Boolean parameters 1 + 1, Id + Id and 0 + 0. Notice that not all boolean parameters are essential.

Essential boolean parameters

We now restrict our attention even further to just essential boolean parameters. These represent parameters represented by non-degenerate monotone boolean function. Figure 4c shows 9 non-degenerate MBFs with three inputs in blue circles. Paper⁸ studied repressive tetrahedron network (see “Toggle tetrahedron network” below) where all four nodes have three repressive inputs from the other three nodes, and in turn repress all other nodes. Each node has three inputs and three outputs and the parameter graph ${\mathsf{PG}}$ has about 27 trillion nodes. However, since there are only nine non-degenerate MBFs, the total number of essential boolean parameters is only 9⁴ = 6561. Surprisingly, the frequency of observed equilibria that exists within this small set approximates well the overall frequency of dynamics across entire ${\mathsf{PG}}$, as documented by random DSGRN parameter sampling as well as ODE parameter sampling by RACIPE⁸. Clearly, analyzing dynamics of 6561 parameters is computationally feasible while examining 27 trillion parameters is not. The reason why this small sample seems to match the overall dynamics remains an open problem.

Dynamics

The multi-valued boolean dynamics associated to a network ${\mathsf{RN}}=(V,E,\delta )$ depends on a choice of parameter $p\in {\mathcal{P}}$, and on the input function B defined in (3) that reflects the position of the positive and negative in the network through function δ.

The dynamics occur on the state space ${\mathcal{C}}={\prod }_{{v}_{i}\in V}{X}_{i},$ introduced earlier. We call $c\in {\mathcal{C}}$ a state of the network ${\mathsf{RN}}$.

We return to the E2F-Rb example and define the functions ${B}^{1}:{X}_{3}\to {\mathbb{B}},{B}^{2}:{X}_{1}\times {X}_{3}\to {{\mathbb{B}}}^{2}$ and ${B}^{3}:{X}_{2}\to {\mathbb{B}}$, see Fig. 5 for the order parameter $({\theta }_{1},{\theta }_{2},{\theta }_{3}^{1})$, where ${\theta }_{3}^{1}({v}_{1})=1$ and ${\theta }_{3}^{2}({v}_{2})=2$. We only list relevant inputs ${X}_{i}\subset {\mathcal{C}}$ for each i. Since the edge v₃ → v₁ is activating and since ${\theta }_{3}^{1}({v}_{1})=1$, v₃ activates v₁ at the first threshold the output value changes from 0 to 1 at the first threshold (see Fig. 5a.) Because the edge from v₁ to v₂ is repressive, the first component ${B}_{1}^{2}$ of the function B² reverses the boolean input from node v₁. The second component ${B}_{3}^{2}$ describes input from node v₃ to node v₂ which is activating at the second threshold, see Fig. 5b. Finally, the function B³ in Fig. 5c reflects the fact that the edge x₂⊣x₃ is repressive.

Fig. 5: Functions B¹, B², B³, where we only list the relevant inputs.

Note that the presence of negative edge between v₁ and v₂ is manifested in the reversal in the first coordinate ${B}_{1}^{2}$ of B² and negative edge between v₂ and v₃ is reflected in reversal in function B³.

Definition 1.5

The dynamics for network ${\mathsf{RN}}$ with the sign function δ at parameter $(g,\theta )\in {\mathcal{P}}$ is defined as an asynchronous update of function f:= g ∘ B. More precisely,

• 1. The multi-valued boolean map$f:{\mathcal{C}}\to {\mathcal{C}}$ is defined by

  $${f}_{i}(c):={g}_{i}({B}^{i}(c))$$

  (4)

• 2. The multi-level boolean dynamics${\mathcal{F}}:{\mathcal{C}}\rightrightarrows {\mathcal{C}}$ is a multi-valued map generated by f and defined by

  • If f(c) = c then ${\mathcal{F}}(c)=\{c\}$.

  • For any v_i and η ∈ { − 1, 1} satisfying ηf_i(c) > ηc_i the state

    $${\overline{c}}_{i}={c}_{i}+\eta ,\quad {\overline{c}}_{j}={c}_{j}\,{\rm{for}}\,j\,\ne\, i$$

    satisfies $\overline{c}\in {\mathcal{F}}(c)$.

The maps f and ${\mathcal{F}}$ depend on the choice of network ${\mathsf{RN}}$ and the choice of parameter $(g,\theta )\in {\mathcal{P}}$. We will explicitly include these dependencies as arguments as needed.

This definition provides a connection between each parameter $(g,\theta )\in {\mathcal{P}}$ and a discrete dynamics on ${\mathcal{C}}$ given by map ${\mathcal{F}}$. As we show in “Connecting parameter graph PG to ODE models” each such map ${\mathcal{F}}$ also represents behavior of continuous solutions of switching ODE system that models continuous network dynamics. Therefore the parameter graph ${\mathsf{PG}}$ connects continuous dynamics of ODEs and asynchronous update dynamics induced by discrete map ${\mathcal{F}}$.

Remark 1.1

Consider all boolean parameters $p=(g,\theta )\in {\mathsf{PG}}$ where the logical parameter g gives rise to the same boolean function $\tilde{g}$, but where they differ in the order parameter. Then it is easy to see that the dynamics at all these parameters will be the same since the order of thresholds is irrelevant for the resulting update function $f(c)=\tilde{g}(B(c)).$ Therefore boolean parameters are fully described by their logic parameters and such logic parameters correspond to collections of mMBFs.

Morse graph

The recurrent dynamics of ${\mathcal{F}}(\cdot ;p)$ are encoded by a Morse graph${\mathsf{MG}}(p)$. The Morse graph ${\mathsf{MG}}=({\mathsf{SCC}},A)$ is a directed graph with nodes consisting of strongly connected components of ${\mathsf{STG}}({\mathcal{C}},p)$. The Morse graph is the Haase diagram on ${\mathsf{SCC}}$ of the reachability relation A on the strongly connected components within ${\mathsf{STG}}({\mathcal{C}},p)$. We label each strongly connected component $s\in {\mathsf{SCC}}$ according to the following.

• If $s\in {\mathsf{SCC}}$ consists of a single recurrent state, s = {x}, then x is a fixed point of ${\mathcal{F}}$ and we label s by ${\mathsf{FP}}(x)$.

• If $s\in {\mathsf{SCC}}$ is not an ${\mathsf{FP}}$ then we label s as a partial cycle${\mathsf{PC}}$ or a full cycle${\mathsf{FC}}$. The strongly connected component s is a ${\mathsf{PC}}$ if s is constant in at least one coordinate i.e., there is a node u ∈ V and an integer k such that x ∈ s implies x_u = k. If s is not an ${\mathsf{FP}}$ or an ${\mathsf{PC}}$ then s is an ${\mathsf{FC}}$. If $s\in {\mathsf{SCC}}$ has no out-edges in ${\mathsf{MG}}(p)$, we call sstable Morse node. Otherwise, s is unstable.

Applications

We now illustrate our approach on three examples. First, we investigate the ability of E2F-Rb network without self-loop on E2F (Fig. 2c) to support the bistable phenotype between On and Off state that characterizes the switch-like entry into S phase in the cell cycle. Then we look at two networks that have been studied in the context of differentiation of immune cells subtypes: toggle triad and toggle tetrahedron. For toggle triad we look at prevalence of different types of bistability and for toggle tetrahedron we summarize the results on prevalence of different types of equilibria, that are described in more details in ref. ⁸.

In all of these examples we focus our attention to essential boolean parameters as this small set is amenable to theoretical analysis. The analysis across entire parameter graph ${\mathsf{PG}}$ is possible using DSGRN software^26,27.

E2F-Rb network

In this section, we find fixed points for the E2F-Rb network at different parameters. Fixed points fulfill the satisfiability condition

$$s\in {\mathcal{C}}\,{\rm{is}}\,{\rm{a}}\,{\rm{fixed}}\,{\rm{point}},\,{\rm{iff}}\,{f}_{i}(s)={g}_{i}({B}^{i}(s))={s}_{i},\quad i=1,2,3,$$

(5)

where ${g}_{i}\in {\mathcal{L}}({v}_{i})$, the set of logical parameters. Recall that ${\mathcal{L}}({v}_{1})$ is in Fig. 4a, ${\mathcal{L}}({v}_{2})$ in Fig. 1c, and the ${\mathcal{L}}({v}_{3})$ in Fig. 4b. The functions Bⁱ are listed in Fig. 5. The set of composite functions f₁:= g₁ ∘ B¹: X₃ → X₁, where ${g}_{1}\in {{\mathcal{L}}}_{1}$ is identical to that in Fig. 3a. All possibilities for the second composite function f₂:= g₂ ∘ B²: X₁ × X₃ → X₂, for all choices of g₂, are listed as columns in Fig. 6a. We list all compositions f₃:= g₃ ∘ B³: X₂ → X₃ in Fig. 6b.

Fig. 6: Asynchronous update functions.

a Compositions f₂ = g₂ ∘ B² for all 6 choices of function g². b Compositions f₃ = g₃ ∘ B³ for all six choices of function g³.

These tables make direct verification of Eq. (5) possible, albeit for larger network this poses a combinatorial problem as the satisfiability of (5) is equivalent to logical satisfiability problem²⁸ which is NP complete^29,30.

We consider two potential fixed points that are biologically important. First the state s_on = (1, 0, 2) represents the state On; that is, a commitment to transition from G1 to S phase of the cell cycle, since both v₁ (CycE) and v₃ (free E2F) are at their highest states, and v₂ (E2F-Rb dimer) is at the lowest state. Consider two parameters p₁: = (L₁, θ) and p₂: = (L₂, θ) with the order parameter $\theta :=({\theta }_{1},{\theta }_{2},{\theta }_{3}^{1})$ used above and the only two essential logic parameters

$${L_1}=({g_1}=Id,\,{g_2}=\wedge,\,{g_3}=Id\,+\,Id),\quad{L_2}=({g_1}=Id,\,{g_2}=\vee,\,{g_3}=Id\,+\,Id).$$

Then for parameter p₁ we get

$$f({s_{on})}=f(1,\,0,\,2)=({f_1}(2),\,{f_2}(12),\,{f_3}(0))=(1,\,0,\,2),$$

so s_on is a fixed point, but for parameter p₂ we get

$$f({s_{on}})=f(1,\,0,\,2)=({f_1}(2),\,{f_2}(12),\,{f_3}(0))=(1,\,1,\,2).$$

Therefore s_on is a fixed point for p₁, but not for p₂. Similar calculation shows that s_off = (0, 1, 0) that represents the Off state where cell is pausing in G1 phase, is a fixed point under p₂, but not under p₁.

We remark that there are two other essential parameters ${p}_{3}:=({L}_{1},\bar{\theta })$ and ${p}_{4}:=({L}_{2},\bar{\theta })$ with the same logical parameters L₁, L₂, but order parameter $\bar{\theta }=({\theta }_{1},{\theta }_{2},{\theta }_{3}^{2})$. The results are similar: one of the parameters supports only s_on and one of them supports only s_off.

Since E2F-Rb network is assumed to act as a bistable switch^1,15,16 we would like to investigate if there are other, non-essential parameters where both s_on and s_off are fixed points. Examining Fig. 6 for columns where f₃(12) = 0 and f₃(00) = 1 we find that the only such function arise from logical parameter g₂(X₁, X₃) = X₁. This represents function where the input to v₂ from v₃ does not affect the outcome since the function g₂ only depends on the input from v₁. Erasing the edge v₃ → v₂ from the network we get a network that consists of single positive loop. Such a reduced network is known to support bistablity.

Our analysis can be interpreted in two ways:

• the smaller network consisting of a positive loop v₁⊣v₂, v₂⊣v₃ and v₃ → v₁ supports the bistability;

• the self-edge E2F to E2F is needed for the original network to support the bistability at the set of essential parameters.

Both interpretations provide valuable insight into interplay between the structure of the network and bistability.

Developmental networks

Multistability in toggle triad

We now investigate parameters that support bistability and multistability in toggle triad. We only consider essential boolean parameters which, by Remark 1.1, can be represented as g = (g_a, g_b, g_c) where each g_i is a non-degenerate monotone boolean function.

Using the update functions f_i = g_i ∘ Bⁱ for i = a, b, c, where the Bⁱ(XY) = (¬X ¬Y) reverses both inputs (see Fig. 1b), the essential boolean parameters that support so called mirror bistability between (001) and (110) must satisfy

$$\begin{array}{rc}{f}_{a}(01)=0,\quad &{f}_{a}(10)=1\\ {f}_{b}(01)=0,\quad &{f}_{b}(10)=1\\ {f}_{c}(00)=1,\quad &{f}_{c}(11)=0\end{array}$$

Direct inspection of table in Fig. 1b shows that there is unique choice of functions for both g₁(X, Y) = Y and g₂(X, Y) = Y. On the other hand any g₃(X, Y) ∈ {∨, Y, X, ∧} works. Therefore there are 4 boolean parameters which support this type of bistability. However, none of these parameters are essential.

On the other hand, non-mirror bistability between (001) and (100) is supported by all parameters for which

$$\begin{array}{rc}{f}_{a}(01)=0,\quad &{f}_{a}(00)=1\\ {f}_{b}(01)=0,\quad &{f}_{b}(10)=0\\ {f}_{c}(00)=1,\quad &{f}_{c}(10)=0.\end{array}$$

Then any combination of choices g_a(X, Y) ∈ {∧, Y}, g_b(X, Y) ∈ {0, ∧,} and g_c(X, Y) ∈ {∧, X} satisfy these equations. These combinations form eight parameters supporting this bistability, and one of them, g = (∧, ∧, ∧) is an essential boolean parameter.

Can the network support tristability? The natural candidates for three fixed points are (001), (100), (010). This adds additional conditions (third column below) to the conditions above

$$\begin{array}{rc}{f}_{a}(01)=0,\quad &{f}_{a}(00)=1\quad {f}_{a}(10)=0\\ {f}_{b}(01)=0,\quad &{f}_{b}(10)=0\quad {f}_{b}(00)=1\\ {f}_{c}(00)=1,\quad &{f}_{c}(10)=0.\quad {f}_{c}(01)=0\end{array}$$

Direct calculation shows that g = (∧, ∧, ∧) supports the tristability (001), (100), (010). Similar calculations shows that the only parameter that supports tristability between (110), (011), (101) is g = (∨, ∨, ∨).

We close this part by discussion of all 8 essential boolean parameters. From the discussion in the introduction, the equilibrium (001) is supported by two essential parameters g = (∧, ∧, ∨) and g = (∧, ∧, ∧). By symmetry, the equilibrium (010) is supported by g = (∧, ∨, ∧) and g = (∧, ∧, ∧) and, finally, the equilibrium (100) by g = (∨, ∧, ∧) and g = (∧, ∧, ∧). The second one of these, logical parameters g(∧, ∧, ∧), supports tristability. Similar argument shows that the parameters with two copies of g_i = ∨ and one copy of g_i = ∧ support a single equilibrium in the set (110), (011), (101). We conclude that no essential boolean parameter supports bistability in the toggle triad. While we examined a very small subset of essential boolean parameters, our results are consistent with¹⁴ which found that the prevalence of tristability among (100), (100), (010) is greater than any other type of tristability and that bistability is comparatively rare.

The methodology in this paper also allows us to ask us what happens if we perturb parameters away from essential boolean parameters. Perturbing essentiality leads to consideration of 216 choices of boolean functions discussed in the introduction. Perturbing boolean functions to the class of multivalued boolean functions is possible within the structure of the parameter graph and will result in potentially different dynamics.

Toggle tetrahedron network

In this section, we briefly review extensions of the results from toggle triad to toggle tetrahedron⁸. Motivation for studying this network is differentiation of naive CD4+ T cells into four different types denoted Th1, Th2, Th17, and Treg. Each of these four types of cells is characterized by a lineage specific transcription factors and these factors repress each other.

Therefore toggle tetrahedron has four nodes a, b, c, d that are fully connected without self-edges and each node receives three repressive inputs from other three nodes. We again focus on computing the number of essential boolean parameters g = (g_a, g_b, g_c, g_d), where each g_i is a non-degenerate monotone boolean function, that support a particular type of a steady state. The types we are interested in include all-high (1111) and all low (0000) states, as well as states with one (1000), two (1100) or three (1110) active components. Poset of all MBFs with three inputs in Fig. 4c has 20 functions with 9 non-degenerate MBF marked in blue^6,24.

We now summarize results from⁸.

We first note that, similarly to toggle triad, the only parameters that support constant equilibria (0000) and (1111) are (0, 0, 0, 0) and (1, 1, 1, 1), respectively. Further, by symmetry for every parameter supporting equilibrium (1000) there is a parameter that supports equilibrium (0111), since the logic parameter functions are simply negated.

Therefore we only need to consider equilibria of type 3–1 where three genes have different expression levels than the fourth gene and the equilibria of type 2–2 where two genes are active and two are inactive. Similar analysis to the one for toggle triad gives the following.

Theorem 0.1

(⁸) Out of total of 9⁴ = 6561 essential boolean parameters, there are

• $2\,\ast\,2\,\ast\,2\,\ast\,9=72$ essential boolean parameters that support any 3–1 equilibrium.

• 7⁴ = 2401 essential boolean parameters that support any 2–2 equilibrium.

As discussed in detail in ref. ⁸ significantly higher prevalence of 2–2 equilibria than prevalence of 3–1 equilibria may indicate that the direct differentiation from precursor cell into individual cell types, represented by a 3–1 state, is less likely that a two step differentiation, where in the first step cells attain a mixed state represented by a 2–2 equilibrium, followed by a subsequent differentiation to individual cell types.

Connecting parameter graph ${\mathsf{PG}}$ to ODE models

The switching system dynamics^{3,10,31,32,33,34,35,36,37,38,39} associated to a regulatory network ${\mathsf{RN}}$ is a system of ordinary differential equations

$${\dot{x}}_{i}={\Lambda }_{u}(x)-{\gamma }_{i}{x}_{i},\quad i\in V$$

(6)

where $x={({x}_{i})}_{{v}_{i}\in V}\in {{\mathbb{R}}}_{+}^{n}$, ${\gamma }_{i}\in {\mathbb{R}}$ is the decay rate of x_i, and Λ_i is a piecewise constant function which captures the effect of the sources S(i) on the node i. The function Λ = (Λ₁, …, Λ_n) is defined for parameter $p=(g,\theta )\in {\mathcal{P}}$ as follows.

• 1. We associate a continuous variable x_i to each node v_i ∈ V.

• 2. We associate a threshold values θ_ji, j ∈ T(i) to each edge i⊸j and assume that these thresholds are distinct θ_ji ≠ θ_ki for any j, k ∈ T(i).

• 3. The thresholds θ_ji form a rectangular grid $G:=\{x\in {{\mathbb{R}}}_{+}^{N}\ | \ x={\theta }_{ji},\,u\in V,\,j\in {\bf{T}}(i)\}$. The set ${{\mathbb{R}}}_{+}^{n}\setminus G$ is a collection of a finite number of open domains${\mathcal{D}}$ where $x\in {\mathcal{D}}$ if all components of vector x lie between the thresholds. Observe that a collection of all domains ${\mathcal{D}}$ is in one-to-one correspondence with space ${\mathcal{C}}$. This is expressed via a map

  $$\varphi (x):{{\mathbb{R}}}_{+}^{n}\setminus G\to {\mathcal{C}}\qquad x\,\mapsto\, ({k}_{1},\ldots ,{k}_{n}),$$

  where k_i is an integer k_i ∈ X_i such that k_i < x_i < k_i + for all i. This map associates to each $x\in {{\mathbb{R}}}_{+}^{n}\setminus G$ a signature $c\in {\mathcal{C}}$ of its domain $d\in {\mathcal{D}}$.

• 4. Then we set

  $${\Lambda }_{i}(x):={\gamma }_{i}{f}_{i}({\varphi }_{i}(x))={\gamma }_{i}{g}_{i}(B({\varphi }_{i}(x)))$$

  (7)

In an open domain $d\in {\mathcal{D}}$, the function Λ is constant and the flow of (6) is directed toward the target pointΛ(x). All trajectories in d are straight lines towards the target point. If the target point is contained in d then the target point is an asymptotically stable fixed point of (6). If the target point is not in d, then the trajectories continue in a straight line until they hit the boundary of d. For a generic set of initial condition in d, trajectory hits a co-dimension one boundary of d where x = θ_ji for single threshold of θ_ji. If j ≠ i, then the sign of ${\dot{x}}_{i}$ does not change at x_i = θ_ji and the trajectory can be extended by continuation into a new domain $d^{\prime}$. If i = j and the edge ${i}\dashv {j}$ is repressing, then it is possible the sign of ${\dot{x}}_{i}$ may change on x_i = θ_ii. However, since only one component of Λ changes at θ_ii, all the components of the vector field Λ_k(x), k ≠ i remain the same between d and $d^{\prime}$. Therefore a sliding motion along the hyperplane x_i = θ_ii between d and $d^{\prime}$ is well defined. As a consequence, if the target point of d does not lie in d, for generic set of initial conditions in d, the solutions can be continued to some neighboring domain $d^{\prime}$. This observation has been used in ref. ² to define state transition graphs even for systems with negative self-edges.

This description shows that the dynamics of (6) are well defined for every parameter $p=(g,\theta )\in {\mathcal{P}}$ and determined by the target point function f = g ∘ B, see eq. (4). Furthermore it is easy to see that the trajectories of (6) that exit domain d may enter any domaing ${\mathcal{F}}(d)$. Therefore transition of the state transition graph defined by ${\mathcal{F}}$ capture all possible transitions by solutions of (6). It follows, that the Morse nodes denoted by ${\mathsf{FP}}$ of ${\mathsf{MG}}$ contain fixed points of ODE system (6) and any Morse node ${\mathsf{PC}}$ or ${\mathsf{FC}}$ has a potential to contain periodic solutions of (6).

The precise correspondence between invariant sets of (6) which are central objects in study of dynamical systems⁴⁰ and the Morse nodes is complex and beyond the scope of this paper¹¹. The ongoing current work aims to show that the Morse graph recovers Morse decomposition of a wide class of smooth ordinary differential equations that are approximated by the switching system (6). We describe briefly the main ideas for a restricted class of functions, where Λ has a form of product-of-sums^41,42,43,44 and which have been used extensively in DSGRN^3,5,26,27. In product-of-sums systems, the functional form for Λ_u is restricted to be a product of sums of switching functions

$$\begin{array}{r}{\Lambda }_{i}(x)=\prod \sum\limits_{j\in {\bf{S}}(i)}{\sigma }_{ij}({x}_{j})\qquad {\sigma }_{ij}({x}_{j}):=\left\{\begin{array}{ll}{L}_{ij}\quad \quad &{\rm{if}}\,{\delta }_{ij}({x}_{j}-{\theta }_{ij}) \,<\, 0\\ {U}_{ij},\quad \quad &{\rm{if}}\,{\delta }_{ij}({x}_{j}-{\theta }_{ij}) \,>\, 0\end{array}\right.\end{array}$$

(8)

where 0 < L_ij < U_ij are the lower (L) and upper (U) values for the effect of v_j on v_i. The advantage of the product-of-sums description for Λ is that the parameters L and U are easy to interpret in applications.

In particular, for every function σ_ij there is a sequence of Hill functions, parameterized by the Hill parameter n, of the form

$${h}_{ij}^{n}({x}_{j}):={L}_{ij}+({U}_{ij}-{L}_{ij})\frac{{x}_{i}^{n}}{{\theta }_{ij}^{n}+{x}_{j}^{n}}$$

(9)

such that

$$\mathop{\lim }\limits_{n\to \infty }{h}_{ij}^{n}(x)={\sigma }_{ij}(x)\qquad {\rm{pointwise.}}$$

This allows comparison between ODE system with Hill functions and switching systems. Since the repertoire of long-term dynamics of switching system associated to a network ${\mathsf{RN}}$ is determined by collection of Morse graphs, parameterized by all multi-valued MBFs in parameter graph ${\mathsf{PG}}$, DGSRN provides a bridge between continuous dynamics of networks and combinatorial, finite collection of Morse graphs in ${\mathsf{PG}}$.

There is numerical evidence that DSGRN successfully predicts dynamics of ODE network dynamics^8,12. In ref. ¹², the results from DSGRN computation of equilibria were compared to results from RACIPE⁹ approach that samples parameters of Hill function network models and then runs the ODE simulations. In particular, ref. ¹² examines at what value of Hill coefficient n the RACIPE and DSGRN results start to agree. Surprisingly, DSGRN predicts RACIPE results even for relatively small values of n. The paper⁸ considers toggle tetrahedron network which has 27 trillion DSGRN parameters which is too large for exhaustive computation. We hasten to add that computations involving several billion of parameters can be computed on a laptop in matter of hours. Two alternative approaches have been used. In one, four random samples of 10,000 DSGRN parameters from the set of all DSGRN parameters were selected and examined for different types of equilibria and different types of multistability. In the second approach the collection of all 6561 essential boolean parameters have been examined. We compared results from both of these approaches to results from RACIPE samples and again, we found good agreement between all three measurements. This is surprising as the essential Boolean parameters represents a tiny slice of the parameter space, yet it seems to predict well behavior of the network over a entire parameter space.

Since the DSGRN analysis is computationally many orders of magnitude faster that RACIPE this suggests that DSGRN is a valuable tool for the first pass analysis of the range of behaviors that the network is able to support.

Discussion

Cellular regulatory networks describe directed pairwise interactions between genes and proteins. Some small networks seems to occur statistically more frequently that others⁴⁵, which suggests that they are subject to evolutionary selection. The role of cell regulation is to dynamically respond to changes in the environment and thus dynamics supported by the regulatory networks is related to cell’s fitness. It is therefore important to understand dynamics that these networks can support. Accordingly, theory of motifs^46,47 suggested that a particular dynamics of the motifs is responsible for their overrepresentation within the set of cellular networks. However, any model of network dynamics depends on choice of parameters which represent mathematically different environmental resources, external signals as well as internal resources like number of ribosomes. Since these are difficult to measure in individual cells, it is natural to try to examine the entire range of dynamical behaviors that the network can support.

We have reviewed recent progress on the problem of describing range of dynamics supported by a network. We concentrate here on description of equilibria, or steady states, rather than more dynamic behaviors like periodic attractors. We show that there is natural connection between network models consisting of collections of multivalued monotone boolean functions and models using ordinary differential equations. These mMBFs are organized in a parameter graph ${\mathsf{PG}}$. This structure allows us to start from a small subset of essential boolean parameters, examine dynamics at these parameters, and then explore the neighborhood of these parameters.

We examine three example networks where we discuss prevalence of different equilibria within the set of essential boolean parameters.

Our approach provides a new tool to answer the questions about range of dynamics a network may exhibit across different conditions. If this range does not include experimentally observed dynamics, the network is likely incomplete. When network does exhibit observed dynamics, its prevalence within ${\mathsf{PG}}$ may be used to rank the networks and focus experimental efforts^1,2,48, and reduce the set of potential hypotheses.