betaFeedback

WorksAgricultural and Biological Sciences

Dynamical Modularity in Automata Models of Biochemical Networks

Abstract

Given the large size and complexity of most biochemical regulation and signaling networks, there is a non-trivial relationship between the micro-level logic of component interactions and the observed macro-dynamics. Here we address this issue by formalizing the existing concept of pathway modules, which are sequences of state updates that are guaranteed to occur (barring outside interference) in the dynamics of automata networks after the perturbation of a subset of driver nodes. We present a novel algorithm to automatically extract pathway modules from networks and we characterize the interactions that may take place between modules. This methodology uses only the causal logic of individual node variables (micro-dynamics) without the need to compute the dynamical landscape of the networks (macro-dynamics). Specifically, we identify complex modules, which maximize pathway length and require synergy between their components. This allows us to propose a new take on dynamical modularity that partitions complex networks into causal pathways of variables that are guaranteed to transition to specific states given a perturbation to a set of driver nodes. Thus, the same node variable can take part in distinct modules depending on the state it takes. Our measure of dynamical modularity of a network is then inversely proportional to the overlap among complex modules and maximal when complex modules are completely decouplable from one another in the network dynamics. We estimate dynamical modularity for several genetic regulatory networks, including the Drosophila melanogaster segment-polarity network. We discuss how identifying complex modules and the dynamical modularity portrait of networks explains the macro-dynamics of biological networks, such as uncovering the (more or less) decouplable building blocks of emergent computation (or collective behavior) in biochemical regulation and signaling.

macro-dynamics of biological networks, such as uncovering the (more or less) decouplable building blocks of emergent computation (or collective behavior) in biochemical regulation and signaling.

Introduction

Biological intracellular networks are often composed of modules that are formed from molecular components and perform a specific function within the cell [2, 3, 4, 5, 6, 7]. These separable components are thought to provide the biological organism with robustness to environmental perturbations and genotypic mutations while still allowing enough flexibility for evolution [8, 9, 10] [11]. Though this kind of modularity is a general and intuitive concept, there are many formal definitions and it is not clear how to best model this phenomenon in living systems.

A popular method to model biological systems is with discrete dynamic network models because they are simple to understand and do not rely on the estimation of kinetic parameters (unlike continuous models such as ordinary differential equations) [12, 13]. The network nodes (automata) typically represent genes, transcripts, proteins, molecular species, external inputs, or other qualitative states affecting the biological cell, and they are connected to one another by an edge if they interact in some way. Automata can take any number of discrete states, but the simplest example is Boolean automata which are in one of two states at any given time [14, 15, 16]. These models are often applied to intracellular signaling networks because they can recreate phenotypical states using discrete variables, while ignoring kinetic details.

Even given a simple model like a Boolean network (BN), it is unclear how to optimally decompose the system into separable modules. Furthermore, networks observed in the real-world may contain a large number of nodes and interactions and be arbitrarily complex. Although the interactions between components in such a BN are well defined, it is unclear how the individual node interactions give rise to global properties of the network such as its modularity or attractor landscape. It is, therefore, useful to understand how the micro-dynamics of component interactions give rise to the macro-dynamic behavior observed in networks.

Modularity methods have become a standard approach to decompose graphs and solve problems such as community detection. These approaches typically focus on topological modules, where a module is defined by a higher density of links between nodes in the same module and a lower density of links to nodes in different modules [17, 18]. Such structural modularity measures ignore the dynamical information of the network and may, therefore, be limited when it comes to discovering functional modules [19, 20]. It has also been shown that relying on structural information alone cannot account well for dynamics in control problems on BNs [21]. Additionally, the same circuit topologies in biological systems can switch between distinct steady states and dynamical behaviors (multi-stability and multifunctionality), which indicates that there is not a clear relationship between structure and function [22].

For these reasons, dynamical modularity measures have also been proposed. Irons et al. proposed a method to decompose BNs into dynamical modules based on attractors of the system without the details of the underlying network, although with a suitable mathematical model the method can also determine how robust the subsystems are and how they are regulated [23]. Kolchinsky et al. proposed a method based on the idea that modules constrain the spread of perturbations and defined perturbation modularity as the autocovariance of perturbed trajectories [24]. Other methods combine structural and dynamical approaches by decomposing a network into structural components and associating these components with dynamical properties [25, 26]. Zañudo and Albert decompose an expanded version of a BN (taking into account its dynamics) into stable motifs, which are strongly-connected components representing partial fixed points of the system. They show that controlling these motifs can drive a network to a desired attractor [27].

We use the threshold network representation of automata network dynamics proposed by Marques-Pita and Rocha, the dynamics canalization map (DCM), which represents both Boolean states of every node. They simplified the description of a network’s dynamics by explicitly removing redundancy in the logical expressions governing each node’s update (described in the following subsections). This redescription allows to describe dynamical modularity, critical nodes that guarantee convergence to steady states (with incomplete knowledge of initial conditions), and measures of macro-level canalization [1]. Using the DCM, they identified the dynamical modules on the Drosophila melanogaster single-cell segment polarity network (SPN) [28] that are controlled by the network’s inputs.

Here we formally define modules on the DCM. We expand the analysis of [1] by finding such modules not just for the inputs but for all possible nodes and low-order interactions on the drosophila segment polarity network (SPN). We develop theoretical results to explain the interaction of different dynamical modules and define synergy between modules. The concept of synergy is used to define a subset of modules, called complex modules, that capture all unique dynamical information in the BN.

We then use complex modules to define a measure of dynamical modularity for BNs. This measure is driven purely by the network’s dynamics rather than its structure. Unlike other measures, our dynamical modularity measure differentiates between different states of a variable. It accounts for the fact that a single variable may be part of multiple functional modules depending on its behavior and thus may be useful in models of multifunctionality in biological systems. Additionally, our measure makes explicit the influence of each variable in each state and the control that a given variable has on the rest of the network. We also use the mean dynamical modularity of a network to quantify its decomposability and use this metric to compare different biological networks.

This paper is organized as follows: In the remainder of the Introduction, we give some background on schematic redescription, canalyzing maps, and the DCM introduced in [1]. In section II, we give theoretical results concerning the formal definition of pathway modules (based on the perturbation of seed nodes), complex modules (which have synergy between seed nodes and are of maximal size), and dynamical modularity (based on an optimal partition of the DCM). In section III, we apply our methodology to the drosophila single-cell and parasegment SPN to find complex modules on these networks, quantify their dynamical modularity, and compare them to other biological networks of comparable size. In section IV, we offer our conclusions and note some limitations to our methodology.

Boolean Networks

A Boolean automaton xx can be in one of two states, x∈{0,1}x \in\{0,1\} (traditionally ON or OFF, representing activation of the molecule of interest above or below a certain threshold) [14, 15, 16]. The state of an automaton is updated in discrete time steps governed by a logical function of its inputs (e.g., A=B∨CA = B \lor C). More formally, xt+1=f(x1t,…,xkt)x^{t+1} = f(x_1^t,\ldots,x_k^t) for automaton xx with kk inputs at time step tt, where the mapping f:{0,1}k→{0,1}f : \{0,1\}^k \to\{0,1\} can be read from the automaton’s look-up table FF that denotes the output xt+1x^{t+1} for each of its 2k2^k input combinations (refer to Figure 1).

A BN is a graph B=(X,E)B = (X,E) where XX is a set of nn Boolean automata nodes and EE is a set of directed edges ei,j∈Ee_{i,j} \in E that indicate that node xix_i is an input to node xjx_j [14, 29]. The configuration of a BN is the value of all automata states x∈Xx \in X. Automata nodes within the network may be updated synchronously in discrete time steps or asynchronously, where each node has a different update schedule (deterministic asynchronous BNs) or is selected at random with some probability [30, 29]. Deterministic BNs are guaranteed to eventually resolve in some attractor, either a fixed point or a limit cycle of repeating states. In biological networks, attractors are typically associated with some phenotype (such as a wildtype expression pattern) [16].

Node canalization

Canalization refers to the ability of a subset of inputs to control an automaton’s transition [1] [31, 32, 33, 34, 21, 35]. The Boolean transition function of the automaton is thus satisfied by this subset of inputs and the logical states of its other inputs can be ignored. This shows inherent redundancy in the transition function that can be removed via schematic redescription, a process introduced in [1]. The Quine-McCluskey Boolean minimization algorithm is used to reduce an automaton’s look-up table FF to a set of prime implicants [36] that are then combined to form a set of wildcard schemata F′F^\prime. Within the wildcard schemata only essential inputs (enputs) are defined as ON or OFF. Every other input is replaced with the wildcard symbol (#) which indicates that those inputs are redundant (given the states of the enputs) and do not affect the automaton’s state transition [1]. Additionally, permutations of inputs that leave the transition unchanged are marked with a position-free symbol (°) and combined to form group-invariant enputs. This captures the input-symmetry within the wildcard schemata and further reduces them to a set of two-symbol schemata without permutation redundancy F′′F^{\prime\prime} (see Figure 1). It is not surprising to find input redundancy and input-symmetry at the automaton level (known as micro-canalization) in biological networks because they are known to be robust, which buffers perturbations to individual inputs and can help maintain wildtype phenotypes [10] [37, 33].

After all redundancy is removed, the necessary and sufficient logic of automata nodes can also be represented by a canalyzing map (CM) [1], a type of threshold network [38]. The CM of a variable xx represents all logical transitions (two-symbol schemata) that can result in an update of the state of xx. It is composed of s-units which represent nodes (xx and its inputs) in a particular discrete state (e.g., ON or OFF), t-units that implement the transition function of xx via thresholds, and fibres that connect s-units and t-units together. A fibre may connect one s-unit to one t-unit (indicating that the s-unit sends one signal to the t-unit), or multiple fibres may be merged together so that several s-units send one signal to a t-unit (representing permutation redundancy). T-units have a threshold value τ\tau and only fire if they receive at least τ\tau simultaneous incoming signals from s-units; s-units fire if they receive any incoming signal from a t-unit. All logical interactions between xx and its inputs are represented such that each t-unit corresponds to one schema in F′′F^{\prime\prime}. Thus the CM is equivalent to the schemata necessary to ensure the logical transition from xtx^t to xt+1x^{t+1} (see Figure 1).

Example automaton with a logical ‘OR’ transition function

Figure 1. Example automaton with a logical ‘OR’ transition function. Left: The node x has two inputs. Center: The look-up table F describing the transition of x and the one and two-symbol schemata redescription (F′F' and F′′F''; # is a wildcard enput, o is a group-invariant enput). Right: The CM for x with the associated logical function representing both state updates. Black s-units represent nodes in their ON state, white s-units represent nodes in their OFF state, and blue diamonds represent t-units labeled with their threshold value (τ\tau). Each edge (fibre) represents the logical contribution of a source unit to an end unit and thus dictates how X will turn ON or OFF. The CM shows that one ON input is sufficient to turn X ON but that two OFF inputs are needed to turn X OFF.

Dynamics canalization maps

The canalyzing map of each automaton can be be integrated into a larger threshold network called the DCM [1]. This parsimonious network, with input and symmetry redundancy removed, represents the control logic and dynamics of the entire BN. Each possible state of each variable is represented in the DCM; thus there are 2n2n s-units for a BN of size nn and t-units that represent each schema, as defined for each individual CM.

Because the DCM captures the state updates of all automata in the network, it is possible to determine a logical sequence of signals based on the deterministic firing of s-units and t-units. Given an initial set of s-units (and barring any outside interference), a logical sequence of state updates is guaranteed to occur based on the logic embedded in the schema F′′F'' and represented by the t-units in the DCM. This sequence of state updates is referred to as a pathway module because it is a sequence of s-units and t-units firing in the DCM and the state updates occur independently of all other node states that are not involved in the firing of t-units [1].

Importantly, the initial conditions of a pathway module may only define the state of a (small) subset of nodes in the network, while the complement of this set is assumed to be in an unknown state (represented by ‘#’). These known and unknown node states are referred to as a partial configuration x^\hat{x} of the network. Because dynamics are deterministic, this partial configuration causes a sequence of state updates (which we refer to as dynamical unfolding) that results in an outcome configuration PP, which may be either another partial configuration or an attractor of the network. If PP is an attractor then we know that x^\hat{x} controls the full network dynamics because the attractor is guaranteed to occur based on the subset of known s-units in the initial condition if the initial node states are sustained [1]. Thus, we can compute global (macro-scale) dynamical information from only partial knowledge of the network configuration by integrating knowledge of the local (micro-scale) dynamics.

We note that the calculation of dynamical unfolding is similar to the calculation of partial steady states in the logical interaction hypergraph [39], cascading effects of node removal and the calculation of elementary signaling modes on the expanded network [40], and calculation of the logical domain of influence on the expanded network [41]. However, none of these methods explicitly remove input symmetry from the transition functions of nodes or consider different types of node perturbation.

In the next section we give a formal treatment of pathway modules and provide definitions of novel concepts such as pathway module interaction, complex modules, and measures of dynamical modularity.

Formal results

Pathway modules can be discovered using a breadth-first search algorithm on the DCM starting from the initial seeds. However, unlike a search on a traditional graph, the different types of units on the DCM must be considered. For a t-unit to be included, its threshold τ\tau must be met. Furthermore, the threshold is met only if its inputs fire simultaneously; therefore, the firing of a t-unit with multiple inputs requires confidence that all of its inputs can fire at the same time. If the initial seeds are pinned (not allowed to change), then they fire at every time step and all downstream s-units fire repeatedly as well. However, if the initial seeds are only perturbed once (pulse perturbation), then their future state cannot be guaranteed after time t=0t = 0. The type of initial perturbation, therefore, affects the pathway module that unfolds on the DCM.

Example GRN showing the interaction graph and DCM

Figure 2. Example GRN. The interaction graph is shown on the left, the DCM on the right. This network has two inputs (i1,i2i_1,i_2), two genes (g1,g2g_1,g_2), and two proteins (P1,P2P_1,P_2). There is a negative feedback loop present as P1P_1 promotes the creation of P2P_2, an inhibitory protein. P1P_1 requires both g1g_1 and the absence of P2P_2, while P2P_2 requires both g2g_2 and i2i_2. The exact logic of the dynamics is captured in the DCM, where black s-units represent nodes in their active (ON) state, white s-units represent nodes in their inactive (OFF) state, and grey diamonds represent t-units. The seeds of pathway modules MP2−1M_{P_2-1} and Mi1−0M_{i_1-0} are indicated by double edges; the pathway module Mi1−0M_{i_1-0} is shown in blue. Note that t-units with τ=1\tau= 1 and no permutation redundancy are left out of the DCM for simplicity.

As an example, consider the case of the engrailed (en) protein from the drosophila SPN (see Fig. 3). If en is perturbed to ON for only a single time step, the subsequent pathway module takes four time steps to unfold (panel a). However, if en is constitutively active, then the resulting pathway module takes six time steps to unfold and reaches two extra node states (hhhh-1 and HH-1), which can fire because the logical condition for hhhh-1 (hht+1=ENt∧¬CIRthh_{t+1}=EN_t \land\neg CIR_t) is satisfied by the ongoing firing of EN-1 (panel b). Perturbations may be more complicated than these two extremes of pulse or pinning perturbation. For example, an s-unit may be fired in kk time step intervals or may be controlled for a specific length of time and then released.

It is also important to factor logical contradiction into the search algorithm when determining pathway modules. If an s-unit representing the state of variable xx fires at time tt, then an s-unit representing a different state of $x cannot also fire at time tt. For pinning perturbation, this guarantees that only one state of any variable is ever reached, while for pulse perturbation s-units representing different states of xx may fire. The consequence of this is that modules based on pinning perturbation may uncover fixed points in the network but not limit cycles.

Two heatmaps showing the dynamical unfolding of pathway module $\mathrm{M}_{\mathrm{en}-1}$ under pulse and pinning perturbations

Figure 3. Example of different perturbations in the drosophila SPN. Black represents nodes in their active (ON) state, white represents nodes in their inactive (OFF) state, and grey represents nodes whose state is unknown. (a) The dynamical unfolding of the pathway module Men−1\mathrm{M}_{\mathrm{en}-1} in the drosophila single-cell SPN under pulse perturbation. Node states are not maintained over time, and as a result, cannot activate hhhh or HH which require the activation of EN. (b) Men−1\mathrm{M}_{\mathrm{en}-1} unfolding under pinning perturbation. The s-units hhhh-1 and HH-1 fire due to the ongoing activation of EN.

In the example GRN in Fig. 2, the module Mi1−0\mathrm{M}_{\mathrm{i1}-0} includes the same s-units (g1-0, P1-0, g2-0, and P2-0) and t-units (not shown in the figure), regardless of perturbation type. The module MP2−1\mathrm{M}_{\mathrm{P2}-1}, however, includes the s-units P1-0, g2-0, and P2-0 under pulse perturbation but only P1-0 and g2-0 under pinning perturbation (because P2-0 is a logical contradiction to P2-1).

Multiple pathway modules may simultaneously unfold within the complex dynamics of a network. Thus, it is natural to explore how different pathway modules may interact, assuming that their initial conditions are simultaneously activated. This leads to concepts such as independence, logical obstruction, and synergy. Synergy is used to define complex modules, which are maximal pathway modules whose seeds have synergy between them; complex modules are further used to define the dynamical modularity of the network. Formal definitions of these concepts are given in the following subsections.

Defining Pathway Modules

The definition of the DCM is provided in the Introduction. Formally, let XX be the set of all nodes in an automata network BB and SS be the set of all s-units in the DCM (which represents all node states) of BB. For Boolean networks, ∣S∣=2∗∣X∣|S| = 2 \ast|X|. Let Θ\Theta be the set of all threshold units in the DCM (its size ∣Θ∣|\Theta| depends on the number of redescribed schemata for each node in BB). At any given time tt, a set of s-units, St⊂SS^{t} \subset S, and a set of t-units, θt⊂Θ\theta^{t} \subset\Theta, fire in the DCM. A t-unit fires at time tt if its logical conditions are met (determined by its threshold value τ\tau), causing its neighboring s-unit to fire at time t+1t+1. The firing of a t-unit means that there is sufficient information to satisfy a schema in the look-up table of the variable associated with the downstream s-unit. The output state of this schema is the state associated with the s-unit (i.e., 0 or 1). An s-unit fires if its predecessor (a t-unit) fires; when it fires, it sends signals to all of its neighboring t-units. An s-unit may also fire at time tt due to an external signal, i.e., a perturbation that is applied to that node variable of BB. Such a signal can immediately trigger downstream t-units to fire if their logical conditions are met. In other words, while signals from t-units to s-units propagate with a one time step delay (dt=1dt = 1), signals from s-units to t-units propagate immediately (dt=0dt = 0) $1. This asymmetry guarantees that the original dynamics of state transitions in BispreservedintheDCM.Here,wedenotethestateofaBooleanvariableis preserved in the DCM. Here, we denote the state of a Boolean variablexbybyx_{-1}ififxisONandis ON andx_{-0}ififx$ is OFF.

There is an important constraint on the set StS^{t} of s-units that fire at time tt. If an s-unit that represents the state of xx fires at time tt, the s-unit that represents the negation of the state of xx cannot fire. Thus, x−1∈St⟹x−0∉Stx_{-1} \in S^{t} \Longrightarrow x_{-0} \notin S^{t} and vice versa. SitS_i^{t} represents a partial configuration whereby the logical state of the corresponding node variables x∈Xx \in X is known, but any other variable may be in either state (ON or OFF). The number of (full) configurations that a partial configuration StS^{t} describes is 2∣X∣−∣Sit∣2^{|X|-|S_i^{t}|}. As a corollary, max⁡(∣Sit∣)=∣X∣\max(|S_i^{t}|) = |X| denotes the situation when the logical state of all variables is known, and we know the precise configuration the network is in at time tt.

A seed set is a set of s-units S0⊂SS^{0} \subset S that, without loss of generality, are assumed to fire at time t=0t = 0. This functions as an external perturbation applied to a subset of variables X0⊂XX^{0} \subset X of network B. Note that these s-units can represent variables in either the ON or OFF states.

Canalized dynamics is represented by a function μ(St)→St+1\mu(S^{t}) \to S^{t+1}, whereby the set of s-units StS^{t} that fire at time tt transition to another set of s-units that fire at time t+1t + 1. Naturally, this function can be applied sequentially for t=0,1,…,∞t = 0, 1, \ldots, \infty, which we refer to as dynamical unfolding (see below). Note also that St+1∩St≠∅S^{t+1} \cap S^{t} \ne\varnothing if any s-units in StS^{t} fire again due to external perturbation, regulation by other members of StS^{t}, or self-reinforcement. Importantly, unlike the computation of dynamics in the original Boolean network B, dynamical unfolding in the DCM via μ\mu is typically computed with no information about the logical state of many variables. This is possible because the schemata redescription of logical functions introduces the wildcard and position-free symbols.

S0S^{0} can be treated differently in the dynamical unfolding process. When studying pulse perturbations, s-units s∈S0s \in S^{0} are assumed to fire only at t=0t = 0, unless the logic of the canalized dynamics (μ\mu) leads them to fire again. In contrast, pinning perturbations lock the s-units s∈S0s \in S^{0} into firing at every time step tt.2 In this case, we always have St⊂St+1S^{t} \subset S^{t+1} in the canalized dynamics. Unless otherwise noted, we use pinning perturbation, which represents situations where the perturbation signal is assumed to be in steady-state and last much longer than the transient dynamics that it affects. This is a realistic scenario, especially for gene regulatory network models.

A module in the DCM is defined as Mt≡(St,θt)M^{t} \equiv(S^{t}, \theta^{t}). It is a tuple consisting of a set of s-units St⊂SS^{t} \subset S and t-units θt⊂Θ\theta^{t} \subset\Theta that fire at time tt due to a perturbation applied to seed set S0S^{0} at t=0t = 0. For convenience we define set operations on modules by applying the operation to both elements of the tuple. Thus, Mit⊂MjuM^{t}_{i} \subset M^{u}_{j} if and only if Sit⊂SjuS^{t}_{i} \subset S^{u}_{j} and θit⊂θju\theta^{t}_{i} \subset\theta^{u}_{j}, for modules MiM_i and MjM_j at time steps tt and uu. Other operators, such as union and intersection, are defined similarly.

Modules dynamically unfold in time via the function μ(St)→St+1\mu(S^t) \to S^{t+1} until a time t=Tt = T when the module either repeats (MT≡Mt<TM^T \equiv M^{t<T}) or is empty (MT≡(∅,∅)M^T \equiv(\varnothing, \varnothing)) because no s- or t-units can logically fire with the known information. This leads to a pathway module, a time-ordered sequence of all modules that unfold due to a perturbation given by seed set S0S^0: M(S0)=[M0,M1,…,MT]M(S^0) = [M^0, M^1, \ldots, M^T] for all time steps t≤Tt \le T.

In turn, the pathway module set includes all s-units that fire in at least one module Mt∈M(S0)M^t \in M(S^0), and is defined as S=S0→T=⋃t≤TStS = S^{0\to T} = \bigcup_{t\le T} S^t. Under pulse perturbation (or other perturbation types), not all elements of SS are guaranteed to fire at time TT. However, in the case of pinning perturbation, S=ST=S∞S = S^T = S^\infty, since St⊂St+1S^t \subset S^{t+1}.3 The length of a pathway module M(S0)M(S^0) is TT, whereas its size is simply the cardinality of its corresponding pathway module set ∣S∣|S|. Finally, PsP_s denotes the set of all pathway modules M(S0)M(S^0) that unfold in a DCM from seed sets of size s=∣S0∣s = |S^0|.

Interaction of pathway modules

Given that there is an exponential number of pathway modules, for computational purposes we must narrow down the possible dynamical interactions of the system. Therefore, we define how pathway modules may interact to hone in on those that best define the computational dynamics of the network. Specifically, we consider that two pathway modules MiM_i and MjM_j can be combined by considering the dynamical unfolding of the union of their seed sets, Mi,j=μ(Si0∪Sj0)M_{i,j} = \mu(S_i^0 \cup S_j^0).4

Pathway module MiM_i is subsumed by MjM_j if Si⊂SjS_i \subset S_j. MiM_i is partially subsumed by MjM_j if Si∩Sj≠∅S_i \cap S_j \ne\varnothing but Si⊄SjS_i \not\subset S_j (i.e., there is some overlap between the dynamical unfolding of the two modules). MiM_i is temporally subsumed by MjM_j if there exists a k≥0k \ge0 such that Mit⊂Mjt+kM_i^t \subset M_j^{t+k} for all $t \le T (the sequence is preserved temporally, where constant k≥0k \ge0 indicates that the dynamical unfolding of the subsequence Mi\mathrm{M}_i within Mj\mathrm{M}_j begins kk time steps after t=0t = 0).

Pathway module Mi\mathrm{M}_i is a submodule of Mj\mathrm{M}_j if Si0⊂Sj0S_i^0 \subset S_j^0 and Si0≠∅S_i^0 \ne\emptyset. Note that when Mi\mathrm{M}_i is a submodule of Mj\mathrm{M}_j, it does not imply that Mi\mathrm{M}_i is subsumed by Mj\mathrm{M}_j due to the possibility of logical obstruction (see below).

Pathway module Mi\mathrm{M}_i is considered maximal if it cannot be temporally subsumed by any other pathway modules with the same seed set size. For pinning perturbation, Si0⊄Sj0S_i^0 \not\subset S_j^0 for all pathway modules Mj\mathrm{M}_j with seed set size ∣Sj0∣≤∣Si0∣\lvert S_j^0\rvert\le\lvert S_i^0\rvert. In other words, μ(Si0)\mu(S_i^0) results in a unique set of s-units that cannot be obtained from dynamically unfolding any other pathway module with the same seed set size. Λs⊂Ps\Lambda_s \subset P_s is the set of all maximal pathway modules with seed set size ss.

Logical obstruction exists between pathway modules Mi\mathrm{M}_i and Mj\mathrm{M}_j if their combination Mi,j\mathrm{M}_{i,j} results in an s-unit not firing during time step t=kt = k when that s-unit does fire in either pathway module Mi\mathrm{M}_i or Mj\mathrm{M}_j at time t=kt = k. For pinning perturbation, this situation occurs when μ(Si0)∪μ(Sj0)−μ(Si0∪Sj0)≠∅\mu(S_i^0) \cup\mu(S_j^0) - \mu(S_i^0 \cup S_j^0) \ne\emptyset. In cases where there is also no synergy between Mi\mathrm{M}_i and Mj\mathrm{M}_j (see below), μ(Si0∪Sj0)⊂μ(Si0)∪μ(Sj0)\mu(S_i^0 \cup S_j^0) \subset\mu(S_i^0) \cup\mu(S_j^0).

Logical obstruction can only occur when the union of the seed sets results in a logical contradiction whereby s-units for the state of at least one node variable and its negation are both included (in the seed sets or their dynamical unfolding logic), for example, x−1∈Si0∧x−0∈Sj0x_{-1} \in S_i^0 \land x_{-0} \in S_j^0. This means that combining the pathway modules results in one or more s-units not firing that would have fired had the pathway modules been separate.

Synergy exists between pathway modules Mi\mathrm{M}_i and Mj\mathrm{M}_j if their combination Mi,j\mathrm{M}_{i,j} results in an s-unit (or t-unit) firing during time step t=kt = k when that s-unit (or t-unit) does not fire in either pathway module Mi\mathrm{M}_i or Mj\mathrm{M}_j at time t=kt = k. For pinning perturbation we have: μ(Si0∪Sj0)−μ(Si0)∪μ(Sj0)≠∅\mu(S_i^0 \cup S_j^0) - \mu(S_i^0) \cup\mu(S_j^0) \ne\emptyset.

If there is no logical obstruction (see above) between Mi\mathrm{M}_i and Mj\mathrm{M}_j, then: μ(Si0∪Sj0)⊃μ(Si0)∪μ(Sj0)\mu(S_i^0 \cup S_j^0) \supset\mu(S_i^0) \cup\mu(S_j^0). This means that additional s-units fire as a result of combining the pathway modules.

Pathway modules Mi\mathrm{M}_i and Mj\mathrm{M}_j are decoupled if there is no partial subsumption (s-unit overlap), logical obstruction, or synergy between them. This means that μ(Si0∪Sj0)≡μ(Si0)∪μ(Sj0)\mu(S_i^0 \cup S_j^0) \equiv\mu(S_i^0) \cup\mu(S_j^0) and ∣μ(Si0∪Sj0)∣=∣μ(Si0)∣+∣μ(Sj0)∣|\mu(S_i^0 \cup S_j^0)| = |\mu(S_i^0)| + |\mu(S_j^0)| are necessary and sufficient conditions for pinning perturbation.

Pathway module Mi\mathbf{M}_i is a complex module if Mi∈Λs\mathbf{M}_i \in\Lambda_s and any submodule Mj\mathbf{M}_j of Mi\mathbf{M}_i is synergistic with the submodule Mk\mathbf{M}_k whose seed set is Sk0=Si0−Sj0S_k^0 = S_i^0 - S_j^0. For s=1s = 1, this means that all modules Mi∈Λ1\mathbf{M}_i \in\Lambda_1 are complex. We define Is⊂PsI_s \subset P_s as the set of all complex modules with seed size ss.

To be a complex module then, a pathway module must be maximal and every submodule (seed combination) within it must add synergy. For a given ss, each complex module Mi∈Is\mathbf{M}_i \in I_s represents the introduction of a unique firing sequence that is not part of any other pathway module with seed set size x≤sx \leq s (otherwise it would not be maximal) or any combination of pathway modules with seed set sizes x≤sx \leq s (because every submodule adds synergy). As a consequence, complex modules are the building blocks of a network’s dynamics. Importantly, complex modules allow the vast number of possible dynamical interactions to be reduced to a smaller set of unique signaling sequences that may represent (full or partial) biologically functional pathways.

Given a DCM, its complex modules are defined using only parameter ss, the size of the seed set. Moreover, the complex modules are hierarchical in the sense that modules with larger seed set sizes are composed of (partially or fully subsumed) modules with smaller seed set sizes. Higher-level complex modules thus capture the emergent behavior (e.g., synergy) that results from combining lower-level modules. For s=1s = 1, the set of complex modules I1=Λ1I_1 = \Lambda_1 is the minimal set of pathway modules that covers the DCM. However, synergy allows for the DCM to be covered using fewer pathway modules (with larger seed sets).

Possible interactions between pathway modules are demonstrated in Fig. 4. In this example network, module MP1−0\mathbf{M}_{P1-0} is subsumed by module Mi1−0\mathbf{M}_{i1-0} with either pinning or pulse perturbation (panel a). Thus, Mi1−0∈Λ1\mathbf{M}_{i1-0} \in\Lambda_1 is a maximal module, whereas MP1−0\mathbf{M}_{P1-0} is not. Modules MP1−1\mathbf{M}_{P1-1} and Mi1−1\mathbf{M}_{i1-1} are decoupled (dynamically independent) as they share no overlap or synergy, regardless of perturbation type (panel b). Module MP1−1\mathbf{M}_{P1-1} logically obstructs module MP2−1\mathbf{M}_{P2-1} with pinning perturbation as the pinning of P1 prevents the firing of P1-0 and the subsequent unfolding of MP2−1\mathbf{M}_{P2-1} (panel c). By contrast, there is synergy between the modules MP1−1M_{\mathrm{P1-1}} and Mi2−1M_{\mathrm{i2-1}} that results in the firing of P2−1P_{\mathrm{2-1}} (panel d). If the input i2i_2 is constant, but the node P1P_1 is not (pulse perturbation), several additional downstream ss-units will be reached. Panel e shows a limit cycle of the network reached by the combination of modules MP1−1M_{\mathrm{P1-1}}, Mi1−1M_{\mathrm{i1-1}}, and Mi2−1M_{\mathrm{i2-1}}. In this case, the inputs i1i_1 and i2i_2 are held constant but the node P1P_1 is not (pulse perturbation). Finally, all six complex modules of seed set size s=1s = 1 are shown, assuming pinning perturbation (panel f).

Dynamical Modularity

With the characterization of pathway module interaction and the introduction of complex modules, we may now characterize the macro-scale properties of the network, such as its organization and modularity. The concept of dynamical modularity is analogous to structural modularity in graphs, whereby it is considered to occur when interactions within modules are strong and interactions between modules are weak. Dynamical modularity is, however, a more general concept derived from Simon’s framing of complex systems in terms of near-decomposability [45], which includes both structural and dynamical interactions [46, 24, 21]. We use it to find subsets of variables and their dynamical states that are more or less easy to decouple in a given multivariate dynamical system. Thus, we can compare complex (dynamical) networks (or systems) to determine which ones are easier to decouple into independently-functioning parts.

The cover of a DCM is a set of pathway modules Π={Mi,Mj,…}\Pi= \{M_i, M_j, \ldots\} such that the union of their corresponding pathway modules sets is equivalent to the set of all ss-units in the DCM; that is, SΠ=⋃iSi=SS_{\Pi} = \bigcup_i S_i = S for set SiS_i with corresponding pathway module Mi∈ΠM_i \in\Pi. Because pathway module sets may overlap, this results in a fuzzy partition of ss-units. ∣Π∣|\Pi| is the size of the cover in terms of the number of pathway modules that comprise it. In practice, we are interested in finding a cover Πs\Pi_s that is composed of modules with no more than ss seeds; additionally, we focus on small ss because modules with smaller seed sets are generally easier to control.

Example GRN interactions

Figure 4. Example GRN interactions. The DCM shown here is the same as in Figure 2. Individual pathway modules are differentiated by color; the seed ss-unit has a double edge. (a) MP1−0M_{\mathrm{P}1-0} is subsumed by module Mi1−0M_{\mathrm{i}1-0}. (b) MP1−1M_{\mathrm{P}1-1} and Mi1−1M_{\mathrm{i}1-1} are decoupled. (c) There is logical obstruction between MP1−1M_{\mathrm{P}1-1} and MP2−1M_{\mathrm{P}2-1}. (d) There is synergy between MP1−1M_{\mathrm{P}1-1} and Mi2−1M_{\mathrm{i}2-1}. (e) A limit cycle of the network due to MP1−1M_{\mathrm{P}1-1}, Mi1−1M_{\mathrm{i}1-1}, and Mi2−1M_{\mathrm{i}2-1}. The inputs are held constant but the node P1 is not (pulse perturbation). (f) All six complex modules with seed set size s=1s = 1. The nodes shown in yellow are subsumed by multiple other modules.

The independence of a pathway module Mi\mathbf{M}_i from a set of pathway modules Σ\Sigma is the fraction of unique s-units that fire within the pathway module:

ind⁡(Mi,Σ)=∣Si−SΣ∣∣Si∣(1)\operatorname{ind}(\mathbf{M}_i,\Sigma)=\frac{|\mathbf{S}_i-\mathbf{S}_\Sigma|}{|\mathbf{S}_i|} \tag*{(1)}

where SΣ=⋃jSj\mathbf{S}_\Sigma=\bigcup_j \mathbf{S}_j for set Sj\mathbf{S}_j with corresponding pathway module Mj∈Σ\mathbf{M}_j\in\Sigma. If {Mi}∪Σ=Π\{\mathbf{M}_i\}\cup\Sigma=\Pi, then Si∪SΣ=SΠ\mathbf{S}_i\cup\mathbf{S}_\Sigma=\mathbf{S}_\Pi and ind⁡(Mi,Σ)\operatorname{ind}(\mathbf{M}_i,\Sigma) gives us the independence of pathway module Mi\mathbf{M}_i within a cover Π\Pi.

The dynamical modularity of a cover Π\Pi is the distribution of independence scores for all its pathway modules: D(Π)≡{ind⁡(Mi,Π−Mi)}, ∀Mi∈Π\mathrm{D}(\Pi)\equiv\{\operatorname{ind}(\mathbf{M}_i,\Pi-\mathbf{M}_i)\},\ \forall\mathbf{M}_i\in\Pi. One can derive several meaningful statistics from this distribution, but here we use its mean value as a characterization of dynamical modularity:

D‾(Π)=(∑Mi∈Πind⁡(Mi,Π−Mi))/∣Π∣(2)\overline{\mathrm{D}}(\Pi)=\left(\sum_{\mathbf{M}_i\in\Pi}\operatorname{ind}(\mathbf{M}_i,\Pi-\mathbf{M}_i)\right)/|\Pi| \tag*{(2)}

As there are many possible covers of the DCM, it is useful to find one that is optimal for measuring modularity. One can define optimality of a cover in different ways, for example, the cover with the minimal size, Πmin⁡\Pi_{\min}. However, as the goal is to find modules that are decoupable from one another, here we define optimality by maximizing the mean dynamical modularity D‾(Π)\overline{\mathrm{D}}(\Pi). We define Πs∗\Pi_s^* as the optimal cover of the DCM, where Πs∗\Pi_s^* has the maximum mean dynamical modularity among covers that satisfy the property that Mi∈I\mathbf{M}_i\in\mathcal{I} for all pathway modules Mi∈Πs\mathbf{M}_i\in\Pi_s (i.e., the cover is composed only of complex modules with seed set size ∣So∣≤s|\mathbf{S}^o|\leq s). The corresponding mean dynamical modularity of this cover indicates how decoupable a network is into its constituent dynamical building blocks.

We note that the optimal cover may be difficult to calculate exactly due to the exponential number of possible module combinations. When networks and seed set sizes are too large to find an exact solution, we use a greedy selection to estimate Πs∗\Pi_s^*. The algorithm starts with an empty set Σ={}\Sigma=\{\} and then iteratively adds the complex module Mi∈Is\mathbf{M}_i\in\mathcal{I}_s that has the highest independence score from Σ\Sigma, max⁡(ind⁡(Mi,Σ))\max(\operatorname{ind}(\mathbf{M}_i,\Sigma)), until a cover is reached, such that SΣ=S\mathbf{S}_\Sigma=\mathbf{S}. We use this cover Σ\Sigma to estimate the optimal cover and its mean dynamical modularity D‾(Σ)\overline{\mathrm{D}}(\Sigma) to estimate the optimal mean dynamical modularity of the network D(Πs∗)‾\overline{D(\Pi_s^*)}. This quasi-optimal solution provides a lower-bound on D(Πs∗)‾\overline{D(\Pi_s^*)}. In practice, multiple covers may have the same mean dynamical modularity, meaning that there may be multiple optimal solutions.

The modules that compose a cover Πs\Pi_s have a distribution of seed set sizes that are bounded by ss. By definition, the mean dynamical modularity of Πs∗\Pi_s^* should increase or remain the same as ss increases, because each increase in maximum seed set size allows for more modules to choose from when finding an optimal cover. The characteristic seed number s∗s^* occurs when increasing ss no longer increases the mean dynamical modularity of Πs∗\Pi_s^*. This represents the minimal seed set size that allows for a network to optimally be dynamically decoupled.

In Fig. 4 panel f, the six complex modules shown comprise Λ1\Lambda_1 and the associated optimal cover Π1∗\Pi_1^*; these are Mi1−1\mathbf{M}_{i_1-1}, MP1−1\mathbf{M}_{P_1-1}, Mi2−1\mathbf{M}_{i_2-1}, MP2−1\mathbf{M}_{P_2-1}, Mi1−0\mathbf{M}_{i_1-0}, and Mi2−0\mathbf{M}_{i_2-0}. The mean dynamical modularity of this cover is D(Π1∗)‾=0.71\overline{D(\Pi_1^*)}=0.71. Additionally, there are two complex modules (assuming pinning perturbation) with s=2s=2 (MP1−1,i2−1\mathbf{M}_{P_1-1,i_2-1} and Mi1−1,i2−0\mathbf{M}_{i_1-1,i_2-0}). With pinning perturbation, this network can be covered by three modules: Π2={Mi1−1,i2−0,MP1−1,i2−1,Mi1−0}\Pi_2=\{\mathbf{M}_{i_1-1,i_2-0},\mathbf{M}_{P_1-1,i_2-1},\mathbf{M}_{i_1-0}\}, with mean dynamical modularity d=0.6d=0.6. Note that this minimal cover is not optimal because D(Π1∗)‾\overline{D(\Pi_1^*)} has a higher mean dynamical modularity. Rather, the optimal cover at s=2s=2 is Π2∗={Mi1−1,Mi2−0,MP1−1,i2−1,Mi1−0}\Pi_2^*=\{\mathbf{M}_{i_1-1},\mathbf{M}_{i_2-0},\mathbf{M}_{P_1-1,i_2-1},\mathbf{M}_{i_1-0}\}; D(Π2∗)‾=0.83\overline{D(\Pi_2^*)}=0.83. The dynamical modularity does not increase with greater ss so the characteristic seed number of this network is s∗=2s^*=2.

In summary, dynamical modularity allows for the comparison of dynamical organization between networks. Dynamically simple networks will be easier to decouple and will tend to have higher mean dynamical modularity and lower characteristic seed number. More complex networks will have more overlap dynamically and will tend to have lower mean dynamical modularity and higher characteristic seed number.

We note that, because our dynamical cover partitions s-units in the DCM, the same node will belong to different modules depending on what state it is in. This is a more granular but lengthier description of the dynamics of the system than considering the nodes themselves.

Computationally, our optimal measure of dynamical modularity is NP-hard as it entails the set cover optimization problem [47, 48] (by comparing all possible sets of complex modules that cover the set SS). However, the number of modules to consider is greatly reduced by considering only complex modules rather than all pathway modules. For all real-world networks that we observed, Is≪PsI_{\mathrm{s}} \ll P_{\mathrm{s}} because many pathway modules are either subsumed into longer modules or they have non-synergistic seeds. Thus, by only considering complex modules, we can greatly reduce the computational complexity of our dynamical modularity optimization problem.

Experimental Results

We demonstrate our approach by using the above formalism to analyze the dynamical modularity of experimentally-validated models of biochemical regulation from systems biology. We focus on the single-cell and full parasegment drosophila SPN models [28] and compare the analysis to that of additional models such as the yeast cell-cycle [49], Arabidopsis thaliana floral development [50], and T-LGL leukemia [51] networks.

Two versions of the SPN exist to model how a pathway of segment polarity genes (and their protein products) regulate segmentation of the body of the fruit fly in its development. The single-cell model is a regulatory network of n=17n = 17 interacting genes and proteins represented as Boolean variables [1] [52]. It has 3 input nodes that are not regulated by other nodes and are usually assumed to be pinned ON or OFF: SLP (Sloppy-Paired proteins), nWG (neighboring Wingless protein), and nHH (neighboring Hedgehog protein). The remaining 14 (internal) nodes are regulated by other nodes in the network.

A larger parasegment network of n=60n = 60 gene and protein variables is built by connecting the single-cell model in a linear lattice of 4 cells with periodic boundary conditions. This network models intra- and inter-cellular regulatory pathways where each of the 4 cells has the same 14 internal nodes as the single-cell model, plus one SLP input per cell (which represents the output of upstream developmental pathways and is usually assumed to be pinned ON or OFF). Furthermore, each of the 4 cells in the parasegment regulates its two neighboring cells via its internal WG and HH nodes, which act as external, inter-cellular inputs to the two neighboring cells. Thus, in the parasegment SPN there are no input nWG or nHH nodes for each cell, which results in a network of n=60n = 60 variables. This model has been extensively studied [1] [53, 28, 54, 55, 56, 57, 21] and its attractors are fully known for the single-cell case, which makes it a useful example to test our modularity methodology.

We compute all complex modules present in the dynamics of the single-cell and full parasegment SPN models for seed set size s≤6s \le6. This analysis allows us to calculate the dynamical modularity of the SPN and compare it to the other systems biology models we analyzed. In the present work we only consider the dynamics that ensues from pinning perturbation of the seed set. This form of perturbation is feasible for experimental work with the target biological models (e.g., gene silencing in drosophila [58]), but our approach also allows for other forms of perturbation (e.g., pulse perturbations) that can be explored in the future.

Complex modules in the Drosophila Single-Cell SPN

Analysis of the drosophila single-cell SPN highlights many useful features of our dynamical modularity methodology. It allows us to reduce the enormous complexity of this dynamical system’s state space to only a few building blocks, characterize which dynamics are involved in transient configurations and attractors, understand the dynamical overlap between similar modules, and study the specific effects of individual nodes and sets of nodes (e.g., comparing network inputs to internal nodes).

To understand the effect of perturbing a specific node in the single-cell SPN with a brute-force approach would require analysis of 2172^{17} configurations. Additionally, there are 2s(17s)2^s \binom{17}{s} different ways to perturb ss seeds, where each node xx in the seed set of size ss may be in the state x-0 or x-1. However, our dynamical modularity methodology offers a much more direct approach without enumerating all network configurations and by reducing the total possible number of seed sets to only those that are complex modules.

For seed sets of size s=1s = 1, there are 34 possible pathway modules to consider (because there are 34 possible seeds; each node xx of the n=17n = 17 nodes may be in the state x-0 or x-1), but only 14 complex modules. This indicates that the other 20 modules do not reveal any dynamical information that is not contained in the 14 complex modules. These complex modules cover the DCM, meaning that they include all 34 node states. For seed sets of size s=2s = 2, there are 9 complex modules out of 544 pathway modules; for size s=3s = 3, there are 19 complex modules out of 5440 pathway modules; for size s=4s = 4, there are 14 complex modules out of 38080 pathway modules. For seed set sizes s>4s > 4 there are no additional complex modules. Any higher-order interaction between variables (i.e., modules with larger seed sets) can be understood as a combination of lower-order interactions that may include overlap or contradictions between the respective modules but no synergy. In other words, no novel synergy emerges in the network by pinning more than 4 seeds. Thus, all of the macro-scale computation that the dynamical system is doing involves building blocks that are controllable by a small number of nodes.

This results in a total of 56 complex modules. However, this number can be further reduced using the maximal seed heuristic where modules are discarded if they contain seeds that do not initiate maximal pathway modules. That is, we consider core complex modules to be those where each seed’s pathway module is itself maximal, Mx∈Λ1,∀x∈S0\mathbf{M}_{x} \in\Lambda_{1}, \forall x \in S^{0}. This reduction removes modules that would have been subsumed if not for contradiction. For example, both Mptc−1,nHH−0\mathbf{M}_{\mathrm{ptc-1,nHH-0}} and MPTC−1,nHH−0\mathbf{M}_{\mathrm{PTC-1,nHH-0}} are complex modules in the single-cell SPN; however, the only reason that MPTC−1,nHH−0\mathbf{M}_{\mathrm{PTC-1,nHH-0}} is not subsumed by Mptc−1,nHH−0\mathbf{M}_{\mathrm{ptc-1,nHH-0}} is because the former includes the state ptc-0, which contradicts the seed set of the latter. Moreover, MPTC−1,nHH−0\mathbf{M}_{\mathrm{PTC-1,nHH-0}} is not a core complex module because its submodule MPTC−1\mathbf{M}_{\mathrm{PTC-1}} is subsumed by Mptc−1\mathbf{M}_{\mathrm{ptc-1}}. Using the maximal seed heuristic, there are 28 core complex modules for the single-cell SPN with maximal seed set size s=3s = 3. These 28 are sufficient to describe all attractors in the network (with a slight caveat mentioned below) and are listed in the supplementary materials.

Only one complex module directly results in an attractor, meaning that the states of all n=17n = 17 variables are resolved: ∣S(nWG−1,SLP−0,nHH−1)∣=17|\mathrm{S}(\mathrm{nWG}-1,\mathrm{SLP}-0,\mathrm{nHH}-1)| = 17, as shown in Fig. 5d. The other 9 attractors of the single-cell SPN can be recovered by combining two or three complex modules (see the supplementary materials for a full description of each attractor). Certain modules appear in multiple attractors. For example, ∣S(SLP−1,nHH−1)∣=16|\mathrm{S}(\mathrm{SLP}-1,\mathrm{nHH}-1)| = 16 (shown in Fig. 5c) resolves every node except the input nWG. The module ∣S(nWG−0,nHH−1)∣=14|\mathrm{S}(\mathrm{nWG}-0,\mathrm{nHH}-1)| = 14 is identical in its unfolding except that it does not resolve wgwg or WG; therefore, this module must be combined with Mwg−0\mathrm{M}_{wg-0} or Mwg−1\mathrm{M}_{wg-1} and MSLP−0\mathrm{M}_{SLP-0} or MSLP−1\mathrm{M}_{SLP-1} to reach an attractor. The module ∣S(nWG−1,SLP−0)∣=13|\mathrm{S}(\mathrm{nWG}-1,\mathrm{SLP}-0)| = 13 (shown in Fig. 5c) resolves most nodes and is in the basin of two attractors when nHH is OFF (when nHH is ON, it is subsumed by M(nWG−1,SLP−0,nHH−1)\mathrm{M}(\mathrm{nWG}-1,\mathrm{SLP}-0,\mathrm{nHH}-1) mentioned above). Finally, ∣S(ptc−1,SLP−1,nHH−0)∣=16|\mathrm{S}(\mathrm{ptc}-1,\mathrm{SLP}-1,\mathrm{nHH}-0)| = 16 (shown in Fig. 5d) and the similar module ∣S(ptc−1,nWG−0,nHH−0)∣=16|\mathrm{S}(\mathrm{ptc}-1,\mathrm{nWG}-0,\mathrm{nHH}-0)| = 16 reach one of three attractors, depending on the state of the input nodes SLP and nWG.5

Even modules that do not result in a steady-state of the network give us important information about partial control of the network state. The size of the module indicates how many other nodes can be controlled. For example, if a researcher can only perturb one node in the single-cell SPN, then turning en ON has the most effect because ∣Sen−1∣=9|\mathrm{S}_{en-1}| = 9 is the longest module at s=1s = 1 (note that this one seed alone controls half of the other network nodes). If perturbing two nodes, then ∣S(SLP−1,nHH−1)∣=16|\mathrm{S}(\mathrm{SLP}-1,\mathrm{nHH}-1)| = 16 gives the most control.

In addition to quantifying how influential a node x is, our methodology also identifies which other node states are reached if x is perturbed. This is useful information when a researcher is interested in reaching certain states in the network. For example, for the T-LGL leukemia network, modules of interest may include those that result in Apoptosis-1 because perturbation of the respective seed set guarantees that the cell death state is reached.

Our methodology also indicates how synergy occurs between seeds and the time step at which it occurs. For example, ∣SSLP−1∣=7\lvert S_{\mathrm{SLP}-1}\rvert= 7 and ∣SPTC−1∣=4\lvert S_{\mathrm{PTC}-1}\rvert= 4; however, combining the modules results in novel synergy, ∣S(SLP−1,PTC−1)∣=15\lvert S_{(\mathrm{SLP}-1,\mathrm{PTC}-1)}\rvert= 15 (and thus resolves every node in the network except the two additional inputs nWG\mathrm{nWG} and nHH\mathrm{nHH}), with synergy between the two modules occurring at time steps t=5t = 5 and t=6t = 6. Knowing specific states of specific nodes allows for additional inferences when making further perturbations. For example, M(SLP−1,nHH−1)M_{(\mathrm{SLP}-1,\mathrm{nHH}-1)} results in ptc−1\mathrm{ptc}-1, so if the state of nHH\mathrm{nHH} is flipped, then M(ptc−1,SLP−1,nHH−0)M_{(\mathrm{ptc}-1,\mathrm{SLP}-1,\mathrm{nHH}-0)} will unfold, resulting in a different attractor (see supplementary materials for a description of the modules).

Complex modules also allow us to see how dynamics overlap between different modules. In some cases, this offers alternative control strategies. For example, the unfolding of Men−1M_{\mathrm{en}-1} is identical to the unfolding of M(SLP−0,nWG−1)M_{(\mathrm{SLP}-0,\mathrm{nWG}-1)}, except that in the former the states of wgwg and WGWG remain unknown. Perhaps less obvious is that PTC\mathrm{PTC}-0 behaves similarly to nHH\mathrm{nHH}-1: they both fire SMO\mathrm{SMO}-1 and CIR\mathrm{CIR}-0 and contribute to firing CIA\mathrm{CIA}-1. This shared behavior means that S(SLP−1,nHH−1)S_{(\mathrm{SLP}-1,\mathrm{nHH}-1)} and S(SLP−1,PTC−0)S_{(\mathrm{SLP}-1,\mathrm{PTC}-0)} are identical except for the seed nodes and the state of the PH\mathrm{PH} node.

In other cases, the lack of overlap tells us that two modules are independent. For example, Men−1M_{\mathrm{en}-1} and MSLP−1M_{\mathrm{SLP}-1} have no overlap and all of their downstream products are in opposing states to one another. This indicates that only one of these modules will ever be active at a time in the dynamical system. Because of this independence, these modules and modules of greater seed set size that subsume them appear in the optimal covers of the DCM for seed set sizes s=[1,4]s = [1,4].

Finally, these complex modules help to elucidate the role of specific nodes, such as the inputs, in the single-cell SPN dynamics. It is already known that the input nodes control much of the network dynamics [1] [21]; however, our analysis shows when the inputs themselves may result in an attractor and when an additional node such as wgwg or PTC\mathrm{PTC} is needed6. Additionally, we see the effects that internal nodes, such as PTC\mathrm{PTC} or CIR\mathrm{CIR}, have by themselves.

This is especially useful in analyzing the parasegment SPN (n=60n = 60) because all nodes in this network are internal except for the four SLP inputs.

For help in analyzing the parasegment SPN, we group modules that have nearly identical (possibly differing in the inclusion of wgwg or WG) downstream products together: let Σ1={MnWG−0,MSLP−1}\Sigma_1 = \{\mathrm{M}_{nWG-0}, \mathrm{M}_{SLP-1}\}, Σ2={Men−1,MnWG−1,SLP−0}\Sigma_2 = \{\mathrm{M}_{en-1}, \mathrm{M}_{nWG-1,SLP-0}\}, Σ3={MnWG−0,nHH−1,MSLP−1,nHH−1}\Sigma_3 = \{\mathrm{M}_{nWG-0,nHH-1}, \mathrm{M}_{SLP-1,nHH-1}\}, Σ4={Men−1,nHH−1,MnWG−1,SLP−0,nHH−1}\Sigma_4 = \{\mathrm{M}_{en-1,nHH-1}, \mathrm{M}_{nWG-1,SLP-0,nHH-1}\}, and Σ5={MnWG−0,PTC−0,MSLP−1,PTC−0}\Sigma_5 = \{\mathrm{M}_{nWG-0,PTC-0}, \mathrm{M}_{SLP-1,PTC-0}\}. As discussed below, these groups are seen often in the parasegment’s dynamics.

Even though the complex modules discussed here are based on pinning perturbation, many of the results are generalizable to any type of perturbation because the input node states are self-sustaining and, therefore, all of their downstream products are guaranteed to fire at some future point. Other modules may be self-sustaining as well. For example, ∣S(PTC−1,nHH−0)∣=6|S(\mathrm{PTC-1,nHH-0})| = 6 maintains the state of its inputs (and, therefore, its downstream products) due to a positive feedback loop between PTC-1 and nHH-0.

Complex modules in the Drosophila Parasegment SPN

We use our dynamical modularity methodology to aid the analysis of the drosophila parasegment SPN. As in the single-cell case, this allows for a great reduction in the complexity of the dynamical system model and enables us to characterize dynamical trajectories within the system. Using complex modules, we are able to find a minimal seed set that reaches the wildtype attractor of drosophila that is lower than previous estimates seen in the literature. Furthermore, we are able to characterize the transient dynamics toward this attractor in terms of the intracellular modules we found in the single-cell SPN.

It is computationally restrictive to discover all complex modules for the drosophila parasegment model, but as in the single-cell case, the number of complex modules found for low seed set sizes is substantially less than the number of possible pinned perturbations. We again use the maximal seed heuristic to speed up computation time. For s=1s = 1, we find 40 complex modules out of 120 possible pathway modules; for s=2s = 2, we find 40 core

Image not extracted

Figure 5. Complex modules in the drosophila single-cell SPN. (a) The DCM of the drosophila single-cell SPN (input nodes have a double edge). Black represents variables in their active (ON) state, white represents variables in their inactive (OFF) state, and grey diamonds represent t-units. The DCM consists of 34 s-units. Note that several t-units have been removed or modified in the figure for clarity of the transition function. (b) Select complex modules (indicated by color) are shown for seed set size ∣Si0∣=1|S_i^0| = 1. These modules dynamically unfold from their respective seed sets (highlighted with a double edge) and include the s and t-units that are guaranteed to fire given pinning perturbation. Modules Men−1M_{\mathrm{en}-1} (blue), MnHH−1M_{\mathrm{nHH}-1} (green), MSLP−1M_{\mathrm{SLP}-1} (pink), and MnHH−0M_{\mathrm{nHH}-0} (gold) are shown. The s-unit CIR-0 is in both Men−1M_{\mathrm{en}-1} and MnHH−1M_{\mathrm{nHH}-1}. Together these four modules cover 59% of the s-units in the DCM. (c) The same as b, but for ∣Si0∣=2|S_i^0| = 2. Modules MnWG−1,SLP−0M_{\mathrm{nWG}-1,\mathrm{SLP}-0} (blue) and MnHH−1,SLP−1M_{\mathrm{nHH}-1,\mathrm{SLP}-1} (red) are shown. The s-unit CIR-0 is in both modules. Together both modules cover 82% of the s-units in the DCM. (d) The same as b, but for ∣Si0∣=3|S_i^0| = 3. Modules MnHH−1,nWG−1,SLP−0M_{\mathrm{nHH}-1,\mathrm{nWG}-1,\mathrm{SLP}-0} (violet) and MnHH−0,ptc−1,SLP−1M_{\mathrm{nHH}-0,\mathrm{ptc}-1,\mathrm{SLP}-1} (brown) are shown. The s-units CIA-0, PH-0, wg-0 and WG-0 are in both modules. Together both modules cover 85% of the s-units in the DCM. Additional modules are shown in supplementary materials.

complex modules out of 7080 pathway modules; for s=3s = 3, we find 152 core complex modules out of 273760; for s=6s = 6, we find 1475 out of more than 3.2 billion. Despite this great reduction, there are still enough core complex modules to make analysis difficult; therefore, we focus only on the modules with the greatest size for each ss value. We are aided also by the symmetry in the model (the index of each of the four cells does not matter because each one is identical to the next) and the fact that the intracellular dynamics of each cell in the parasegment is the exact same as in the single-cell case, except that they are influenced by inputs from neighboring cells (WG and HH) as well as the external input SLP.

As in the single-cell case, the size of complex modules gives us information about partial control in the network. For s=1s = 1, the largest module is similarly ∣Sen−1∣=13\lvert S_{\mathrm{en}-1}\rvert= 13 in any of the four cells. For s=2s = 2, we see behavior not seen in the single-cell case: the largest modules are ∣S(en−1i,en−1i±1)∣=28\lvert S_{\left(\mathrm{en}-1_i,\mathrm{en}-1_{i\pm1}\right)}\rvert= 28 and ∣S(CIR−1i,CIR−1i±2)∣=28\lvert S_{\left(\mathrm{CIR}-1_i,\mathrm{CIR}-1_{i\pm2}\right)}\rvert= 28, where ii denotes the index of the cell. For s=3s = 3, the largest modules are ∣S(SLP−1i,SLP−1i±2,wg−1i±1)∣=52\lvert S_{\left(\mathrm{SLP}-1_i,\mathrm{SLP}-1_{i\pm2},\mathrm{wg}-1_{i\pm1}\right)}\rvert= 52. We already see that three seeds alone can resolve 87% of the states of the n=60n = 60 nodes in the network. For s=4s = 4, the largest complex modules resolve 56 node states; for s=5s = 5, the largest complex modules resolve 59 node states; for s=6s = 6, the largest complex modules resolve all 60 node states, which indicates a network attractor (see supplementary materials). By sampling larger pathway modules, we find that 9 nodes are sufficient to reach the wildtype attractor of the parasegment SPN, which is lower than previous estimates seen in the literature [1] [44, 59] (see Fig. 6).

The discovery of the complex modules allows us to describe the transient dynamics that occur in the parasegment model toward the wildtype attractor (see Fig. 6 and supplementary materials) and other attractors in the network. We find that inter-cellular interactions can be described by the intracellular complex modules found for the single-cell SPN, where the unfolding of one intracellular module MiM_i may initiate another module MjM_j by causing the seed of that module to fire (Sj0∈SiS_j^0 \in S_i). We observe that these transient dynamics move back and forth across cell boundaries as the unfolding of one intracellular module affects its neighboring cells (see the example of the wildtype attractor in Fig. 6 and further examples in supplementary materials).

For example, a Σ2\Sigma_{2} module will initiate MnHH−1\mathbf{M}_{n\mathrm{HH}-1} in both adjacent cells (which will interact synergistically with any Σ1\Sigma_{1} or Σ2\Sigma_{2} modules already active in those cells) and Σ2\Sigma_{2} modules in non-adjacent cells will activate Σ3\Sigma_{3} modules in their neighboring cells (via neighboring WG-0 and HH-1). Interestingly, some intracellular modules that were dynamically independent in the single-cell SPN work together across cell boundaries in the parasegment. For example, M(SLP−1,nHH−1)\mathbf{M}_{(\mathrm{SLP}-1,n\mathrm{HH}-1)} (a Σ3\Sigma_{3} module) will activate WG-1, which can interact with SLP-0 in an adjacent cell to initiate MnWG−1,SLP−0\mathbf{M}_{n\mathrm{WG}-1,\mathrm{SLP}-0} (a Σ2\Sigma_{2} module) in that cell, even though Σ2\Sigma_{2} and Σ3\Sigma_{3} modules are dynamically independent (with the exception of CIR-0) within the same cell.

By analyzing the largest complex modules, we find that internal nodes play a large role in control of the dynamics, particularly en, wg, PTC, and CIR. For example, the expression of MCIR−1\mathbf{M}_{\mathrm{CIR}-1} in non-adjacent cells activates MnWG−0\mathbf{M}_{n\mathrm{WG}-0} and MnHH−0\mathbf{M}_{n\mathrm{HH}-0} in the other two cells. As in the single-cell case, we also find alternative control strategies. For example, either MPTC−0,SLP−1\mathbf{M}_{\mathrm{PTC}-0,\mathrm{SLP}-1} or MnHH−1,SLP−1\mathbf{M}_{n\mathrm{HH}-1,\mathrm{SLP}-1} activates MnWG−1\mathbf{M}_{n\mathrm{WG}-1} in the two neighboring cells.

We observe that the unfolding of pathway modules indicates a temporal order of events, such that one intracellular module may need to completely unfold to initiate another module in the same cell or an adjacent cell. Of course, during the natural dynamics of the network, multiple modules will be initiated simultaneously based on initial conditions and this natural activation may speed up convergence to a final state. However, the unfolding of a pathway module Mi\mathbf{M}_{i} guarantees that any downstream node states x∈Six \in S_{i} will occur (and gives an upper bound on the number of iterations it will take to do so via the module length), as long as the seed nodes are pinned for a long enough period. As an example, pinning the 9 seeds indicated in Fig. 6 (4 of which are the SLP inputs) is guaranteed to drive the network to the wildtype attractor in no more than 16 iterations. Given that this is a steady state, 16 iterations is also an upper bound on how long the seed nodes must be controlled, as the network will remain in the wildtype configuration once it reaches it.

As seen above, using the easily discoverable intracellular complex modules allows for a concise description and qualitative understanding of what is happening in the parasegment network, even though the network is too large for an exhaustive description. Because the drosophila parasegment is divided into four identical and modular cells, we can understand the dynamics of the larger network by understanding the complex modules within the individual cells and how those modules interact across cell boundaries. This gives us a clearer picture of the multivariate dynamics in the network than we could get via simple attractor analysis, while at the same time (due to its Boolean nature) being easier to analyze than a more detailed model (e.g., parameter estimation of differential equations). To better understand how signals propagate between dynamically dependent modules, we simplify the macro-level dynamics of the system and, thus, how the network computes.

Dynamical Modularity of the Drosophila SPN

We use the complex modules found in the drosophila SPN to estimate dynamical modularity of the single-cell and parasegment models by finding an optimal cover of the DCM, as described in § 2.3. For seed set size s=1s = 1, the optimal cover is defined by the set of complex modules Λ1\Lambda_1; however, the general problem of finding an optimal cover composed of modules with at most ss seeds is NP-hard based on the set-cover optimization problem [47, 48]. We can, however, restrict the number of modules in the cover to a maximum defined by parameter qq. For II complex modules there are, therefore,

(Iq)\binom{I}{q}

options to consider for the optimal cover. In general, dynamical modularity scores increase with qq because there are a greater number of module combinations to choose from. However, for larger networks like the parasegment SPN, it is computationally prohibitive to estimate covers with even a moderately high qq. In this case, we estimate the cover using a greedy algorithm (see § 2.3), where at each step the module with the highest independence score is added to the cover until qq selections have been made. In both cases, we only consider core complex modules using the maximal seed heuristic for inclusion in the cover.

For the single-cell SPN, the optimal cover at s=1s = 1 is composed of 14 complex modules and has mean dynamical modularity D‾(Π1∗)=0.69\overline{D}(\Pi_1^*) = 0.69. For s=2s = 2, we calculate the optimal cover Π2∗\Pi_2^* for q≤11q \le11; for s=3s = 3, we calculate

Dynamical unfolding of the wildtype attractor in the drosophila parasegment

Figure 6. Dynamical unfolding of the wildtype attractor in the drosophila parasegment. The minimal steady-state perturbation that we found sufficient to fully resolve the wildtype attractor is shown. Cell boundaries are separated by a blue line; white indicates that a node is OFF in that time step, black indicates that a node is ON, and grey indicates that the node state is unknown. The color of the node label indicates an associated complex module. Select modules are also highlighted in the dynamical unfolding process by colored borders. Arrows indicate the initiation of a new module; arrows pointing to the side or upward indicate that the respective s-unit is initiating a module in a neighboring cell. For example, MSLP−0M_{\mathrm{SLP}-0} is present in cell 1 based on initial conditions (blue arrow). The influence of WG-1 in cell 4 (blue arrow) initiates MSLP−0,nWG−1M_{\mathrm{SLP}-0,\mathrm{nWG}-1} in cell 1 (blue borders). This module turns ON hhhh and HH, which initiates MnHH−1M_{\mathrm{nHH}-1} in cell 2 (green borders) and then turns OFF WG in cell 1 which, together with WG-0 in cell 3 (red arrows), initiates MnWG−0M_{\mathrm{nWG}-0} in cell 2; the synergy between MnHH−1M_{\mathrm{nHH}-1} and MnWG−0M_{\mathrm{nWG}-0} results in MnHH−1,nWG−0M_{\mathrm{nHH}-1,\mathrm{nWG}-0} in cell 2 (which subsumes both individual modules, shown by red borders). This unfolding demonstrates how developmental dynamics interact across cells in the parasegment. See supplementary materials for a full description of the unfolding of the wildtype attractor and the intracellular complex modules involved.

the optimal cover Π3∗\Pi_3^* for q≤8q \le8; for s≥4s \ge4 there are no more core complex modules so the solution does not change. We find that the optimal covers have more than the minimal number of modules necessary to cover the DCM for s>1s > 1 (see Fig. 7, a-b). For s=2s = 2, the DCM can be covered with 5 modules, but the optimal cover is ∣Π2∗∣=10|\Pi_2^*| = 10, D‾(Π2∗)=0.73\overline{D}(\Pi_2^*) = 0.73. For s=3s = 3, the minimal cover is only three modules, but the optimal cover is ∣Π3∗∣=8|\Pi_3^*| = 8, D‾(Π3∗)=0.81\overline{D}(\Pi_3^*) = 0.81 (s∗=3s^* = 3 is also the characteristic seed number of the single-cell SPN). We also find that the DCM cannot be covered by only pinning the s-units representing the input nodes (SLP, nWG, nHH) because none of these modules include the s-units SMO-0 or CIR-1.

Comparing drosophila to other small GRNs, the yeast cell-cycle network [49] (∣Π3∗∣=7|\Pi_3^*| = 7, D‾(Π3∗)=1.0\overline{D}(\Pi_3^*) = 1.0) and the thaliana cell-fate specification network [50] (∣Π3∗∣=11|\Pi_3^*| = 11, D‾(Π3∗)=0.98\overline{D}(\Pi_3^*) = 0.98) have higher modularity scores and characteristic seed numbers s∗=4s^* = 4 and s∗=2s^* = 2 respectively. Interestingly, in both these networks, we find covers composed of complex modules that are (nearly) completely independent.

For the parasegment SPN, the optimal cover for seed set size s=1s = 1 is ∣Π1∗∣=40|\Pi_1^*| = 40, D‾(Π1∗)=0.83\overline{D}(\Pi_1^*) = 0.83. Using our greedy algorithm, we find similar or increased scores for higher ss values: ∣Π2∗∣=35|\Pi_2^*| = 35, D‾(Π2∗)=0.83\overline{D}(\Pi_2^*) = 0.83, ∣Π3∗∣=36|\Pi_3^*| = 36, D‾(Π3∗)=0.83\overline{D}(\Pi_3^*) = 0.83, and ∣Π4∗∣=32|\Pi_4^*| = 32, D‾(Π4∗)=0.87\overline{D}(\Pi_4^*) = 0.87. Due to the sub-optimality of the algorithm, the estimated score is somewhat lower at higher ss values, with ∣Π6∗∣=24|\Pi_6^*| = 24, D‾(Π6∗)=0.84\overline{D}(\Pi_6^*) = 0.84. Our results suggest that the drosophila parasegment SPN is more modular than both the single-cell SPN and the similarly-sized leukemia T-LGL network [51] (estimated ∣Π4∗∣=36|\Pi_4^*| = 36, D‾(Π4∗)=0.61\overline{D}(\Pi_4^*) = 0.61, see Figure 7, c-d).

We can also identify the modules that are included in the optimal cover. For the single-cell SPN, at s=2s = 2, this includes ∣SnHH−1,CIR−1∣=10|S_{\mathrm{nHH-1,CIR-1}}| = 10 and ∣SnHH−0,ptc−1∣=6|S_{\mathrm{nHH-0,ptc-1}}| = 6, and single seed modules such as ∣Sen−1∣=9|S_{\mathrm{en-1}}| = 9. For s=3s = 3, this includes ∣SSLP−1,nHH−0,ptc−1∣=16|S_{\mathrm{SLP-1,nHH-0,ptc-1}}| = 16 (shown in Fig. 5d), ∣SnHH−1,en−1∣=13|S_{\mathrm{nHH-1,en-1}}| = 13, and additional single seed modules. In both cases, larger complex modules that are mostly independent cover much of the DCM and single seed modules fill in the missing node states.

For the parasegment SPN, the majority of the modules in our estimated covers are also of seed set size s=1s = 1 with only a few larger complex modules.

Additionally, we see in Fig. 7d that the estimated mean dynamical modularity is roughly constant for both the parasegment SPN and the T-LGL leukemia network as ss is increased. This suggests that even though the optimal cover is impossible to calculate at higher ss values, and larger complex modules that include useful synergies may be missed, the mean dynamical modularity at s=1s = 1 is a useful lower bound that may estimate well the true value for higher seed set sizes and may be used for comparison to other networks.

Image not extracted

Figure 7. Comparison of dynamical modularity across GRNs. (a) Results for the drosophila single-cell SPN, the yeast cell cycle network, and thaliana arabadopsis. The relative cover size ∣Πs∣/2n|\Pi_s|/2n is shown for each network’s optimal cover Π∗\Pi^* (based on maximizing D‾(Πs)\overline{D}(\Pi_s), shown as full lines) and minimally-sized cover Πmin⁡\Pi_{\min} (dashed lines) per maximum seed set size ss. Note that ∣Πs∣/2n≤1|\Pi_s|/2n \le1 because there are 2n2n ss-units that together create a trivial cover (every ss-unit acts as a module’s seed). The intermediate line ∣Πs∣=n|\Pi_s| = n is indicated by grey dashes. We see that the optimal cover has more than the minimal number of modules for s>1s > 1. (b) Same as panel a, but the dynamical modularity score d=D‾(Πs)d = \overline{D}(\Pi_s) is shown for each network’s optimal cover Π∗\Pi^* (full lines) and minimally-sized cover Πmin⁡\Pi_{\min} (dashed lines). (c) Results for the drosophila parasegment SPN and the T-LGL leukemia network. We estimate the optimal cover Πs∗\Pi_s^* by greedy selection of the maximum module independence, max⁡(ind⁡(Mi,Πs−Mi))\max(\operatorname{ind}(M_i,\Pi_s - M_i)), as described in § 2.3. The relative cover size ∣Πs∗∣/2n|\Pi_s^*|/2n is shown for each network. Grey dashes indicate the line ∣Πs∣=n|\Pi_s| = n. (d) Same as panel c, but the dynamical modularity score d=D‾(Πs∗)d = \overline{D}(\Pi_s^*) is shown for each network. Due to the suboptimal nature of the greedy selection, dd is sometimes lower for larger maximum seed set sizes.

Conclusion

We have formally defined the pathway modules first discovered in [1] and offered an algorithm to discover them via a modified breadth-first search on a network’s DCM. We have also formally analyzed interactions between pathway modules and defined complex modules, which are maximal pathway modules with synergy (dynamic dependence) between seed s-units. This enables us to define the optimal cover of a DCM (a partition of s-units based on complex modules) and the associated mean dynamical modularity.

This modularity methodology is advantageous in that it greatly reduces the combinatoric number of pathway modules in Boolean GRNs for a given seed set size, 2s(ns)2^{s}\binom{n}{s}, and only considers those that are complex modules. It also allows a bottom-up approach to defining modularity based on a single parameter, the maximum seed set size ss. We were thus able to analyze all complex modules that occur in the drosophila single-cell SPN, and sample many that occur in the parasegment. This analysis of dynamical modularity allows an in-depth understanding of how dynamic signals propagate between cells in the parasegment and how dynamics unfold toward biologically-relevant attractors. It also provides a means to compare different GRNs based on the size and dynamical modularity of the optimal cover of their DCM for a given seed set size. This method can be applied to any automata network DCM, including those outside of the biological domain.

Importantly, this analysis describes the emergent computation that takes place in the example models as single seeds synergistically interact, causing their combined dynamical influence to logically propagate downstream, resulting in either an attractor or a partial configuration that represents the (much reduced) possible network configurations remaining. These partial configurations are useful for control problems because the description of pathway modules elucidates exactly which downstream nodes are guaranteed to be affected and which state they will be changed to. This can be especially helpful for target control [60, 41], where reaching a certain variable state is desirable (such as an apoptotic state in a cancer growth model) or not desirable (such as a proliferative state). Pathway modules, and complex modules in particular, can also be used to find seeds that have a similar effect on downstream targets. Alternative control strategies such as these have potential uses in biological networks, such as designing optimal therapeutic targets.

Pathway modules describe the network dynamics in a mechanistic, causal way. All s-units in a pathway module set are guaranteed to be reached given perturbation of the seed set, as long as there are no other interfering signals. This suggests that modules should be somewhat robust to the updating scheme chosen, although additional work is needed to explore module robustness in depth. Pathway module sets, furthermore, provide the logical domain of influence of the seed set [41]. This is a way to estimate which other variables are stabilized (guaranteed to be in a certain state) based on perturbation of a given seed set, regardless of the state of the other variables in the network.

One drawback to this dynamical modularity methodology is that it is still NP-hard in general, and analysis of moderately-sized networks (such as the drosophila parasegment or the T-LGL leukemia network) becomes difficult. However, it is possible to sample even very large networks with low seed set size and greedy selection criteria to estimate optimal covers. We leave additional analysis of efficient heuristics for finding optimal covers for future work as it is outside the scope of this paper.

Despite the computational difficulty of the problem, our methodology is a step toward understanding how network components interact based on the micro-dynamics of node state updates, and how these dynamical building blocks give rise to the macro-dynamics of network behavior.

Acknowledgements

Luis M. Rocha was partially funded by: National Institutes of Health, National Library of Medicine grant 1R01LM012832; Fundação para Ciencia e Tecnologia grant: 2022.09122.PTDC; National Science Foundation Research Traineeship “Interdisciplinary Training in Complex Networks and Systems” Grant 1735095. The funders had no role in study design, data collection and analysis, decision to publish, or any opinions, findings, conclusions or recommendations expressed in the manuscript. The authors would also like to thank Deborah Rocha for scientific copy editing.

Data availability

Network data can be retrieved at https://github.com/tjparmer/dynamical_modularity and https://github.com/rionbr/CANA/tree/master/cana/datasets [61].

Code availability

The code developed for this paper is made available at https://github.com/tjparmer/dynamical_modularity.

Supplementary Materials for Dynamical Modularity in Automata Models of Biochemical Networks

drosophila model

The update rules of the single-cell segment polarity network (SPN) are listed here.

Inputs:

SLPt+1=SLPtnWGt+1=nWGtnHHt+1=nHHt\begin{aligned} \mathrm{SLP}_{t+1} &= \mathrm{SLP}_{t}\\ \mathrm{nWG}_{t+1} &= \mathrm{nWG}_{t}\\ \mathrm{nHH}_{t+1} &= \mathrm{nHH}_{t} \end{aligned}

Internal nodes:

wgt+1=(CIAt∧SLPt∧¬CIRt)∨(wgt∧(CIAt∨SLPt)∧¬CIRt)WGt+1=wgtent+1=nWGt∧¬SLPtENt+1=enthht+1=ENt∧¬CIRtHHt+1=hhtptct+1=CIAt∧¬ENt∧¬CIRtPTCt+1=ptct∨(PTCt∧¬nHHt)PHt+1=PTCt∧nHHtSMOt+1=¬PTCt∨nHHtcit+1=¬ENtCIt+1=citCIAt+1=CIt∧(¬PTCt∨nHHt)CIRt+1=CIt∧PTCt∧¬nHHt\begin{aligned} \mathrm{wg}_{t+1} &= (\mathrm{CIA}_{t} \land\mathrm{SLP}_{t} \land\lnot\mathrm{CIR}_{t}) \lor(\mathrm{wg}_{t} \land(\mathrm{CIA}_{t} \lor\mathrm{SLP}_{t}) \land\lnot\mathrm{CIR}_{t})\\ \mathrm{WG}_{t+1} &= \mathrm{wg}_{t}\\ \mathrm{en}_{t+1} &= \mathrm{nWG}_{t} \land\lnot\mathrm{SLP}_{t}\\ \mathrm{EN}_{t+1} &= \mathrm{en}_{t}\\ \mathrm{hh}_{t+1} &= \mathrm{EN}_{t} \land\lnot\mathrm{CIR}_{t}\\ \mathrm{HH}_{t+1} &= \mathrm{hh}_{t}\\ \mathrm{ptc}_{t+1} &= \mathrm{CIA}_{t} \land\lnot\mathrm{EN}_{t} \land\lnot\mathrm{CIR}_{t}\\ \mathrm{PTC}_{t+1} &= \mathrm{ptc}_{t} \lor(\mathrm{PTC}_{t} \land\lnot\mathrm{nHH}_{t})\\ \mathrm{PH}_{t+1} &= \mathrm{PTC}_{t} \land\mathrm{nHH}_{t}\\ \mathrm{SMO}_{t+1} &= \lnot\mathrm{PTC}_{t} \lor\mathrm{nHH}_{t}\\ \mathrm{ci}_{t+1} &= \lnot\mathrm{EN}_{t}\\ \mathrm{CI}_{t+1} &= \mathrm{ci}_{t}\\ \mathrm{CIA}_{t+1} &= \mathrm{CI}_{t} \land(\lnot\mathrm{PTC}_{t} \lor\mathrm{nHH}_{t})\\ \mathrm{CIR}_{t+1} &= \mathrm{CI}_{t} \land\mathrm{PTC}_{t} \land\lnot\mathrm{nHH}_{t} \end{aligned}

The parasegment SPN (size n=60n = 60) extends the single-cell model by including all 14 internal nodes in each of four cells, where WG and HH influence both of the cell’s neighbors (periodic boundary conditions assumed), and an additional node, SLP, acts as an input to each cell (see [1] and [2] for a full description).

algorithms

Pathway modules can be discovered by a breadth-first search (BFS) on the DCM (algorithm 1, see Fig. 1), given the caveat of accounting for the temporal dynamics of state updates. Input to the algorithm is a DCM, a seed set SS and a perturbation type (pinning or pulse). The algorithm tracks which s-units and t-units fire in each time step. As with regular BFS units are visited via a first-in first-out (FIFO) queue, but a separate queue is created for each time step. The time counter is initialized at 0 and increases once all of the units in the associated queue have been visited.

T-units are added to the queue associated with the current time step tt if their threshold is met, while s-units are added to the queue associated with time step t+1t + 1. If the perturbation type is pinning, any given unit is only visited once (as they are afterwards assumed to fire every time step). If the perturbation type is pulse, by contrast, units that previously fired are allowed to be visited again in future time steps.

The algorithm halts when no new s-units or t-units can be added to a queue (logically, no more units can fire) or the set of s-units and t-units that fire at time t=it = i is equivalent to the set of s-units and t-units that fired at a previous iteration t=j<it = j < i (a cycle is reached) 1.

The algorithm returns a hash table keyed by time step, where each value is the set of s-units and t-units that fire in the associated time step. The total set of s-units that fire, SS, can then be easily derived by finding the superset of s-units from each time step (and ignoring all t-units).

This algorithm can be extended to the general case where each seed s-unit xx is associated with a firing schedule,

f(x,t)={1if x is forced to fire at time t,0if x is not forced to fire at time t,f(x,t) = \begin{cases} 1 & \text{if } x \text{ is forced to fire at time } t, \\ 0 & \text{if } x \text{ is not forced to fire at time } t, \end{cases}

rather than only allowing pinning or pulse perturbation. In this case, the external perturbations dictated by the firing schedule take precedence over any units already in the queue. Additionally, the delay associated with units can be generalized; here all s-units take one time step to fire (i.e., they have delay dt=1d_t = 1); however, s-units can be allowed a higher delay dt>1d_t > 1 such that it takes several (relative) time steps for a signal to reach an s-unit (for example, this may represent cellular processes that operate on a longer time scale than transcription or translation and could be useful for non-synchronous updating schemes [3, 4]).

The set of pathway modules discovered by algorithm 1 can then be reduced to a set of complex modules (algorithm 2, see Fig. 2). Input to the algorithm is a DCM, a maximum seed set size maxsmax_s, a set of s-units seeds, and a perturbation type (pinning or pulse). Algorithm 2 initially finds all pathway modules with seed set size s=1s = 1 whose seed is in the set seeds using algorithm 1 and then removes any subsumed modules to create an initial set of complex modules I1I_1. It then iteratively finds the set of complex modules Is>1I_{s>1} with increasing seed set size s=2,3,4...maxss = 2, 3, 4...max_s. For each size ss, pathway modules are found for all possible seeds sets, where seeds are obtained from the set seeds. This set of potential modules is then reduced to a set of complex modules by removing all modules that are not maximal or that contain non-synergistic submodules. The algorithm halts when the maximum seed set size maxsmax_s has been reached and returns the set of complex modules found thus far.

The set seeds can be any set of s-units of interest (for example, the s-units representing the network inputs). If seeds =S= S, the set of all s-units in the network, then all pathway modules (and therefore all complex modules) will be found; if, however, seeds =Λ1= \Lambda_1, then only complex modules with maximal seeds will be found 2. This is the maximal seed heuristic which finds all core complex modules in the network.

All analysis and code for this paper, including algorithm 1 and algorithm 2, was written in Python 2.7 with the assistance of the CANA package for finding Boolean network DCMs [5]. The code is publicly available at https://github.com/tjparmer/dynamical_modularity.

Algorithm 1: Pathway module breadth-first search

function thresholded_BFS (DCM, S⁰, perturbation_type):

    time t=0
    time_steps={t: queue(S⁰)}
    unfolding={t: {}}
    active_step={S⁰}
    visited={}

    while t≤max(time_steps):

        visited ← active_step
        if active_step = unfolding[i < t]:
            return unfolding
        if perturbation_type=‘pulse’:
            active_step={}
            reset t-unit thresholds

        while time_steps[t]:
            pop first unit x from queue at time_steps[t]
            unfolding[t] ← x
            for each DCM neighbor (s-unit/t-unit) n ∉ active_step:
                if n is not a contradiction and the threshold τ of n is met:
                    dt = the delay of n
                    time_steps[t+dt] ← n
                    active_step ← n

        t = t + 1

    return unfolding
Image not extracted

Figure 1 (PDF p. 45). Pseudo-code for algorithm 1. Input to the function is a DCM, a seed set of s-units S0S^{0}, and a perturbation type (‘pinning’ or ‘pulse’). The algorithm is similar to breadth-first search (BFS) and explores what part of the DCM is reachable from the seed set, factoring in the perturbation type, relative time steps, logical contradiction, and t-unit thresholds. FIFO queues hashed by relative time step are stored in time_stepstime\_steps while sets of visited units hashed by relative time step are stored in unfoldingunfolding. Units (s or t) are only added to the queue associated with the respective time step if they meet the requisite conditions. S-units are given a default threshold τ=1\tau= 1 and delay dt=1dt = 1, while t-units have delay dt=0dt = 0. Units that are visited are added to the sets visitedvisited and active_stepactive\_step. Each t-unit must track the s-units that contribute towards its threshold; with pulse perturbation, unit thresholds are reset after each time step. The algorithm halts when a repeat set of s-units and t-units is found for a given time step or when no new units can be reached based on their logical conditions. The function returns the pathway module MS0M_{S^{0}} initiated by the seed set, i.e., the sets of units visited at each relative time step. In the above pseudo-code, {key:value} represents a hash table and {} a set.

Algorithm 2: Complex module discovery

function complex_module_search (DCM, max_s, seeds, perturbation_type):

    iteration s=1
    complex modules I={}

    while s ≤ max_s:
        if s=1:
            new_seeds=seeds
        else:
            new_seeds={Sᵢ⁰ ∪ {seed} for i ∈ P, seed ∈ seeds}

        pathway modules P={}

        for seed in new_seeds:
            P ← thresholded_BFS(DCM, seed, perturbation_type)

        for module p ∈ P:
            if p is subsumed by m for any module m ∈ P:
                continue
            else if μ(Sₚ⁰) − μ(Sₚₛ⁰) − μ(Sₚ⁰ − Sₚₛ⁰) = ∅ for any submodule ps of p:
                continue
            else:
                I ← p

        s = s + 1

    return I
Pseudo-code for algorithm 2

Figure 2 (PDF p. 46). Pseudo-code for algorithm 2. Input to the function is a DCM, the maximum seed set size max_smax\_s, a set of s-units seeds, and a perturbation type (‘pinning’ or ‘pulse’). At each iteration, new seed sets of size s = k are generated by combining seed sets of current pathway modules of size s = k − 1 with the members of seeds (size s = 1). The pathway modules for these new seed sets are found using algorithm 1; this set of modules is then condensed to a set of complex modules by removing those that are subsumed by other modules or that fail a synergy check. For pinning perturbation, the former condition filters any module p where Sp⊂SmS_p \subset S_m for any other module m ∈ P, whereas for pulse perturbation the temporal order of when units fire must be checked as well. The function returns the set of complex modules I. In the above pseudo-code, {} represents a set.

Example interactions between pathway modules

Figure 3 (PDF p. 47). Example interactions between pathway modules. (a) Module MAM_A subsumes MBM_B as the unfolding of MBM_B is completely contained in MAM_A. (b) MA,B−0M_{A,B-0} logically obstructs MAM_A because of the contradiction between B-0 and B-1, which prevents the rest of MAM_A from unfolding. (c) MAM_A and MDM_D are decoupled (dynamically independent); even though they share a threshold, MA,DM_{A,D} does not fire the t-unit and thus cannot cause any downstream effects. (d) MAM_A and MFM_F are synergistic because MA,FM_{A,F} fires a t-unit that neither module can fire by itself, thereby reaching the node H. (e) There is both synergy and logical obstruction present between MAM_A and MC−1M_{C-1}, as a logical contradiction with C-1 blocks the complete unfolding of MAM_A; however, the synergy present also allows MA,C−1M_{A,C-1} to include I and J. (f) An example of synergy between non-maximal seeds. MCM_C is subsumed by MAM_A and MKM_K is subsumed by MB−0M_{B-0}. Because of the contradiction of B-0 and B-1, ∣SA,B−0∣=3|S_{A,B-0}| = 3 (shown in green). However, if C and K are used as seeds, then a larger module is seen which includes the extra nodes L and M, ∣SC,K∣=4|S_{C,K}| = 4 (shown in brown). This synergy is found in two complex modules, ∣SC,B−0∣=5|S_{C,B-0}| = 5 and ∣SA,K∣=6|S_{A,K}| = 6; however, neither of these are core complex modules because MCM_C and MKM_K are not maximal.

Complex modules in the drosophila single-cell SPN, showing selected modules and all 14 complex modules

Figure 4 (PDF p. 49). Complex modules in the drosophila single-cell SPN, seed set size s=1s = 1. Select complex modules (indicated by color) are shown: module MnWG−0\mathbf{M}_{\mathrm{nWG}-0} (a), module MCIR−1\mathbf{M}_{\mathrm{CIR}-1} (b), module MPTC−0\mathbf{M}_{\mathrm{PTC}-0} (c), and all 14 complex modules with seed set size s=1s = 1 (d). These modules dynamically unfold from their seed set of size s=1s = 1 (highlighted with a double edge) to include the ss and tt-units that are guaranteed to fire given pinning perturbation. In panel d, the 14 modules indicated compose Λ1\Lambda_{1} and cover the DCM. S-units and tt-units are colored by the largest module that they are a part of; modules that only contain the seed (∣Si∣=1|S_i| = 1) are in purple. Note that several tt-units have been removed or modified in the figure for clarity of the transition function.

Complex modules in the drosophila single-cell SPN, seed set size $s = 2$

Figure 5 (PDF p. 50). Complex modules in the drosophila single-cell SPN, seed set size s=2s = 2. Select complex modules (indicated by color) are shown: module MSLP−1,PTC−0\mathrm{M}_{\mathrm{SLP}-1,\mathrm{PTC}-0} (a), module MnHH−1,en−1\mathrm{M}_{\mathrm{nHH}-1,\mathrm{en}-1} (b), module MnHH−1,CIR−1\mathrm{M}_{\mathrm{nHH}-1,\mathrm{CIR}-1} (c), and module MnHH−0,ptc−1\mathrm{M}_{\mathrm{nHH}-0,\mathrm{ptc}-1} (d). These modules dynamically unfold from their seed set of size s=2s = 2 (highlighted with a double edge) to include the ss and tt-units that are guaranteed to fire given pinning perturbation. In panel d, note that ss-unit ptc-0 does not fire with pinning perturbation due to contradiction with ptc-1. Note that several tt-units have been removed or modified in the figure for clarity of the transition function.

Complex modules in the drosophila single-cell SPN

Figure 6 (PDF p. 51). Complex modules in the drosophila single-cell SPN, seed set size s=3s = 3. Select complex modules (indicated by color) are shown: module MSLP−0,nWG−1,nHH−1M_{\mathrm{SLP-0,nWG-1,nHH-1}} (a), module MnWG−0,nHH−1,CIR−1M_{\mathrm{nWG-0,nHH-1,CIR-1}} (b), module MnWG−0,nHH−0,ptc−1M_{\mathrm{nWG-0,nHH-0,ptc-1}} (c), and module MSLP−0,nHH−0,ptc−1M_{\mathrm{SLP-0,nHH-0,ptc-1}} (d). These modules dynamically unfold from their seed set of size s=3s = 3 (highlighted with a double edge) to include the ss and tt-units that are guaranteed to fire given pinning perturbation. In panel a, the indicated module resolves all 17 variable states and results in one of the network’s 10 attractors. In panel b, the indicated module is identical to MSLP−1,nHH−1,CIR−1M_{\mathrm{SLP-1,nHH-1,CIR-1}} but differs only in the seed. In panel c, the indicated module is identical to MSLP−1,nHH−0,ptc−1M_{\mathrm{SLP-1,nHH-0,ptc-1}} but differs only in the seed. Note that several tt-units have been removed or modified in the figure for clarity of the transition function.

Dynamical unfolding in the drosophila parasegment SPN

Figure 7 (PDF p. 52). Dynamical unfolding in the drosophila parasegment SPN. Cell boundaries are separated by a blue line; white indicates that a node is OFF in that time step, black indicates that a node is ON, and grey indicates that the node’s state is unknown. The color of the node label indicates the associated complex module. (a) The dynamical unfolding of SLP1=SLP3=0SLP_1 = SLP_3 = 0, wg2=1wg_2 = 1. The presence of WG-1 in cell 2 allows MSLP−0,nWG−1M_{SLP-0,nWG-1} (labeled as blue) to unfold in cells 1 and 3 by acting as an additional input to SLP-0. These modules turn off WG and turn on HH in cells 1 and 3, which initiates MnWG−0,nHH−1M_{nWG-0,nHH-1} in cells 2 and 4 (labeled as red). Finally MnWG−0,nHH−1M_{nWG-0,nHH-1} in cells 2 and 4 turns off HH which initiates the (small) MnHH−0M_{nHH-0} module in cells 1 and 3 (labeled as yellow). This resolves almost the entire network (52 variables) with only three inputs. (b) The dynamical unfolding of SLP1=SLP3=PTC2=0SLP_1 = SLP_3 = PTC_2 = 0, SLP2=1SLP_2 = 1 is almost identical, except instead of wg-1, SLP-1 and PTC-0 are pinned in cell 2. MSLP−1,PTC−0M_{SLP-1,PTC-0} (labeled as orange) similarly turns on WG, initiating the MSLP−0,nWG−1M_{SLP-0,nWG-1} module in cells 1 and 3. However, the time differences are more pronounced. The unfolding can be seen in three distinct epochs where first MSLP−1,PTC−0M_{SLP-1,PTC-0} must unfold in cell 2, then the MSLP−0,nWG−1M_{SLP-0,nWG-1} modules are initiated in cells 1 and 3, and then MnWG−0,nHH−1M_{nWG-0,nHH-1} is initiated in cell 4. This demonstrates how important timing is in the dynamic interplay between cells.

∣Si0∣|S_i^0|Si0S_i^0∣Si∣|S_i|associated modules
s=1s = 1en−1ien_{-1i}13M2/M3\mathbf{M}_2/\mathbf{M}_3
s=2s = 2(en−1i,en−1i+1),(CIR−1i,CIR−1i+2)(en_{-1i}, en_{-1i+1}), (CIR_{-1i}, CIR_{-1i+2})28M8/M3\mathbf{M}_8/\mathbf{M}_3, M5/M1/M4\mathbf{M}_5/\mathbf{M}_1/\mathbf{M}_4
s=3s = 3{(SLP−0i,SLP−0i+2,wg−1i+1)}=X\{(SLP_{-0i}, SLP_{-0i+2}, wg_{-1i+1})\} = X52M7/M6/M4\mathbf{M}_7/\mathbf{M}_6/\mathbf{M}_4
s=4s = 4{(X+en−1i+1),(X+en−1i+3)}=Y\{(X + en_{-1i+1}), (X + en_{-1i+3})\} = Y56M8/M10/M6\mathbf{M}_8/\mathbf{M}_{10}/\mathbf{M}_6, M8/M10/M6\mathbf{M}_8/\mathbf{M}_{10}/\mathbf{M}_6
s=5s = 5{(SLP−1i,SLP−1i+1,SLP−0i+2,wg−1i+3,en−1i+3),(SLP−1i,SLP−1i+1,SLP−0i+3,wg−1i+2,en−1i+2),(Y+SLP−1i+3),(Y+SLP−0i+3),(SLP−0i,SLP−0i+1,SLP−1i+2,wg−1i+3,en−1i+3),(SLP−0i,SLP−0i+1,SLP−1i+3,wg−1i+2,en−1i+2)}=Z\{(SLP_{-1i}, SLP_{-1i+1}, SLP_{-0i+2}, wg_{-1i+3}, en_{-1i+3}), (SLP_{-1i}, SLP_{-1i+1}, SLP_{-0i+3}, wg_{-1i+2}, en_{-1i+2}), (Y + SLP_{-1i+3}), (Y + SLP_{-0i+3}), (SLP_{-0i}, SLP_{-0i+1}, SLP_{-1i+2}, wg_{-1i+3}, en_{-1i+3}), (SLP_{-0i}, SLP_{-0i+1}, SLP_{-1i+3}, wg_{-1i+2}, en_{-1i+2})\} = Z59M8/M10/M6\mathbf{M}_8/\mathbf{M}_{10}/\mathbf{M}_6 ...
s=6s = 6(Z+SLP−0j),(Z+SLP−1j)(Z + SLP_{-0j}), (Z + SLP_{-1j})60M8/M10/M6\mathbf{M}_8/\mathbf{M}_{10}/\mathbf{M}_6 ...
s=6s = 6(en−1i,PTC−0i+2,SLP−0i,SLP−0i+1,SLP−1i+2,SLP−1i+3)(en_{-1i}, PTC_{-0i+2}, SLP_{-0i}, SLP_{-0i+1}, SLP_{-1i+2}, SLP_{-1i+3})60M10/M6/M9\mathbf{M}_{10}/\mathbf{M}_6/\mathbf{M}_9
s=6s = 6(en−1i,PTC−0i+2,SLP−0i,SLP−1i+1,SLP−1i+2,SLP−0i+3)(en_{-1i}, PTC_{-0i+2}, SLP_{-0i}, SLP_{-1i+1}, SLP_{-1i+2}, SLP_{-0i+3})60M10/M6/M9\mathbf{M}_{10}/\mathbf{M}_6/\mathbf{M}_9
s=6s = 6(en−1i,PTC−0i+2,SLP−0i,SLP−0i+1,SLP−1i+2,SLP−0i+3)(en_{-1i}, PTC_{-0i+2}, SLP_{-0i}, SLP_{-0i+1}, SLP_{-1i+2}, SLP_{-0i+3})60M10/M6/M9\mathbf{M}_{10}/\mathbf{M}_6/\mathbf{M}_9

Table 2. Table 2: Maximal modules in the drosophila parasegment SPN. The seed set Si0S_i^0 and size ∣Si∣|S_i| of the maximal pathway module per seed set size s=∣Si0∣s = |S_i^0| are shown, along with the associated intracellular complex modules found within the maximal module. Here, M₁ indicates MₙWG−0; M₂ indicates Mₑₙ−1; M₃ indicates MₙHH−1; M₄ indicates MₙHH−0; M₅ indicates M_CIR−1; M₆ indicates M_SLP−1,nHH−1; M₇ indicates M_SLP−0,nWG−1; M₈ indicates MₙHH−1,en−1; M₉ indicates M_PTC−0; finally, M₁₀ indicates M_SLP−0,nWG−1,nHH−1. For s=5s = 5, all maximal pathway modules have the same associated intracellular modules; for s=6s = 6, the first two groupings of seed sets have associated modules M₈, M₁₀, and M₆, while the latter three groupings have associated modules M₁₀, M₆, and M₉. The subscript on the ss-unit labels denotes the cell of the parasegment where ii and jj are arbitrary cells chosen such that there is no logical contradiction between variable states and cellular addition uses modular arithmetic. As maximal modules with larger seed sets tend to build on the same set of modules with smaller seed sets, particular seed sets are condensed to variables for readability. Given the periodic boundaries of the parasegment and the similarity of complex modules, a significant degree of redundancy in regards to cellular indices can be seen in the maximal module sets. A seed set of size s≥6s \ge6 is needed to resolve every variable in the network.

Minimal schemata for attractor control in the drosophila parasegment SPN

Figure 8. Minimal schemata for attractor control in the drosophila parasegment SPN. (a) One of the minimal schemata found to reach an attractor, representing the minimal seeds sufficient to drive the dynamics to that attractor with pinning control. Each row represents a cell in the drosophila parasegment and each column the state of the respective node: black represents ON, white represents OFF, and grey represents a wildcard value (i.e., the node state is redundant for convergence to the attractor under pinning perturbation of the seeds). The color of the row label represents the main module group active in that cell during unfolding (pink represents Σ1\Sigma_1, red represents Σ3\Sigma_3, and violet represents Σ4\Sigma_4, see Table 1). (b) Same as panel a, but for the minimal schema sufficient to reach the wildtype attractor. The minimal configurations found are much smaller than the previous estimates without pinning perturbation found in [2].

MiM_idynamical unfolding∣Si∣|S_i|
Men−1  (Σ2)M_{\mathrm{en-1}}\;(\Sigma_2)EN-1, ci-0, ptc-0, CI-0, CIR-0, CIA-0, hh-1, HH-19
MnWG−0  (Σ1)M_{\mathrm{nWG-0}}\;(\Sigma_1)en-0, EN-0, ci-1, hh-0, CI-1, HH-07
MSLP−1  (Σ1)M_{\mathrm{SLP-1}}\;(\Sigma_1)en-0, EN-0, ci-1, hh-0, CI-1, HH-07
MCIR−1M_{\mathrm{CIR-1}}hh-0, wg-0, ptc-0, HH-0, WG-06
MPTC−0M_{\mathrm{PTC-0}}SMO-1, PH-0, CIR-04
MHH−1M_{\mathrm{HH-1}}SMO-1, CIR-03
MHH−0M_{\mathrm{HH-0}}PH-02
Mwg−1M_{\mathrm{wg-1}}WG-12
Mptc−1M_{\mathrm{ptc-1}}PTC-12
MnWG−1M_{\mathrm{nWG-1}}–1
MSLP−0M_{\mathrm{SLP-0}}–1
MPH−1M_{\mathrm{PH-1}}–1
MSMO−0M_{\mathrm{SMO-0}}–1
MCIA−1M_{\mathrm{CIA-1}}–1
MSLP−1,nHH−1  (Σ3)M_{\mathrm{SLP-1,nHH-1}}\;(\Sigma_3)SMO-1, CIR-0, en-0, EN-0, ci-1, hh-0, CI-1, HH-0, CIA-1, wg-1, ptc-1, WG-1, PTC-1, PH-116
MSLP−1,PTC−0  (Σ5)M_{\mathrm{SLP-1,PTC-0}}\;(\Sigma_5)SMO-1, PH-0, CIR-0, en-0, EN-0, ci-1, hh-0, CI-1, HH-0, CIA-1, wg-1, ptc-1, WG-115
MnWG−0,nHH−1  (Σ3)M_{\mathrm{nWG-0,nHH-1}}\;(\Sigma_3)SMO-1, CIR-0, en-0, EN-0, ci-1, hh-0, CI-1, HH-0, CIA-1, ptc-1, PTC-1, PH-114
MnWG−0,PTC−0  (Σ5)M_{\mathrm{nWG-0,PTC-0}}\;(\Sigma_5)SMO-1, PH-0, CIR-0, en-0, EN-0, ci-1, hh-0, CI-1, HH-0, CIA-1, ptc-113
MnHH−1,en−1  (Σ4)M_{\mathrm{nHH-1,en-1}}\;(\Sigma_4)SMO-1, CIR-0, EN-1, hh-1, ci-0, ptc-0, HH-1, CI-0, PTC-0, PH-0, CIA-013
MSLP−0,nWG−1  (Σ2)M_{\mathrm{SLP-0,nWG-1}}\;(\Sigma_2)en-1, EN-1, ci-0, ptc-0, CI-0, CIR-0, CIA-0, hh-1, wg-0, HH-1, WG-013
MnHH−1,CIR−1M_{\mathrm{nHH-1,CIR-1}}SMO-1, hh-0, wg-0, ptc-0, HH-0, WG-0, PTC-0, PH-010
MnHH−0,ptc−1M_{\mathrm{nHH-0,ptc-1}}PH-0, PTC-1, SMO-0, CIA-06
MSLP−0,nWG−1,nHH−1  (Σ4)M_{\mathrm{SLP-0,nWG-1,nHH-1}}\;(\Sigma_4)SMO-1, CIR-0, en-1, EN-1, hh-1, ci-0, ptc-0, HH-1, CI-0, PTC-0, PH-0, CIA-0, wg-0, WG-017
MSLP−1,nHH−1,CIR−1M_{\mathrm{SLP-1,nHH-1,CIR-1}}SMO-1, hh-0, wg-0, ptc-0, en-0, HH-0, WG-0, PTC-0, EN-0, ci-1, PH-0, CI-1, CIA-116
MnWG−0,nHH−1,CIR−1M_{\mathrm{nWG-0,nHH-1,CIR-1}}SMO-1, hh-0, wg-0, ptc-0, en-0, HH-0, WG-0, PTC-0, EN-0, ci-1, PH-0, CI-1, CIA-116
MSLP−1,nHH−0,ptc−1M_{\mathrm{SLP-1,nHH-0,ptc-1}}PH-0, PTC-1, en-0, SMO-0, CIA-0, EN-0, ci-1, hh-0, CI-1, HH-0, CIR-1, wg-0, WG-016
MnWG−0,nHH−0,ptc−1M_{\mathrm{nWG-0,nHH-0,ptc-1}}PH-0, PTC-1, en-0, SMO-0, CIA-0, EN-0, ci-1, hh-0, CI-1, HH-0, CIR-1, wg-0, WG-016
MSLP−0,nHH−0,ptc−1M_{\mathrm{SLP-0,nHH-0,ptc-1}}PH-0, PTC-1, SMO-0, CIA-0, wg-0, WG-09

Table 1. Table 1: List of the core complex modules in the drosophila single-cell SPN with pinning perturbation. Modules are grouped by seed set size and ordered by resulting size ∣Si∣|S_i|. The module labels are colored to correspond to Figure 5 in the main text, as well as supplementary figures 4, 5, and 6; membership in a set of related modules Σ\Sigma is also indicated in parentheses. The s-units are listed in the temporal order that they are visited within the dynamical unfolding process.

Dynamical unfolding of a minimal seed set to reach an attractor in the drosophila parasegment SPN

Figure 9. Dynamical unfolding of a minimal seed set to reach an attractor in the drosophila parasegment SPN. Cell boundaries are separated by a blue line; white indicates that a node is OFF in that time step, black indicates that a node is ON, and grey indicates that the node’s state is unknown. The color of the node label indicates the associated complex module. All four SLP inputs are pinned; additionally, wg and en are ON in the first cell. Men−1\mathrm{M}_{\mathrm{en}-1} unfolds in cell 1, and wg-1 initiates MSLP−0,nWG−1\mathrm{M}_{\mathrm{SLP-0,nWG-1}} in cell 2 by acting as an input along with SLP-0. This turns on HH in both cells which extends the unfolding in each cell via additional synergy (modules Men−1,nHH−1\mathrm{M}_{\mathrm{en-1,nHH-1}} and MSLP−0,nWG−1,nHH−1\mathrm{M}_{\mathrm{SLP-0,nWG-1,nHH-1}}, labeled as violet). It also extends the unfolding of MSLP−1\mathrm{M}_{\mathrm{SLP-1}} in cells 3 and 4 (module MSLP−1,nHH−1\mathrm{M}_{\mathrm{SLP-1,nHH-1}}, labeled as red). This final configuration is in the basin of attraction of the broad stripes attractor [1], and the network will reach this attractor once the seeds wg and en in cell 1 are no longer pinned.

Dynamical unfolding of the wildtype attractor in the drosophila parasegment SPN

Figure 10. Dynamical unfolding of the wildtype attractor in the drosophila parasegment SPN. This figure is the same as Fig. 6 in the main text except that the full unfolding of the minimal seed set to the wildtype attractor is shown in terms of intracellular complex modules. MSLP−0M_{\mathrm{SLP}-0} is present in cell 1 based on initial conditions (blue arrow). The influence of WG−1\mathrm{WG}-1 in cell 4 (blue arrow) initiates MSLP−0,nWG−1M_{\mathrm{SLP}-0,\mathrm{nWG}-1} in cell 1 (shown by blue borders). This module turns on hh\mathit{hh} and HH\mathit{HH} which initiates MnHH−1M_{\mathrm{nHH}-1} in cell 2 (shown in green) and then turns off WG\mathrm{WG} in cell 1 which, together with WG−0\mathrm{WG}-0 in cell 3 (indicated by red arrows), initiates MnWG−0M_{\mathrm{nWG}-0} in cell 2; the synergy between MnHH−1M_{\mathrm{nHH}-1} and MnWG−0M_{\mathrm{nWG}-0} results in MnHH−1,nWG−0M_{\mathrm{nHH}-1,\mathrm{nWG}-0} in cell 2 (which subsumes both modules and is shown by red borders). Based on initial conditions, MPTC−0M_{\mathrm{PTC}-0} is also present in cell 1, MSLP−0M_{\mathrm{SLP}-0} and Mwg−0M_{\mathrm{wg}-0} are present in cell 2, MSLP−1M_{\mathrm{SLP}-1} and MCIR−1M_{\mathrm{CIR}-1} are present in cell 3, and MSLP−1M_{\mathrm{SLP}-1} and Mwg−1M_{\mathrm{wg}-1} are present in cell 4. MSLP−1M_{\mathrm{SLP}-1} in cell 4 (shown by pink borders) turns off hh\mathit{hh} and HH\mathit{HH} which, together with hh−0\mathit{hh}-0 and HH−0\mathit{HH}-0 in cell 2 (indicated by brown arrows), initiates MnHH−0M_{\mathrm{nHH}-0} in cell 3, which is subsumed by MnHH−0,PTC−1M_{\mathrm{nHH}-0,\mathrm{PTC}-1} (shown by brown borders). Finally, the presence of hh−1\mathit{hh}-1 and HH−1\mathit{HH}-1 in cell 1 initiates MnHH−1M_{\mathrm{nHH}-1} in cell 4, which is subsumed by MSLP−1,nHH−1M_{\mathrm{SLP}-1,\mathrm{nHH}-1} (shown in red).

drosophila observability and control

The single-cell SPN is small enough that the attractors of the network can be fully enumerated. Analysis of the dynamical activity within each of the 10 attractors corresponds well with the analysis of complex modules, as each attractor can be associated with one or more modules (Table 3). The Σ4\Sigma_4 module MSLP−0,nWG−1,nHH−1\mathrm{M}_{\mathrm{SLP}-0,\mathrm{nWG}-1,\mathrm{nHH}-1} is seen in only one attractor as it requires an AND condition between all three inputs, resulting in the driver set (SLP=0, nWG=1, nHH=1). The Σ3\Sigma_3 modules, MSLP−1,nHH−1\mathrm{M}_{\mathrm{SLP}-1,\mathrm{nHH}-1} and MnWG−0,nHH−1\mathrm{M}_{\mathrm{nWG}-0,\mathrm{nHH}-1}, are seen in four attractors: the former module resolves every variable except for the input nWG and therefore leads to two attractors depending on the state of this input with driver sets (SLP=1, nWG=1, nHH=1) and (SLP=1, nWG=0, nHH=1); the latter module resolves every variable except for SLP, wgwg, and WG and can lead to three attractors, with driver sets (SLP=1, nWG=0, nHH=1, wgwg=0) (seen above), (SLP=0, nWG=0, nHH=1, wgwg=0), and (SLP=0, nWG=0, nHH=1, wgwg=1). The modules MSLP−1,nHH−0,PTC−1\mathrm{M}_{\mathrm{SLP}-1,\mathrm{nHH}-0,\mathrm{PTC}-1} and MnWG−0,nHH−0,PTC−1\mathrm{M}_{\mathrm{nWG}-0,\mathrm{nHH}-0,\mathrm{PTC}-1} are identical except for their seeds and lead to three attractors, as both modules resolve every variable state except for the missing input (which my be in either state) 3. The driver sets for the three attractors are therefore (SLP=1, nWG=0, nHH=0, PTC=1), (SLP=1, nWG=1, nHH=0, PTC=1), and (SLP=0, nWG=0, nHH=0, PTC=1). The final two attractors require MSLP−0,nWG−1\mathrm{M}_{\mathrm{SLP}-0,\mathrm{nWG}-1} in combination with other modules; one requires MnHH−0\mathrm{M}_{\mathrm{nHH}-0} and MPTC−0\mathrm{M}_{\mathrm{PTC}-0}, while the other requires MnHH−0,PTC−1\mathrm{M}_{\mathrm{nHH}-0,\mathrm{PTC}-1} (note that there is synergy between nHH-0 and PTC-1 and that this module is also a submodule of MSLP−1,nHH−0,PTC−1\mathrm{M}_{\mathrm{SLP}-1,\mathrm{nHH}-0,\mathrm{PTC}-1} and MnWG−0,nHH−0,PTC−1\mathrm{M}_{\mathrm{nWG}-0,\mathrm{nHH}-0,\mathrm{PTC}-1}, meaning that it appears in four attractors). The driver sets for these two attractors are therefore (SLP=0, nWG=1, nHH=0, PTC=0) and (SLP=0, nWG=1, nHH=0, PTC=1). Interestingly, the superset of the nodes associated with the minimal driver sets found via this methodology are the same driver nodes predicted by feedback vertex set theory (inputs SLP, nWG, nHH and internal nodes PTC and wgwg).

AttractorMinimal observability setsMinimal control setAssociated modules
1110000111111101011100001111111010{(nHH ⁣− ⁣1,SLP ⁣− ⁣1,nWG ⁣− ⁣0),(SLP ⁣− ⁣1,ptc ⁣− ⁣1,nWG ⁣− ⁣0),(wg ⁣− ⁣1,SLP ⁣− ⁣1,nWG ⁣− ⁣0),(SLP ⁣− ⁣1,nWG ⁣− ⁣0,WG ⁣− ⁣1),(CIR ⁣− ⁣0,SLP ⁣− ⁣1,nWG ⁣− ⁣0),(SLP ⁣− ⁣1,nWG ⁣− ⁣0,CIA ⁣− ⁣1),(SLP ⁣− ⁣1,nWG ⁣− ⁣0,PH ⁣− ⁣1),(SLP ⁣− ⁣1,SMO ⁣− ⁣1,nWG ⁣− ⁣0)}\{(nHH\!-\!1, SLP\!-\!1, nWG\!-\!0), (SLP\!-\!1, ptc\!-\!1, nWG\!-\!0), (wg\!-\!1, SLP\!-\!1, nWG\!-\!0), (SLP\!-\!1, nWG\!-\!0, WG\!-\!1), (CIR\!-\!0, SLP\!-\!1, nWG\!-\!0), (SLP\!-\!1, nWG\!-\!0, CIA\!-\!1), (SLP\!-\!1, nWG\!-\!0, PH\!-\!1), (SLP\!-\!1, SMO\!-\!1, nWG\!-\!0)\}(nHH ⁣− ⁣1,SLP ⁣− ⁣1,nWG ⁣− ⁣0)(nHH\!-\!1, SLP\!-\!1, nWG\!-\!0)M6,M11\mathrm{M}_{6},\mathrm{M}_{11}
0110000111111101001100001111111010{(wg ⁣− ⁣1,SLP ⁣− ⁣0),(SLP ⁣− ⁣0,WG ⁣− ⁣1)}\{(wg\!-\!1, SLP\!-\!0), (SLP\!-\!0, WG\!-\!1)\}(nHH ⁣− ⁣1,nWG ⁣− ⁣0,wg ⁣− ⁣1,SLP ⁣− ⁣0)(nHH\!-\!1, nWG\!-\!0, wg\!-\!1, SLP\!-\!0)M11,Mwg ⁣− ⁣1,MSLP ⁣− ⁣0\mathrm{M}_{11},\mathrm{M}_{wg\!-\!1},\mathrm{M}_{SLP\!-\!0}
1110000111111101111100001111111011{(nWG ⁣− ⁣1,wg ⁣− ⁣1),(ptc ⁣− ⁣1,nWG ⁣− ⁣1),(nWG ⁣− ⁣1,PH ⁣− ⁣1),(nWG ⁣− ⁣1,CIA ⁣− ⁣1),(nWG ⁣− ⁣1,WG ⁣− ⁣1)}\{(nWG\!-\!1, wg\!-\!1), (ptc\!-\!1, nWG\!-\!1), (nWG\!-\!1, PH\!-\!1), (nWG\!-\!1, CIA\!-\!1), (nWG\!-\!1, WG\!-\!1)\}(nHH ⁣− ⁣1,nWG ⁣− ⁣1,SLP ⁣− ⁣1)(nHH\!-\!1, nWG\!-\!1, SLP\!-\!1)M6,MnWG ⁣− ⁣1\mathrm{M}_{6},\mathrm{M}_{nWG\!-\!1}
0001111000100001100011110001000011{(nHH ⁣− ⁣1,PTC ⁣− ⁣0),(nHH ⁣− ⁣1,en ⁣− ⁣1),(EN ⁣− ⁣1,nHH ⁣− ⁣1),(nHH ⁣− ⁣1,ci ⁣− ⁣0),(CI ⁣− ⁣0,nHH ⁣− ⁣1),(nHH ⁣− ⁣1,CIA ⁣− ⁣0),(nHH ⁣− ⁣1,ptc ⁣− ⁣0),(nHH ⁣− ⁣1,hh ⁣− ⁣1),(HH ⁣− ⁣1,nHH ⁣− ⁣1),(nHH ⁣− ⁣1,PH ⁣− ⁣0)}\{(nHH\!-\!1, PTC\!-\!0), (nHH\!-\!1, en\!-\!1), (EN\!-\!1, nHH\!-\!1), (nHH\!-\!1, ci\!-\!0), (CI\!-\!0, nHH\!-\!1), (nHH\!-\!1, CIA\!-\!0), (nHH\!-\!1, ptc\!-\!0), (nHH\!-\!1, hh\!-\!1), (HH\!-\!1, nHH\!-\!1), (nHH\!-\!1, PH\!-\!0)\}(nHH ⁣− ⁣1,nWG ⁣− ⁣1,SLP ⁣− ⁣0)(nHH\!-\!1, nWG\!-\!1, SLP\!-\!0)M10\mathrm{M}_{10}
1000000010011010110000000100110101{(CIR ⁣− ⁣1,nWG ⁣− ⁣1)}\{(CIR\!-\!1, nWG\!-\!1)\}(SLP ⁣− ⁣1,nHH ⁣− ⁣0,PTC ⁣− ⁣1,nWG ⁣− ⁣1)(SLP\!-\!1, nHH\!-\!0, PTC\!-\!1, nWG\!-\!1)M13,MnWG ⁣− ⁣1\mathrm{M}_{13},\mathrm{M}_{nWG\!-\!1}
0001111000100000100011110001000001{(nHH ⁣− ⁣0,PTC ⁣− ⁣0),(SMO ⁣− ⁣1,nHH ⁣− ⁣0)}\{(nHH\!-\!0, PTC\!-\!0), (SMO\!-\!1, nHH\!-\!0)\}(nWG ⁣− ⁣1,PTC ⁣− ⁣0,nHH ⁣− ⁣0,SLP ⁣− ⁣0)(nWG\!-\!1, PTC\!-\!0, nHH\!-\!0, SLP\!-\!0)M7,M9,M4\mathrm{M}_{7},\mathrm{M}_{9},\mathrm{M}_{4}
0000000111111101000000001111111010{(wg ⁣− ⁣0,ptc ⁣− ⁣1),(ptc ⁣− ⁣1,WG ⁣− ⁣0),(wg ⁣− ⁣0,PH ⁣− ⁣1),(wg ⁣− ⁣0,CIA ⁣− ⁣1),(WG ⁣− ⁣0,PH ⁣− ⁣1),(WG ⁣− ⁣0,CIA ⁣− ⁣1)}\{(wg\!-\!0, ptc\!-\!1), (ptc\!-\!1, WG\!-\!0), (wg\!-\!0, PH\!-\!1), (wg\!-\!0, CIA\!-\!1), (WG\!-\!0, PH\!-\!1), (WG\!-\!0, CIA\!-\!1)\}(nWG ⁣− ⁣0,nHH ⁣− ⁣1,SLP ⁣− ⁣0,wg ⁣− ⁣0)(nWG\!-\!0, nHH\!-\!1, SLP\!-\!0, wg\!-\!0)M11,Mwg ⁣− ⁣0,MSLP ⁣− ⁣0\mathrm{M}_{11},\mathrm{M}_{wg\!-\!0},\mathrm{M}_{SLP\!-\!0}
0001111010000000100011110100000001{(PTC ⁣− ⁣1,en ⁣− ⁣1),(SMO ⁣− ⁣0,en ⁣− ⁣1),(SMO ⁣− ⁣0,EN ⁣− ⁣1),(PTC ⁣− ⁣1,EN ⁣− ⁣1),(PTC ⁣− ⁣1,ci ⁣− ⁣0),(SMO ⁣− ⁣0,ci ⁣− ⁣0),(CI ⁣− ⁣0,SMO ⁣− ⁣0),(PTC ⁣− ⁣1,CI ⁣− ⁣0),(PTC ⁣− ⁣1,hh ⁣− ⁣1),(SMO ⁣− ⁣0,hh ⁣− ⁣1),(PTC ⁣− ⁣1,HH ⁣− ⁣1),(CIR ⁣− ⁣0,SMO ⁣− ⁣0),(HH ⁣− ⁣1,SMO ⁣− ⁣0)}\{(PTC\!-\!1, en\!-\!1), (SMO\!-\!0, en\!-\!1), (SMO\!-\!0, EN\!-\!1), (PTC\!-\!1, EN\!-\!1), (PTC\!-\!1, ci\!-\!0), (SMO\!-\!0, ci\!-\!0), (CI\!-\!0, SMO\!-\!0), (PTC\!-\!1, CI\!-\!0), (PTC\!-\!1, hh\!-\!1), (SMO\!-\!0, hh\!-\!1), (PTC\!-\!1, HH\!-\!1), (CIR\!-\!0, SMO\!-\!0), (HH\!-\!1, SMO\!-\!0)\}(nWG ⁣− ⁣1,PTC ⁣− ⁣1,SLP ⁣− ⁣0,nHH ⁣− ⁣0)(nWG\!-\!1, PTC\!-\!1, SLP\!-\!0, nHH\!-\!0)M7,M12\mathrm{M}_{7},\mathrm{M}_{12}
0000000010011010000000000100110100{(CIR ⁣− ⁣1,SLP ⁣− ⁣0)}\{(CIR\!-\!1, SLP\!-\!0)\}(nWG ⁣− ⁣0,nHH ⁣− ⁣0,PTC ⁣− ⁣1,SLP ⁣− ⁣0)(nWG\!-\!0, nHH\!-\!0, PTC\!-\!1, SLP\!-\!0)M14,MSLP ⁣− ⁣0\mathrm{M}_{14},\mathrm{M}_{SLP\!-\!0}
1000000010011010010000000100110100{(nWG ⁣− ⁣0,SLP ⁣− ⁣1,wg ⁣− ⁣0),(nWG ⁣− ⁣0,nHH ⁣− ⁣0,SLP ⁣− ⁣1),(CIR ⁣− ⁣1,SLP ⁣− ⁣1,nWG ⁣− ⁣0),(SLP ⁣− ⁣1,nWG ⁣− ⁣0,CIA ⁣− ⁣0),(SLP ⁣− ⁣1,SMO ⁣− ⁣0,nWG ⁣− ⁣0),(SLP ⁣− ⁣1,nWG ⁣− ⁣0,WG ⁣− ⁣0),(SLP ⁣− ⁣1,nWG ⁣− ⁣0,PH ⁣− ⁣0),(SLP ⁣− ⁣1,ptc ⁣− ⁣0,nWG ⁣− ⁣0)}\{(nWG\!-\!0, SLP\!-\!1, wg\!-\!0), (nWG\!-\!0, nHH\!-\!0, SLP\!-\!1), (CIR\!-\!1, SLP\!-\!1, nWG\!-\!0), (SLP\!-\!1, nWG\!-\!0, CIA\!-\!0), (SLP\!-\!1, SMO\!-\!0, nWG\!-\!0), (SLP\!-\!1, nWG\!-\!0, WG\!-\!0), (SLP\!-\!1, nWG\!-\!0, PH\!-\!0), (SLP\!-\!1, ptc\!-\!0, nWG\!-\!0)\}(SLP ⁣− ⁣1,nWG ⁣− ⁣0,nHH ⁣− ⁣0,PTC ⁣− ⁣1)(SLP\!-\!1, nWG\!-\!0, nHH\!-\!0, PTC\!-\!1)M13,M14\mathrm{M}_{13},\mathrm{M}_{14}

Table 3. Minimal observability and control sets for the drosophila single-cell SPN. The attractors label the node states in order of SLPSLP, wgwg, WGWG, enen, ENEN, hhhh, HHHH, ptcptc, PTCPTC, PHPH, SMOSMO, cici, CICI, CIACIA, CIRCIR, nHHnHH, nWGnWG. The associated complex modules are colored to correspond to Table 1. Here, M4M_{4} indicates MnHH ⁣− ⁣0M_{nHH\!-\!0}; M6M_{6} indicates MSLP ⁣− ⁣1,nHH ⁣− ⁣1M_{SLP\!-\!1,nHH\!-\!1}; M7M_{7} indicates MSLP ⁣− ⁣0,nWG ⁣− ⁣1M_{SLP\!-\!0,nWG\!-\!1}; M9M_{9} indicates MPTC ⁣− ⁣0M_{PTC\!-\!0}, M10M_{10} indicates MSLP ⁣− ⁣0,nWG ⁣− ⁣1,nHH ⁣− ⁣1M_{SLP\!-\!0,nWG\!-\!1,nHH\!-\!1}, M11M_{11} indicates MnWG ⁣− ⁣0,nHH ⁣− ⁣1M_{nWG\!-\!0,nHH\!-\!1}, M12M_{12} indicates MnHH ⁣− ⁣0,PTC ⁣− ⁣1M_{nHH\!-\!0,PTC\!-\!1}, M13M_{13} indicates MSLP ⁣− ⁣1,nHH ⁣− ⁣0,PTC ⁣− ⁣1M_{SLP\!-\!1,nHH\!-\!0,PTC\!-\!1}; finally, M14M_{14} indicates MnWG ⁣− ⁣0,nHH ⁣− ⁣0,PTC ⁣− ⁣1M_{nWG\!-\!0,nHH\!-\!0,PTC\!-\!1}.

The characterization of dynamical modules here highlights the difference between the driver node set with pinning and pulse perturbation control. If a driver node’s state must be constant, as with pinning perturbations, PTC and wgwg are needed to fully control the network. However, if one is allowed to flip the states of the input variables, then no internal nodes need to be pinned. For example, to reach the attractor that requires MSLP−0,nWG−1\mathrm{M}_{\mathrm{SLP}-0,\mathrm{nWG}-1}, MnHH−0\mathrm{M}_{\mathrm{nHH}-0}, and MPTC−0\mathrm{M}_{\mathrm{PTC}-0}, the module MSLP−0,nWG−1,nHH−1\mathrm{M}_{\mathrm{SLP}-0,\mathrm{nWG}-1,\mathrm{nHH}-1} can be used which turns off PTC (and maintains PTC in the OFF state), and nHH can then be switched OFF to reach the attractor. Furthermore, modules MSLP−1,nHH−1\mathrm{M}_{\mathrm{SLP}-1,\mathrm{nHH}-1} and MnWG−0,nHH−1\mathrm{M}_{\mathrm{nWG}-0,\mathrm{nHH}-1} turn off ptcptc; if the state of nHH is then flipped, the module MnHH−0,PTC−1\mathrm{M}_{\mathrm{nHH}-0,\mathrm{PTC}-1} will unfold, as is seen in four attractors. In general, perturbing nHH along with the other input nodes replaces the need to control PTC as nHH is an input to PTC. Perturbing the internal node wgwg, meanwhile, allows to turn on or off wgwg and WG, when SLP=0, nWG=0, and nHH=1. However, SLP can also be turned ON after MnWG−0,nHH−1\mathrm{M}_{\mathrm{nWG}-0,\mathrm{nHH}-1} unfolds to turn on wgwg and WG and then turned OFF. Alternatively, SLP can be turned OFF while nWG and nHH are ON to initiate MSLP−0,nWG−1,nHH−1\mathrm{M}_{\mathrm{SLP}-0,\mathrm{nWG}-1,\mathrm{nHH}-1}, which turns off wgwg and wgwg, then nWG can be flipped to initiate MnWG−0,nHH−1\mathrm{M}_{\mathrm{nWG}-0,\mathrm{nHH}-1}. Therefore, perturbing SLP and nWG replaces the need to control wgwg. In a sense, pinning the internal nodes then is just a shortcut to replace the need for input node perturbations. This highlights the usefulness of complex modules in developing a qualitative understanding of control in a system.

Perhaps unsurprisingly, the same intracellular modules that lead to attractors in the single-cell SPN lead to attractors in the parasegment SPN, when considering six biologically-relevant attractors from [1]. In particular, MSLP−0,nWG−1M_{\mathrm{SLP}-0,\mathrm{nWG}-1}, MnWG−0,nHH−1M_{\mathrm{nWG}-0,\mathrm{nHH}-1}, MSLP−1,nHH−1M_{\mathrm{SLP}-1,\mathrm{nHH}-1}, and MSLP−1,nHH−0,PTC−1M_{\mathrm{SLP}-1,\mathrm{nHH}-0,\mathrm{PTC}-1} each play a significant role, appearing in at least four of the attractors (see Table 4).

AttractorExpressed nodesMinimal observability setsAssociated modules
Wild-type(wg4; WG4; en1; EN1; hh1; HH1; ptc2,4; PTC2,3,4; ci2,3,4; CI2,3,4; CIA2,4; CIR3)(wg_{4};\ \mathrm{WG}_{4};\ en_{1};\ \mathrm{EN}_{1};\ hh_{1};\ \mathrm{HH}_{1};\ ptc_{2,4};\ \mathrm{PTC}_{2,3,4};\ ci_{2,3,4};\ \mathrm{CI}_{2,3,4};\ \mathrm{CIA}_{2,4};\ \mathrm{CIR}_{3}){(CIR3-1, PTC1-0), (PTC1-0, ptc2-1), (CIA2-1, PTC1-0), (PH2-1, PTC1-0), (PTC1-0, SMO3-0)}\{(\mathrm{CIR}_{3}\text{-}1,\ \mathrm{PTC}_{1}\text{-}0),\ (\mathrm{PTC}_{1}\text{-}0,\ ptc_{2}\text{-}1),\ (\mathrm{CIA}_{2}\text{-}1,\ \mathrm{PTC}_{1}\text{-}0),\ (\mathrm{PH}_{2}\text{-}1,\ \mathrm{PTC}_{1}\text{-}0),\ (\mathrm{PTC}_{1}\text{-}0,\ \mathrm{SMO}_{3}\text{-}0)\}M7/M9, M11, M13, M6\mathrm{M}_{7}/\mathrm{M}_{9},\ \mathrm{M}_{11},\ \mathrm{M}_{13},\ \mathrm{M}_{6}
Broad stripes(wg3,4; WG3,4; en1,2; EN1,2; hh1,2; HH1,2; ptc3,4; PTC3,4; ci3,4; CI3,4; CIA3,4)(wg_{3,4};\ \mathrm{WG}_{3,4};\ en_{1,2};\ \mathrm{EN}_{1,2};\ hh_{1,2};\ \mathrm{HH}_{1,2};\ ptc_{3,4};\ \mathrm{PTC}_{3,4};\ ci_{3,4};\ \mathrm{CI}_{3,4};\ \mathrm{CIA}_{3,4}){(en1-1, en2-1), (en2-1, ptc4-1), (en1-1, ptc3-1), (en1-1, wg3-1), (wg4-1, en2-1)}\{(en_{1}\text{-}1,\ en_{2}\text{-}1),\ (en_{2}\text{-}1,\ ptc_{4}\text{-}1),\ (en_{1}\text{-}1,\ ptc_{3}\text{-}1),\ (en_{1}\text{-}1,\ wg_{3}\text{-}1),\ (wg_{4}\text{-}1,\ en_{2}\text{-}1)\}M10, M10, M6, M6\mathrm{M}_{10},\ \mathrm{M}_{10},\ \mathrm{M}_{6},\ \mathrm{M}_{6}
No segmentation(ci1,2,3,4; CI1,2,3,4; PTC1,2,3,4; CIR1,2,3,4)(ci_{1,2,3,4};\ \mathrm{CI}_{1,2,3,4};\ \mathrm{PTC}_{1,2,3,4};\ \mathrm{CIR}_{1,2,3,4}){(CIR2-1, CIR4-1), (CIR3-1, CIR1-1), (SLP3-1, CIR1-1), (SLP4-1, CIR2-1), (SLP3-1, CIR2-1), (SLP4-1, CIR1-1)}\{(\mathrm{CIR}_{2}\text{-}1,\ \mathrm{CIR}_{4}\text{-}1),\ (\mathrm{CIR}_{3}\text{-}1,\ \mathrm{CIR}_{1}\text{-}1),\ (\mathrm{SLP}_{3}\text{-}1,\ \mathrm{CIR}_{1}\text{-}1),\ (\mathrm{SLP}_{4}\text{-}1,\ \mathrm{CIR}_{2}\text{-}1),\ (\mathrm{SLP}_{3}\text{-}1,\ \mathrm{CIR}_{2}\text{-}1),\ (\mathrm{SLP}_{4}\text{-}1,\ \mathrm{CIR}_{1}\text{-}1)\}M14, M14, M13, M13\mathrm{M}_{14},\ \mathrm{M}_{14},\ \mathrm{M}_{13},\ \mathrm{M}_{13}
Wild-type variant(wg4; WG4; en1; EN1; hh1; HH1; ptc2,4; PTC1,2,3,4; ci2,3,4; CI2,3,4; CIA2,4; CIR3)(wg_{4};\ \mathrm{WG}_{4};\ en_{1};\ \mathrm{EN}_{1};\ hh_{1};\ \mathrm{HH}_{1};\ ptc_{2,4};\ \mathrm{PTC}_{1,2,3,4};\ ci_{2,3,4};\ \mathrm{CI}_{2,3,4};\ \mathrm{CIA}_{2,4};\ \mathrm{CIR}_{3}){(en1-1, SMO1-0), (SMO1-0, ptc4-1), (SMO1-0, ptc2-1), (wg4-1, SMO1-0)}\{(en_{1}\text{-}1,\ \mathrm{SMO}_{1}\text{-}0),\ (\mathrm{SMO}_{1}\text{-}0,\ ptc_{4}\text{-}1),\ (\mathrm{SMO}_{1}\text{-}0,\ ptc_{2}\text{-}1),\ (wg_{4}\text{-}1,\ \mathrm{SMO}_{1}\text{-}0)\}M7/M12, M11, M13, M6\mathrm{M}_{7}/\mathrm{M}_{12},\ \mathrm{M}_{11},\ \mathrm{M}_{13},\ \mathrm{M}_{6}
Ectopic(wg3; WG3; en2; EN2; hh2; HH2; ptc1,3; PTC1,3,4; ci1,3,4; CI1,3,4; CIA1,3; CIR4)(wg_{3};\ \mathrm{WG}_{3};\ en_{2};\ \mathrm{EN}_{2};\ hh_{2};\ \mathrm{HH}_{2};\ ptc_{1,3};\ \mathrm{PTC}_{1,3,4};\ ci_{1,3,4};\ \mathrm{CI}_{1,3,4};\ \mathrm{CIA}_{1,3};\ \mathrm{CIR}_{4}){(CIR4-1, PTC2-0), (ptc1-1, PTC2-0), (CIA1-1, PTC2-0), (PH1-1, PTC2-0), (SMO4-0, PTC2-0)}\{(\mathrm{CIR}_{4}\text{-}1,\ \mathrm{PTC}_{2}\text{-}0),\ (ptc_{1}\text{-}1,\ \mathrm{PTC}_{2}\text{-}0),\ (\mathrm{CIA}_{1}\text{-}1,\ \mathrm{PTC}_{2}\text{-}0),\ (\mathrm{PH}_{1}\text{-}1,\ \mathrm{PTC}_{2}\text{-}0),\ (\mathrm{SMO}_{4}\text{-}0,\ \mathrm{PTC}_{2}\text{-}0)\}M11, M7/M9, M6, M13\mathrm{M}_{11},\ \mathrm{M}_{7}/\mathrm{M}_{9},\ \mathrm{M}_{6},\ \mathrm{M}_{13}
Ectopic variant(wg3; WG3; en2; EN2; hh2; HH2; ptc1,3; PTC1,2,3,4; ci1,3,4; CI1,3,4; CIA1,3; CIR4)(wg_{3};\ \mathrm{WG}_{3};\ en_{2};\ \mathrm{EN}_{2};\ hh_{2};\ \mathrm{HH}_{2};\ ptc_{1,3};\ \mathrm{PTC}_{1,2,3,4};\ ci_{1,3,4};\ \mathrm{CI}_{1,3,4};\ \mathrm{CIA}_{1,3};\ \mathrm{CIR}_{4}){(SMO2-0, en2-1), (SMO2-0, ptc3-1), (SMO2-0, wg3-1), (SMO2-0, ptc1-1)}\{(\mathrm{SMO}_{2}\text{-}0,\ en_{2}\text{-}1),\ (\mathrm{SMO}_{2}\text{-}0,\ ptc_{3}\text{-}1),\ (\mathrm{SMO}_{2}\text{-}0,\ wg_{3}\text{-}1),\ (\mathrm{SMO}_{2}\text{-}0,\ ptc_{1}\text{-}1)\}M11, M7/M12, M6, M13\mathrm{M}_{11},\ \mathrm{M}_{7}/\mathrm{M}_{12},\ \mathrm{M}_{6},\ \mathrm{M}_{13}

Table 4. Attractors and minimal observability sets for the drosophila parasegment SPN. A node or s-unit’s index indicates to which cell in the parasegment it belongs. In addition to the expressed nodes listed, every attractor has input nodes SLP1,2=OFF\mathrm{SLP}_{1,2} = \mathrm{OFF}, SLP3,4=ON\mathrm{SLP}_{3,4} = \mathrm{ON}. The associated intracellular complex modules are listed for cells 1-4 (top to bottom) in the parasegment. Only the main complex modules for each cell are listed; they are colored to correspond to Table 1. Here, M6\mathrm{M}_{6} indicates MSLP−1,nHH−1\mathrm{M}_{\mathrm{SLP}-1,\mathrm{nHH}-1}; M7\mathrm{M}_{7} indicates MSLP−0,nWG−1\mathrm{M}_{\mathrm{SLP}-0,\mathrm{nWG}-1}; M9\mathrm{M}_{9} indicates MPTC−0\mathrm{M}_{\mathrm{PTC}-0}, M10\mathrm{M}_{10} indicates MSLP−0,nWG−1,nHH−1\mathrm{M}_{\mathrm{SLP}-0,\mathrm{nWG}-1,\mathrm{nHH}-1}, M11\mathrm{M}_{11} indicates MnWG−0,nHH−1\mathrm{M}_{\mathrm{nWG}-0,\mathrm{nHH}-1}, M12\mathrm{M}_{12} indicates MnHH−0,PTC−1\mathrm{M}_{\mathrm{nHH}-0,\mathrm{PTC}-1}, M13\mathrm{M}_{13} indicates MSLP−1,nHH−0,PTC−1\mathrm{M}_{\mathrm{SLP}-1,\mathrm{nHH}-0,\mathrm{PTC}-1}; finally, M14\mathrm{M}_{14} indicates MnWG−0,nHH−0,PTC−1\mathrm{M}_{\mathrm{nWG}-0,\mathrm{nHH}-0,\mathrm{PTC}-1}. Note that observability sets only require two sensors to reveal the given attractor.

The logical inferences made during the dynamical unfolding process are also useful in the problem of observability. If a network has reached a fixed point, then each variable state is unchanging (i.e., pinned); thus, observing a set of sensor nodes with corresponding s-units Si0S_i^0 guarantees that the module MSi0M_{S_i^0} has fully unfolded and all the variable states contained in SiS_i are present in the current state of the network. Observing only a small subset of such states (2-3 in the case of the drosophila single-cell SPN, equivalent to less than 18% of the network size) is sufficient to figure out which attractor the network is in. The size of this minimal observability set is naturally upper-bounded by the size of the minimal driver set. For the drosophila parasegment SPN, the minimal observability sets require only two s-units (3% of the network size) when considering only the six biologically-relevant attractors in Table 4.

NodesS-unitsAttractorsD(Π∗)‾\overline{D(\Pi^*)}∣Π∗∣|\Pi^*|avg. ∣Si∣∈Π∗|S_i| \in\Pi^*max ∣Si∣∈Π∗|S_i| \in\Pi^*
Example GRN61250.8343.255 (83%)
Drosophila single-cell1734100.8185.2516 (94%)
Thaliana1530100.98112.8211 (73%)
Yeast1224111.073.4312 (100%)
Drosophila parasegment60120?0.87324.4433 (55%)
Leukemia60120?0.64414.9542 (70%)

Table 5. Comparison of dynamical modularity between genetic regulatory networks. The optimal cover Π∗\Pi^* is estimated for each network by maximizing the mean dynamical modularity among covers across seed set sizes, assuming pinning perturbation. Six networks are considered: the example GRN from Fig. 2 in the main text, the drosophila single-cell and parasegment SPNs [1], the Thaliana arabadopsis cell-fate specification network [6], the yeast cell-cycle network [7], and the T-LGL leukemia network [8]. For the first grouping of networks, Π∗\Pi^* was calculated considering all possible covers of q≤6q \le6 core complex modules with seed set size s≤5s \le5, with higher qq values used when computationally feasible. By contrast, Π∗\Pi^* for the drosophila parasegment and leukemia networks was estimated using the greedy heuristic mentioned in § 2.3. For each network the mean dynamical modularity of the optimal cover, D(Π∗)‾\overline{D(\Pi^*)}, the size of the estimated optimal cover, ∣Π∗∣|\Pi^*|, the average module size within the optimal cover, avg. ∣Si∣∈Π∗|S_i| \in\Pi^*, and the maximum module size within the optimal cover, max ∣Si∣∈Π∗|S_i| \in\Pi^*, is shown. Percentages are calculated based on the number of nodes in the network.

Average driver set sizeMin driver set sizeMax driver set sizeDriver superset sizeFVS size
Example GRN22223
Drosophila single-cell3.73455
Thaliana6.15799
Yeast6.455778

Table 6. Comparison of attractor controllability between genetic regulatory networks. Statistics for the driver sets sufficient to fully resolve each fixed point attractor in the network, assuming pinning perturbation, are shown. Driver sets are equivalent to the seed sets of the minimal pathway modules whose unfolding includes all node states found in the respective attractor. The superset of driver nodes needed (based on the set of s-units sufficient to control to each attractor) is compared to that predicted by feedback vertex set theory [9, 10]. See the caption of Fig. 5 for a description of the networks used here.

YeastThalianaDrosophila single-cellDrosophila parasegmentLeukemia
Network size1215176060
Number of attractors111010??
s=1s = 1 number of modules, maximum module size (% of network)17, 4 (33%)16, 8 (53%)14, 9 (53%)40, 13 (22%)48, 24 (40%)
s=2s = 2 number of modules, maximum module size (% of network)12, 10 (83%)7, 12 (80%)8, 16 (94%)40, 28 (47%)64, 41 (68%)
s=3s = 3 number of modules, maximum module size (% of network)12, 12 (100%)3, 14 (93%)6, 17 (100%)152, 52 (87%)223, 53 (88%)
s=4s = 4 number of modules, maximum module size (% of network)4, 12 (100%)0,0,472, 56 (93%)646, 54 (90%)
s=5s = 5 number of modules, maximum module size (% of network)2, 12 (100%)0,0,1073, 59 (98%)1446, 56 (93%)
s=6s = 6 number of modules, maximum module size (% of network)0,0,0,1475, 60 (100%)2353, 57 (95%)
Min fixed point seed set size (% of network)3 (25%)4 (27%)3 (18%)6 (10%)8 (13%)

Table 7. Comparison of core complex modules between genetic regulatory networks. The number of core complex modules, along with the maximum module size, is found per network per seed set size ss. Additionally, the minimal seed set size found to fully resolve every variable state (min fixed point seed set size) is shown; note that this fixed point is not necessarily an attractor of the original network, due to the pinning of the seeds involved. It is apparent that variable states in each network are quickly resolved as ss is increased when considering the largest complex module. In comparing the larger networks, the leukemia network has more core complex modules than the drosophila parasegment per ss value, suggesting more complicated dynamics. Percentages are calculated based on the number of variables (nodes) in the network. See the caption of Fig. 5 for a description of the networks used here.

References

  1. [1]Réka Albert and Hans G Othmer. The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in drosophila melanogaster. Journal of theoretical biology, 223(1):1–18, 2003.pubmed.ncbi.nlm.nih.gov/12782112
  2. [2]Manuel Marques-Pita and Luis M Rocha. Canalization and control in automata networks: body segmentation in drosophila melanogaster. PloS one, 8(3):e55946, 2013.
  3. [3]Madalena Chaves, Eduardo D Sontag, and Réka Albert. Methods of robustness analysis for boolean models of gene control networks. arXiv preprint q-bio/0605004, 2006.pubmed.ncbi.nlm.nih.gov/16986617
  4. [4]Carlos Gershenson. Introduction to random boolean networks. arXiv preprint nlin/0408006, 2004.arxiv.org/abs/nlin/0408006
  5. [5]Rion Brattig Correia, Alexander J Gates, Xuan Wang, and Luis M Rocha. Cana: A python package for quantifying control and canalization in boolean networks. arXiv preprint arXiv:1803.04774, 2018.DOI
  6. [6]Alvaro Chaos, Max Aldana, Carlos Espinosa-Soto, Berenice García Ponce de León, Adriana Garay Arroyo, and Elena R Alvarez-Buylla. From genes to flower patterns and evolution: dynamic models of gene regulatory networks. Journal of Plant Growth Regulation, 25(4):278–289, 2006.DOI
  7. [7]Fangting Li, Tao Long, Ying Lu, Qi Ouyang, and Chao Tang. The yeast cell-cycle network is robustly designed. Proceedings of the National Academy of Sciences, 101(14):4781–4786, 2004.pubmed.ncbi.nlm.nih.gov/15037758
  8. [8]Ranran Zhang, Mithun Vinod Shah, Jun Yang, Susan B Nyland, Xin Liu, Jong K Yun, Réka Albert, and Thomas P Loughran. Network model of survival signaling in large granular lymphocyte leukemia. Proceedings of the National Academy of Sciences, 2008.DOI
  9. [9]Bernold Fiedler, Atsushi Mochizuki, Gen Kurosawa, and Daisuke Saito. Dynamics and control at feedback vertex sets. i: Informative and determining nodes in regulatory networks. Journal of Dynamics and Differential Equations, 25(3):563–604, 2013.DOI
  10. [10]Atsushi Mochizuki, Bernold Fiedler, Gen Kurosawa, and Daisuke Saito. Dynamics and control at feedback vertex sets. ii: A faithful monitor to determine the diversity of molecular activities in regulatory networks. Journal of theoretical biology, 335:130–146, 2013.DOI

Paper details

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

views · 0

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