PaperlayerView exact revision on arXiv

Source-linked AI summary

An effective network reduction approach to find the dynamical repertoire of discrete dynamic networks

Jorge G. T. Zañudo, Réka Albert

arXiv:1304.3467v2q-bio.MNcond-mat.dis-nnphysics.bio-ph

TL;DR

Large Boolean networks pose a challenge for attractor analysis because their state spaces grow exponentially, while existing tools do not always scale. This paper uses topologically identified components in an expanded network to reduce networks. The method preserves attractors and, in most cases, predicts which nodes stabilize or oscillate.

  • Problem

    Attractor analysis for large networks is difficult because state spaces grow exponentially, and many existing structure–dynamics tools are computationally demanding or difficult to apply at scale.

    Source: §I · pp. 1–2

  • Method

    The method identifies stable motifs as components of an expanded network and uses them to reduce the network and infer node behavior.

    Source: LEAD PARAGRAPH · p. 1, E. Identifying Stable Motifs from the… · p. 4

  • Results

    The reduction preserves all attractors, outperforms state-space sampling in attractors or quasi-attractors found and computational time, and in most cases predicts which nodes stabilize or oscillate.

    Source: §IV · p. 13

  • Takeaways & Limitations

    For the T-LGL leukemia network, identified stable components appear to play an important biological role and to be used as a cell-fate determination mechanism for cytotoxic T cells.

    Source: §IV · p. 15

    The stated oscillation criteria are necessary but not sufficient; excluding stable motifs made only of normal and complementary nodes adds a sufficient, though not necessary, condition.

    Source: G. Oscillations and oscillating… · p. 7

Abstract

from arXiv · show

Discrete dynamic models are a powerful tool for the understanding and modeling of large biological networks. Although a lot of progress has been made in developing analysis tools for these models, there is still a need to find approaches that can directly relate the network structure to its dynamics. Of special interest is identifying the stable patterns of activity, i.e., the attractors of the system. This is a problem for large networks, because the state space of the system increases exponentially with network size. In this work we present a novel network reduction approach that is based on finding network motifs that stabilize in a fixed state. Notably, we use a topological criterion to identify these motifs. Specifically, we find certain types of strongly connected components in a suitably expanded representation of the network. To test our method we apply it to a dynamic network model for a type of cytotoxic T cell cancer and to an ensemble of random Boolean networks of size up to 200. Our results show that our method goes beyond reducing the network and in most cases can actually predict the dynamical repertoire of the nodes (fixed states or oscillations) in the attractors of the system.

LEAD PARAGRAPH

Discrete dynamic models capture qualitative behavior using interaction signs rather than kinetic rates, but finding attractors becomes difficult as networks grow. This work introduces a topology-based reduction method for identifying fixed-state components and inferring network dynamics.

A. Biological networks and discrete dynamic models

  • Discrete dynamic models reproduce qualitative system dynamics from activating or inhibiting interactions without requiring biochemical rate information.The paper uses Boolean models, whose nodes take one of two states, and general asynchronous updating to represent rate-invariant activity patterns.Source: §I · p. 1, A. Biological networks and discrete… · pp. 2–3

I. INTRODUCTION

  • Earlier structure–dynamics rules identify positive feedback as necessary for multistability and negative feedback as necessary for sustained oscillations.The introduction notes that later work extended these rules to include sufficient conditions.Source: §I · p. 2
  • Attractor analysis is difficult at large scale because state spaces grow exponentially and many existing tools are computationally demanding or hard to apply.The introduction also notes that theorem conditions can become harder to satisfy as network size increases.Source: §I · pp. 1–2
  • The proposed method expands the network to identify stable components topologically, then uses them to simplify the network and infer its dynamical repertoire.A complete reduction directly gives fixed points; a partial reduction leaves a simplified network whose remaining nodes are expected to oscillate.Source: LEAD PARAGRAPH · p. 1, §I · p. 2

A. Biological networks and discrete dynamic models

  • General asynchronous updating represents attractors as activity patterns invariant to arbitrary fluctuations in process rates.The method treats finding these attractors as finding the network's stable dynamic repertoire.Source: A. Biological networks and discrete… · p. 3

B. Finding the attractors of a Boolean model

The paper addresses the exponential state-space cost of Boolean attractor searches and limitations of earlier reductions. It identifies stable components and uses an expanded network representation to support reduction and prediction of fixed or oscillating node behavior.

B. Finding the attractors of a Boolean model

  • Boolean state spaces contain 2^N states, limiting full attractor searches in practice to small networks, while earlier reductions may remain intractable or alter attractor space.Some prior methods preserve only selected attractor types, such as steady states.Source: B. Finding the attractors of a Boolean… · p. 3

C. The role of stable motifs and oscillating components in the attractor landscape

  • The method's novelty is efficiently identifying motifs that stabilize in asynchronous attractors despite coupling to the rest of the network.Repeatedly applying reduction can identify states of other nodes stabilized by those motifs.Source: C. The role of stable motifs and… · p. 3
  • Stable motifs are network components that take fixed states and can stabilize themselves and other nodes.If the fixed-state nodes cover the whole network, they identify a fixed-point attractor; if only a subset is covered, the remaining nodes are expected to oscillate.Source: C. The role of stable motifs and… · pp. 3–4

D. Expanded Network

  • The expanded network incorporates update functions and interaction logic to make stable motifs identifiable.It adds complementary nodes to represent inhibitory effects and composite nodes for synergistic AND relationships.Source: D. Expanded Network · p. 4
  • Composite nodes encode conjunctive clauses in disjunctive normal form, with one added for each set of nodes in an AND-dependent relationship.The update function and its negation are represented in disjunctive normal form before composite nodes are introduced.Source: D. Expanded Network · p. 4

E. Identifying Stable Motifs from the Expanded Network

Stable motifs are the smallest qualifying strongly connected components in the expanded network, and their composition specifies fixed states for Boolean-network nodes. Their identity depends on the network’s logical rules and topology.

E. Identifying Stable Motifs from the Expanded Network

  • A stable motif is a smallest strongly connected component that contains no node together with its complement and includes every input of any composite node it contains.“Smallest” means it contains no smaller SCC satisfying both properties; its size can otherwise vary.Source: E. Identifying Stable Motifs from the… · p. 4
  • Restricting the search to smallest qualifying SCCs allows all combinations of such SCCs to be considered as steady states, while larger SCCs can be examined after reduction.The definition also extends to the corresponding set of Boolean-network nodes whose states are specified by an expanded-network motif.Source: E. Identifying Stable Motifs from the… · pp. 4–5
  • Normal nodes in a stable motif take state 1, while nodes represented by their complementary nodes take state 0.This maps the motif’s composition to the states of a subset of Boolean-network nodes.Source: E. Identifying Stable Motifs from the… · p. 4
  • The example’s two motifs specify states {A = 1, B = 1, C = 0} and {B = 0, C = 1}.Source: E. Identifying Stable Motifs from the… · p. 5
  • Stable motifs depend on the logical-rule structure and network topology, so arbitrary changes can alter them and require reconstructing the expanded network to determine how.Source: E. Identifying Stable Motifs from the… · p. 5

F. Network Reduction

Network reduction propagates fixed states from stable motifs, simplifies the remaining network, and repeats the process. Its output records stabilized nodes alongside any nodes whose states remain undetermined.

F. Network Reduction

  • For each stable motif, the reduction identifies its fixed-state nodes as source nodes and fixes their values in downstream Boolean functions.A downstream node whose modified function has only one possible outcome can itself become a source node.Source: F. Network Reduction · pp. 5–6
  • The method removes mediator nodes by connecting their inputs to their outputs, and removes irrelevant sink nodes with no outgoing edges.A mediator has one incoming and one outgoing edge; its value can be determined once its input values are known.Source: F. Network Reduction · p. 6
  • The two reduction steps are repeated recursively for each stable motif until neither step applies, then the process is reapplied to reduced networks.When no unknown states remain, the stabilized node states directly give a fixed-point attractor.Source: F. Network Reduction · p. 6
  • Each reduction output pairs stabilized node states with a reduced network of nodes whose states remain unknown; this is called a quasi-attractor.The remaining nodes are expected to oscillate in an attractor associated with that quasi-attractor.Source: F. Network Reduction · p. 6
  • Every attractor has an associated quasi-attractor whose fixed node states match the values of those nodes in that attractor.When no nodes oscillate in the quasi-attractor, its stabilized states correspond to a fixed-point attractor.Source: F. Network Reduction · p. 7

G. Oscillations and oscillating components

The expanded network identifies candidate oscillating components through SCC structure, but the structural conditions alone do not guarantee oscillation. Unstable and incomplete oscillations can affect which nodes stabilize and how reduction represents the dynamics.

G. Oscillations and oscillating components

  • Candidate oscillating components are the largest SCCs containing both each normal node and its complement, and all inputs of any included composite node.The largest SCCs capture nodes that feed back to one another in the oscillation.Source: G. Oscillations and oscillating… · p. 7
  • These structural properties are necessary but not sufficient; a candidate lacking stable motifs made only of normal and complementary nodes satisfies an additional sufficient, but not necessary, condition for oscillation.Components meeting only the necessary conditions may have unstable oscillations, so reduction tracks them as marked quasi-attractors that may not correspond to an attractor.Source: G. Oscillations and oscillating… · p. 7
  • In an incomplete oscillation, nodes in an oscillating component do not visit every state in their sub-state-space, allowing downstream nodes to stabilize.For example, A and B visit (1,0), (0,0), and (0,1), but not (1,1), so C with fC = A AND B stabilizes at 0.Source: G. Oscillations and oscillating… · p. 7
  • Incomplete oscillations can therefore fix downstream nodes, a behavior previously reported in synchronous networks.Source: G. Oscillations and oscillating… · p. 7

III. RESULTS

The authors formally establish that the reduction method finds a quasi-attractor corresponding to every Boolean-network attractor. They also describe computational challenges and illustrate unstable and incomplete oscillation cases.

III. RESULTS

  • Finding all candidate stable motifs requires searching directed cycles, with Johnson’s algorithm taking O((N + E)(c + 1)) time, where c is the number of cycles.The number of directed cycles can grow faster than 2N in the worst case of a fully connected network.Source: §III · p. 7
  • Every Boolean-network attractor has a corresponding quasi-attractor that the reduction method finds.The authors state that Appendix A formally proves this correspondence.Source: §III · p. 7
  • The method is tested on a T-LGL leukemia network and an ensemble of random Boolean networks.The passage identifies these as tests of validity and generality, without reporting their outcomes.Source: §III · pp. 7–8
  • The examples show that a stable motif can coexist with an oscillating SCC and fixed-point attractor, and that incomplete oscillation can stabilize a downstream node.Figure 3 shows state 11 as a fixed point alongside the complex attractor 01, 00, and 10; Figure 4 shows C fixed at 0 when A and B miss state 11.Source: Figure 3 · p. 8, Figure 4 · p. 8

A. T Cell Large Granular Lymphocyte Leukemia Network

The T-LGL leukemia network models abnormal cytotoxic T-cell survival and signaling. Across external-signal combinations with antigen present, reduction-derived attractors and quasi-attractors matched those found by sampling.

A. T Cell Large Granular Lymphocyte Leukemia Network

  • T-LGL leukemia involves abnormal mature cytotoxic T-cell survival and deregulated signaling, while earlier reduction work could leave networks of 30–40 nodes for some input combinations.The modeled network has 60 nodes and 142 regulatory edges; its input and output nodes represent external signals and cell-fate or function indicators.Source: A. T Cell Large Granular Lymphocyte… · pp. 8–10
  • Across all external-signal combinations with Stimuli=ON, reduction-derived attractors and quasi-attractors matched sampled attractors, and the authors say this supports finding all possible attractors.The claim is also supported by the proof in Appendix A.Source: A. T Cell Large Granular Lymphocyte… · p. 10
  • With IL15 and Stimuli ON and the other listed signals OFF, the 42-node network yielded four stable motifs and reduced networks of 3, 39, 35, and 39 nodes.The motifs were PDGFR=S1P=SPHK1=ON with Ceramide=OFF; PDGFR=S1P=SPHK1=OFF; TBET=ON; and P2=ON.Source: A. T Cell Large Granular Lymphocyte… · p. 10
  • Further reductions from the second, third, and fourth motifs can produce apoptosis or T-LGL leukemia attractors, with the third and fourth motifs producing both outcomes.The second motif leads to apoptosis after 2–3 additional reductions; the third and fourth can produce either attractor after 2–4 reductions.Source: A. T Cell Large Granular Lymphocyte… · p. 10

B. Ensemble of Random Boolean Networks

The method was tested on random Boolean networks across sizes up to 200 and compared with attractor identification and state-space sampling. It generally matched the reference attractors, found no fewer attractors than sampling in large networks, and was faster for larger networks.

B. Ensemble of Random Boolean Networks

  • The tests used Kauffman N–K networks with K=2 and sizes from 5 to 200, comparing stabilized states in reduction quasi-attractors with asynchronous attractors.Networks up to N=100 used Johnson’s exact cycle-finding algorithm; larger networks restricted the search to cycles shorter than 40 nodes.Source: B. Ensemble of Random Boolean Networks · pp. 10–11
  • For N≤18, attractors were identified as sink strongly connected components in the asynchronous state-transition graph; larger networks used sampled initial conditions and partial-graph validation.Sampling used 5,000 initial conditions, 300 effective steps, 1,500 transient steps, and 50,000 search steps.Source: B. Ensemble of Random Boolean Networks · p. 11
  • Of 1,300 networks compared, all but five had equivalent results; the five largest-network cases were compatible because stabilized-node states matched while some other nodes were fixed in sampled attractors.The method does not predict the states of nodes remaining after motif reduction.Source: B. Ensemble of Random Boolean Networks · p. 11
  • Most quasi-attractors leave a relatively small fraction of nodes unstabilized, but those nodes are not necessarily oscillating.Figure 7 shows the distribution of stabilized-node fractions for N=100 across 1,000 networks, with a logarithmic vertical axis.Source: B. Ensemble of Random Boolean Networks · p. 12, Figure 7 · p. 12
  • For large networks, reduction found the same or more attractors than sampling, and the authors conclude every system attractor has a corresponding reduction quasi-attractor.Some putative attractors with approximately 20 or more oscillating nodes were not always found by partial-graph validation, but trajectory checks gave equivalent or compatible results.Source: B. Ensemble of Random Boolean Networks · p. 12
  • For N=100, 150, and 200, 88%, 76%, and 71% of networks, respectively, completed reduction in under one second; none completed sampling in under one second.At very small sizes (N ≤10), the exact method was faster on average than reduction.Source: B. Ensemble of Random Boolean Networks · p. 12

IV. DISCUSSION

The discussion argues that network reduction shifts attractor-finding complexity from state-space size to cycle count, while often predicting which nodes stabilize or oscillate. In the T-LGL network, identified stable components are linked to cell-fate biology.

IV. DISCUSSION

  • In all tested cases, network reduction agreed with sampled attractors and outperformed state-space sampling in attractors or quasi-attractors found and computational time.Figure 9 compares completion times; the broader comparison also includes attractors or quasi-attractors found.Source: Figure 9 · p. 13, §IV · p. 13
  • Potential unstable-oscillation SCCs were absent in approximately 90% of networks and few in the rest; sampling found none actually oscillating.The authors say the SCC criteria are sufficient, not necessary, and call for more stringent identification conditions.Source: Figure 10 · p. 13, §IV · p. 14
  • The method shifts complexity from state-space size to network cycle count, allowing analysis of systems an order of magnitude larger than full state-space searches.The authors state that the method does not eliminate attractor-finding complexity; it transfers that complexity to the number of network cycles.Source: §IV · pp. 12–13
  • For most random networks, reduction predicted which nodes stabilize and oscillate, though incomplete oscillations can leave downstream nodes fixed without a stable motif.Such fixed-state nodes are one reason the predicted repertoire is not guaranteed by stable motifs alone.Source: §IV · pp. 13–14
  • Incomplete oscillations can produce fixed-state nodes outside stable motifs, and identifying these sets remains future work.The authors describe this configuration as rare in their ensembles and say the method needs generalizing to identify such fixed-state sets.Source: §IV · pp. 13–14
  • The identified T-LGL stable motifs relate to survival and cytokine biology; leukemia fate requires the PDGFR-S1P-SPHK1-Ceramide state ON, ON, ON, OFF.The cited discussion links the motifs to T-LGL survival and cytokine control, and specifies this state as necessary for leukemia fate.Source: §IV · p. 14

Appendix A - Proof of the conservation of attractors by the expanded network/network reduction method

The proof shows that stable-motif reduction preserves the stabilized states of each attractor and leaves the remaining nodes in or downstream of oscillating motifs. It constructs the reducible stabilized subset from nodes that do not depend on oscillating nodes to stabilize.

Assumptions

  • The proof assumes nonconstant Boolean functions, genuine dependence on stated inputs, and a condition on disjunctive clauses; the authors state these conditions can be imposed without loss of generality.Source: Appendix A · p. 15

Stable motifs

  • A stable motif fixes the corresponding node states independently of nodes outside the motif, making those states partial fixed points of the Boolean rules.The proof identifies motifs as source strongly connected components in the expanded representation.Source: Appendix A · p. 15
  • Conversely, node states unchanged by updating regardless of outside-node states correspond to stable motifs, with any specified states not in those motifs downstream of them.Source: Appendix A · pp. 15–16

Attractor properties

  • In an asynchronous attractor, stabilized nodes hold one value across its states, whereas oscillating nodes take both values; their update rules must involve the corresponding stabilized or oscillating inputs.Oscillating nodes cannot be maintained by clauses involving only stabilized-node states.Source: Appendix A · p. 16

Constructing Sred

  • Sred comprises stabilized nodes whose stabilization does not depend on oscillating nodes or on stabilized nodes removed during the iterative construction.The construction repeatedly removes nodes lacking a rule clause supported only by the remaining stabilized nodes.Source: Appendix A · p. 17

Reduction behavior

  • Reduction of motifs built from Sred can stabilize only nodes in Sred, and any Sred node that stabilizes does so in its attractor state.Nodes in Sred not yet stabilized retain a rule clause depending only on the corresponding states of the remaining Sred nodes.Source: Appendix A · pp. 17–18

Oscillating motifs

  • If Sred is empty while oscillating nodes remain, the expanded network has oscillating motifs containing those nodes, with the other nodes downstream.The proof identifies source strongly connected components containing normal and complementary representations of oscillating nodes.Source: Appendix A · p. 18

Main theorem

  • For every attractor, reduction stabilizes a subset of its stabilized nodes in their attractor states, while every remaining node is in or downstream of an oscillating motif.The oscillating motif contains at least one node that oscillated in the original attractor.Source: Appendix A · p. 18

Appendix B - The full network reduction algorithm

The algorithm recursively reduces networks, searches their expanded representations for motifs, and branches on stable and oscillating components. It returns quasi-attractors, while marked cases may require further analysis to confirm a corresponding attractor.

Algorithm steps

  • For each source-node state combination, recursively reduce the network, build its expanded representation, and search for stable motifs and oscillating components.Source: Appendix B · pp. 18–19
  • For each stable motif, branch a network copy and recursively reduce it using that motif’s states as inputs.Source: Appendix B · p. 19
  • For oscillating components larger than two nodes, mark the component and downstream nodes; for two-node components, mark them only under specified downstream-motif conditions.Marked nodes remain undetermined and cannot be reduced in later steps.Source: Appendix B · p. 19
  • Repeat motif searches and reductions until no stable motifs remain; the resulting fixed-state assignments and undetermined-node rules form the quasi-attractors.Source: Appendix B · p. 19
  • Prune duplicate quasi-attractors, retaining the one with more marked nodes when otherwise equivalent.Source: Appendix B · p. 19

Attractor interpretation

  • Unmarked quasi-attractors necessarily correspond to Boolean-network attractors, whereas marked ones may not and require the undetermined nodes’ oscillation states to confirm.The uncertainty is associated with incomplete or unstable oscillations.Source: Appendix B · p. 19

Appendix C - The logical rules of the T-LGL leukemia survival network

This appendix lists the Boolean rules for the T-LGL leukemia survival signaling network. The rules were constructed from experimental results and adapted from earlier work.

Rule construction

  • The listed Boolean rules model the T-LGL leukemia survival signaling network and were constructed from experiments in healthy and leukemic cytotoxic T cells.The model was designed to reproduce knockout and overexpression experiment results.Source: Appendix C · pp. 19–20

Rule interpretation

  • Each rule’s NOT Apoptosis clause encodes that, in the apoptosis state, every node except Apoptosis is OFF.Source: Appendix C · p. 19

Rule sources

  • The rule table is adapted from, with cited for a detailed explanation of the rules.Source: Appendix C · p. 19

Appendix D - The attractors of T-LGL leukemia survival network

Table I summarizes node states for input-signal combinations with antigen present. It reports quasi-attractors rather than the full state sequences and transitions of attractors.

Table I

  • With Stimuli=ON, Table I covers all possible combinations of input signals and reports which nodes oscillate or stabilize.Source: Appendix D · p. 20
  • The table shows quasi-attractors, not the network states visited during oscillations or transitions between those states.Source: Appendix D · p. 20
  • The Apoptosis=ON attractor is omitted because it is always possible; unlisted combinations with CD45=OFF and IL15=OFF have apoptosis as their only attractor.Source: Appendix D · p. 20
Loading 1304.3467v2…