^{1,a)}and Réka Albert

^{1,2,b)}

### Abstract

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.

There is a great interest in understanding how the complex cellular behaviors in living organisms emerge from the underlying network of molecular interactions. Discrete dynamic models, a modeling paradigm in which the dynamical variables can only take discrete states, have been increasingly used to model systems with a large number of components. The feature that makes discrete dynamic models an attractive choice is their ability to reproduce the qualitative dynamics of the system using only the activating or inhibiting nature of the interactions; the knowledge of the rates of the biochemical processes involved is not required. Despite their simplicity, the main impediment in using discrete dynamic models for modeling large systems is combinatorial complexity. In this work, we offer a solution to this problem by introducing a novel network reduction approach. Our reduction approach uses a topological criterion in an augmented representation of the network to identify network components that take a fixed state, which can then be used to shrink the effective network size. A noteworthy virtue of our method is that it can be applied to large network sizes (up to size 200 and beyond). We have found that our method goes beyond reducing the size of the network and can predict the dynamical repertoire of the nodes (fixed states or oscillations).

This work was supported by NSF Grants IIS 1161001 and PHY 1205840. We would also like to thank Zhongyao Sun and Rui-Sheng Wang for fruitful discussions.

I. INTRODUCTION

II. PREDICTING THE STABLE DYNAMICAL REPERTOIRE OF A BOOLEAN MODEL OF A BIOLOGICAL NETWORK

A. Biological networks and discrete dynamic models

B. Finding the attractors of a Boolean model

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

D. Expanded network

E. Identifying stable motifs from the expanded network

F. Network reduction

G. Oscillations and oscillating components

III. RESULTS

A. T cell large granular lymphocyte leukemia network

B. Ensemble of random Boolean networks

IV. DISCUSSION

### Key Topics

- Attractors
- 86.0
- Genetic networks
- 18.0
- Intracellular signaling
- 18.0
- Networks
- 18.0
- Network topology
- 14.0

## Figures

Operations for the creation of the expanded network. (a) Node A has the update function . The addition of complementary nodes introduces a new node with update function . It also introduces a complementary node for node B, which makes the update function of A take the form . (b) Node A has the update function . The addition of composite nodes introduces a new node BC that represents the cooperative effect of B and C on A. (c) Node A has the update function . The two expansion operations introduce complementary nodes for A, B, and C, and a composite node for the AND relation between B and .

Operations for the creation of the expanded network. (a) Node A has the update function . The addition of complementary nodes introduces a new node with update function . It also introduces a complementary node for node B, which makes the update function of A take the form . (b) Node A has the update function . The addition of composite nodes introduces a new node BC that represents the cooperative effect of B and C on A. (c) Node A has the update function . The two expansion operations introduce complementary nodes for A, B, and C, and a composite node for the AND relation between B and .

Identification of stable motifs from the expanded network. (a) An example of a Boolean network. (b) The expanded network representation of the Boolean network in (a). (c) The two stable motifs in the expanded network, that is, the two smallest SCCs in the network that satisfy the requirements of not containing both a node and its complementary node, and containing all the inputs of every included composite node. Each stable motif indicates the fixed states of the corresponding subset of nodes of the Boolean network.

Identification of stable motifs from the expanded network. (a) An example of a Boolean network. (b) The expanded network representation of the Boolean network in (a). (c) The two stable motifs in the expanded network, that is, the two smallest SCCs in the network that satisfy the requirements of not containing both a node and its complementary node, and containing all the inputs of every included composite node. Each stable motif indicates the fixed states of the corresponding subset of nodes of the Boolean network.

An example of a component that has an unstable oscillation. This network has an attractor in which all the nodes oscillate and also has a steady state attractor. (a) The network and its respective Boolean rules. (b)The state transition graph of the network. The nodes of the state transition graph are the states of the system (written in the order A, B) and the edges represent allowed state transitions when only one node is updated. State 11 is a fixed point as there are no transitions going out of it. States 01, 00, and 10 form a complex attractor. (c) The expanded representation of the network. Note that {A, B, AB} forms a stable motif and that the whole expanded network forms an oscillating SCC.

An example of a component that has an unstable oscillation. This network has an attractor in which all the nodes oscillate and also has a steady state attractor. (a) The network and its respective Boolean rules. (b)The state transition graph of the network. The nodes of the state transition graph are the states of the system (written in the order A, B) and the edges represent allowed state transitions when only one node is updated. State 11 is a fixed point as there are no transitions going out of it. States 01, 00, and 10 form a complex attractor. (c) The expanded representation of the network. Note that {A, B, AB} forms a stable motif and that the whole expanded network forms an oscillating SCC.

An example of a node configuration in which a node can stabilize without the influence of an input signal or a stable motif. In this example, A and B oscillate in a complex attractor, but they do not take all possible states of their state transition graph in this attractor. Specifically, they miss the A = 1, B = 1 state. As a consequence node C stabilizes in the state C = 0. (a) The node configuration and their respective Boolean rules. (b) The state transition graph of nodes A and B. States 01, 00, and 10 form a complex attractor.

An example of a node configuration in which a node can stabilize without the influence of an input signal or a stable motif. In this example, A and B oscillate in a complex attractor, but they do not take all possible states of their state transition graph in this attractor. Specifically, they miss the A = 1, B = 1 state. As a consequence node C stabilizes in the state C = 0. (a) The node configuration and their respective Boolean rules. (b) The state transition graph of nodes A and B. States 01, 00, and 10 form a complex attractor.

The T-LGL leukemia survival signaling network. The shape of the nodes indicates the cellular location or the type of nodes: rectangles indicate intracellular components, ellipses indicate extracellular components, diamonds indicate receptors, and hexagons represent conceptual nodes (Stimuli, Stimuli2, P2, Cytoskeleton signaling, Proliferation, and Apoptosis). Node colors are used to distinguish input nodes (white), output nodes (black), and the rest of the nodes in the network (gray). An arrowhead or a short perpendicular bar at the end of an edge indicates activation or inhibition, respectively. This figure and its caption are adapted from Ref. 41 .

The T-LGL leukemia survival signaling network. The shape of the nodes indicates the cellular location or the type of nodes: rectangles indicate intracellular components, ellipses indicate extracellular components, diamonds indicate receptors, and hexagons represent conceptual nodes (Stimuli, Stimuli2, P2, Cytoskeleton signaling, Proliferation, and Apoptosis). Node colors are used to distinguish input nodes (white), output nodes (black), and the rest of the nodes in the network (gray). An arrowhead or a short perpendicular bar at the end of an edge indicates activation or inhibition, respectively. This figure and its caption are adapted from Ref. 41 .

The three stable motifs of the T-LGL leukemia network found most often during the reduction process. The actual motifs found and the states in which each of these motifs can stabilize vary depending on the active signals. We also show the input signals (white nodes) that affect these motifs directly or almost directly (for the motif in (c)). (a) The PDGFR-S1P-SPHK1-Ceramide motif, which represents the ceramide/sphingomyelin pathway and the platelet derived growth factor receptor. (b) The IFNG-P2 motif, which is related to the control of the cytokine interferon gamma in CTLs. (c) The TBET motif, which represents the regulation of the T-box transcription factor.

The three stable motifs of the T-LGL leukemia network found most often during the reduction process. The actual motifs found and the states in which each of these motifs can stabilize vary depending on the active signals. We also show the input signals (white nodes) that affect these motifs directly or almost directly (for the motif in (c)). (a) The PDGFR-S1P-SPHK1-Ceramide motif, which represents the ceramide/sphingomyelin pathway and the platelet derived growth factor receptor. (b) The IFNG-P2 motif, which is related to the control of the cytokine interferon gamma in CTLs. (c) The TBET motif, which represents the regulation of the T-box transcription factor.

Distribution function for the fraction of stabilized nodes in an attractor for N = 100 for an ensemble of networks. Note the logarithmic scale in the vertical axis.

Distribution function for the fraction of stabilized nodes in an attractor for N = 100 for an ensemble of networks. Note the logarithmic scale in the vertical axis.

Difference in the number of attractors found between the reduction and sampling methods. The squares represent the average difference in the number of attractors between the two methods, while the lower and higher limits of the bars represent the 20th and the 80th percentile of the distribution of attractor number difference. In all the cases, the difference is zero or positive, that is, the reduction method never finds less attractors than the sampling method. For all network sizes shown, an ensemble size of 100 networks was used.

Difference in the number of attractors found between the reduction and sampling methods. The squares represent the average difference in the number of attractors between the two methods, while the lower and higher limits of the bars represent the 20th and the 80th percentile of the distribution of attractor number difference. In all the cases, the difference is zero or positive, that is, the reduction method never finds less attractors than the sampling method. For all network sizes shown, an ensemble size of 100 networks was used.

Time performance of the different methods (see also the main text). (a) The average time it takes to find the attractors of a network for each method. Both axes are shown in a logarithmic scale. The bump shown in the N = 150 case for the reduction method is the consequence of a network in the ensemble that took an unusually long time because of the large number of cycles in the network. (b) Cumulative distribution functions for the completion times in the N = 100 ensemble. Note that the horizontal axis has a logarithmic scale.

Time performance of the different methods (see also the main text). (a) The average time it takes to find the attractors of a network for each method. Both axes are shown in a logarithmic scale. The bump shown in the N = 150 case for the reduction method is the consequence of a network in the ensemble that took an unusually long time because of the large number of cycles in the network. (b) Cumulative distribution functions for the completion times in the N = 100 ensemble. Note that the horizontal axis has a logarithmic scale.

Distribution function for the number of components that can display unstable oscillations in the N = 100 ensemble. Note the logarithmic scale in the vertical axis. For approximately 90% of the networks, we find no such components. For the rest, there are usually very few of them, with attractor sampling methods suggesting that none of them actually display unstable oscillations.

Distribution function for the number of components that can display unstable oscillations in the N = 100 ensemble. Note the logarithmic scale in the vertical axis. For approximately 90% of the networks, we find no such components. For the rest, there are usually very few of them, with attractor sampling methods suggesting that none of them actually display unstable oscillations.

The PDGFR-S1P-SPHK1-Ceramide motif, its allowed stable states, and the cell fates associated to them. For both set of stable states, the apoptosis cell fate can be reached depending on the signals present, the asynchronous update order, and on the initial state. On the other hand, the T-LGL leukemia cell fate can only be reached if the motif stabilizes in the {PDGFR = S1P = SPHK1 = ON, Ceramide = OFF} state, regardless of the signals present, the asynchronous update order or of the initial state.

The PDGFR-S1P-SPHK1-Ceramide motif, its allowed stable states, and the cell fates associated to them. For both set of stable states, the apoptosis cell fate can be reached depending on the signals present, the asynchronous update order, and on the initial state. On the other hand, the T-LGL leukemia cell fate can only be reached if the motif stabilizes in the {PDGFR = S1P = SPHK1 = ON, Ceramide = OFF} state, regardless of the signals present, the asynchronous update order or of the initial state.

## Tables

The attractors of T-LGL leukemia survival network. This table shows the state of the nodes for all possible combinations of input signals in the presence of antigen (Stimuli = ON).

The attractors of T-LGL leukemia survival network. This table shows the state of the nodes for all possible combinations of input signals in the presence of antigen (Stimuli = ON).

Article metrics loading...

Full text loading...

Commenting has been disabled for this content