Abstract

Summary: NetDS is a novel Cytoscape plugin that conveniently simulates dynamics related to robustness, and examines structural properties with respect to feedforward/feedback loops. It can evaluate how robustly a network sustains a stable state against mutations by employing a Boolean network model. In addition, the plugin can examine all feedforward/feedback loops appearing in a network and determine whether or not a pair of loops is coupled. Random networks can also be generated to evaluate whether or not an interesting finding in real biological networks is significantly random.

Availability: NetDS is freely available for non-commercial purposes at http://netds.sourceforge.net/.

Contact:kwonyk@ulsan.ac.kr

Supplementary information:Supplementary data are available at Bioinformatics online.

1 INTRODUCTION

Cytoscape (Shannon et al., 2003) is a free open-source software platform that is used to visualize complex networks. Many Cytoscape plugins have been developed for structural analysis of biological networks. For example, MCODE (Bader and Hogue, 2003), BiNoM (Zinovyev et al., 2008) and NeMo (Rivera et al., 2010) were developed to search specific sub-structures in a network including active parts or densely connected regions. Network-Motif-Finder (Taylor et al., 2007) has also been employed to uncover simple network motifs such as small-scale feedforward loops. The motif search function was further extended in NetMatch (Ferro et al., 2007) by enabling a user to query more flexible forms of motifs. Plugins to analyze the dynamics of a biological network also exist. For example, PerturbationAnalyzer (Li et al., 2009) can evaluate the propagation effect of perturbations on interaction networks by computing changes in the equilibrium state. SimBoolNet (Zheng et al., 2010) can examine the dynamics of a signaling transduction pathway using a Boolean network.

However, there are no plugins that may be used to investigate the relationships between the structural characteristics of networks and network dynamics. Considering that the dynamical behavior of a biological network is closely related to its structural characteristics (Kremling et al., 2008; Kwon et al., 2007; Prill et al., 2005), there is a pressing need to develop such plugins that can analyze relationships between the structural characteristics and dynamics of a network. In particular, recent studies indicate that the ability of a network to sustain a stable state against mutations is greatly affected by complex motifs such as feedback loops (FBLs) and feedforward loops (FFLs) harbored by the network. For example, robust networks tend to have a larger number of positive FBLs and a smaller number of negative FBLs (Kwon and Cho, 2008b) The number of FBLs involving a node is also positively correlated with the functional importance of the node (Kwon et al., 2007), and the coherent coupling of FBLs is a design principle of a robust cell signaling network (Kwon and Cho 2008a). FFLs are needed for robust carbohydrate uptake in Escherichia coli (Kremling et al., 2008). Inspired by those studies, we have developed a plugin, NetDS, to analyze the structural characteristics of biological networks with respect to FBLs or FFLs and to compute dynamics related to robustness.

A random Boolean network (RBN) model is employed which has been effectively used for investigating the complex dynamics of biological networks (Kauffman et al., 2003; Kwon et al., 2007; Shmulevich et al., 2003). In fact, SimBoolNet has already been implemented in an RBN model to simulate the dynamics of signaling transduction. More specifically, SimBoolNet observes the response of downstream molecules simulated for a user-specified stimulus for a signal receptor. However, it cannot provide any dynamics related to attractors to which a network will converge since it simply provides the time-series of changes of node values. As such, the robustness of the network against perturbations cannot be calculated. To overcome this limitation, NetDS was designed to analyze the converging state of a network and its robustness against perturbations. In terms of structural analysis, NetDS can analyze both the FBLs/FFLs that appear in a network and detailed properties such as the sign of an FBL, the signs of simple paths comprising an FFL, and the coherence of coupled FBLs or FFLs. In addition, FBL/FFLs containing specific nodes cannot be easily checked with existing plugins. Altogether, NetDS provides a combined analysis of structural properties with respect to FBL/FFLs and dynamics related to robustness.

2 METHODS AND IMPLEMENTATION

2.1 A Boolean network model

A Boolean network is represented with a directed graph G(V, A), where V is a set of Boolean variables and A is a set of ordered pairs of the Boolean variables called directed links. Each viV has a value of 1 (‘on’) or 0 (‘off’) which represents the possible states of the corresponding elements. A directed link (vi, vj) has a positive (‘activating’) or negative (‘inhibiting’) relationship from vi to vj. The value of each variable vi at time t+ 1 is determined by the values of ki other variables with a link to vi at time t by the Boolean function fi : {0, 1}ki→ {0, 1}; all variables are synchronously updated (See Supporting Definitions in Supplementary Material for more details).

2.2 Robustness-related dynamics

In NetDS, we focus on converging dynamics and network robustness against perturbations in terms of Boolean dynamics. Given a Boolean network G(V, A) with V={v0, v1,…, vN−1}, a state of G is defined as a vector of values v0 through vN−1. A state trajectory starts from an initial state and eventually converges to either a fixed-point or limit-cycle attractor. These attractors can represent diverse biological network behaviors such as multi-stability, homeostasis and oscillation. Therefore, the change in the converging attractor can be interpreted as a loss of robustness. Here, we considered two types of perturbations: an initial-state perturbation and an update-rule perturbation. We define the robustness of a node vi against the initial-state perturbation and the update-rule perturbation, denoted as γs(vi) and γr(vi), respectively. Based on them, the robustness of a network G against the initial-state perturbation and the update-rule perturbation, denoted as γs(G) and γr(G), respectively, is calculated (See Supporting Definitions in Supplementary Material for more details).

Unfortunately, it is very time-consuming to compute converging attractors over all possible initial states. To reduce the computation time, we introduced a more effective algorithm in NetDS by avoiding redundant computations (See Supporting Pseudo-codes in Supplementary Material). Based on the module used to compute the converging attractor, NetDS can calculate γs(v), γr(v), γs(G), and γr(G) efficiently (See Supporting Pseudo-codes in Supplementary Material).

2.3 Detection of FBLs and FFLs

In NetDS, a user can search FBLs and FFLs for a specified length (See Supporting Definitions in Supplementary Material for more details). This function was simply implemented using a breadth-first search, which is a kind of graph traversal method. For a dense large network, it will take a long time to detect all FBLs and FFLs. Therefore, the maximum length of the FFLs or FBLs should be specified as a constraint.

2.4 Generation of random Boolean networks

When a real biological network is loaded into Cytoscape, NetDS can analyze the dynamics and FBL/FFL structures of the network. However, extensive simulations over a number of random networks are needed to determine whether or not some observations in the real biological network are significantly random. To this end, NetDS provides three random network generation models: a Barabási–Albert model (Barabasi and Albert, 1999), a Erdõs–Rényi model (Erdösand Rényi, 1959) and a Erdõs–Rényi variant model (See Supporting Pseudo-codes in Supplementary Material).

3 APPLICATION EXAMPLE

NetDS shows the analysis results about robustness-related dynamics and FBL/FFLs-related structures through individual control panels in Cytoscape (Fig. 1). The efficiency of NetDS was demonstrated through some case studies where the results of the previous studies were validated by NetDS (See Supporting Results in Supplementary Material for more details).

Fig. 1.

A sample NetDS-based analysis on cell differentiation regulatory network (Huang and Ingber, 2000). NetDS has two control panels. One is to examine dynamical properties (finding attractors and calculating robustness) and the other is to detect structural properties with respect to FBL and FFL. A relationship between dynamical properties and structural properties can be discovered.

Fig. 1.

A sample NetDS-based analysis on cell differentiation regulatory network (Huang and Ingber, 2000). NetDS has two control panels. One is to examine dynamical properties (finding attractors and calculating robustness) and the other is to detect structural properties with respect to FBL and FFL. A relationship between dynamical properties and structural properties can be discovered.

4 CONCLUSION

Many recent results have shown that robust behavior against perturbations is closely related to structural properties with respect to the FBL/FFLs in biological networks. In this regard, we developed a novel Cytoscape plugin that can compute network robustness against initial-state or update-rule perturbations and examine FBL/FFLs harbored in a network. NetDS is the first Cytoscape plugin to investigate the relationships between dynamic and structural properties in a network. In the future, NetDS will be extended to include a variety of perturbation types and update-rules that can be applied to dynamics analysis.

Funding: This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (2010-0010533).

Conflict of Interest: none declared.

REFERENCES

Bader
G.
Hogue
C.
An automated method for finding molecular complexes in large protein interaction networks
BMC Bioinformatics
 , 
2003
, vol. 
4
 pg. 
2
 
Barabasi
A.L.
Albert
R.
Emergence of scaling in random networks
Science
 , 
1999
, vol. 
286
 (pg. 
509
-
512
)
Erdös
P.
Rényi
A.
On random graphs, I
Publicationes Mathematicae
 , 
1959
, vol. 
6
 (pg. 
290
-
297
)
Ferro
A.
, et al.  . 
NetMatch: a Cytoscape plugin for searching biological networks
Bioinformatics
 , 
2007
, vol. 
23
 (pg. 
910
-
912
)
Huang
S.
Ingber
D.E.
Shape-dependent control of cell growth, differentiation, and apoptosis: switching between attractors in cell regulatory networks
Exp. Cell Res.
 , 
2000
, vol. 
261
 (pg. 
91
-
103
)
Kauffman
S.
, et al.  . 
Random Boolean network models and the yeast transcriptional network
Proc. Natl Acad. Sci. USA
 , 
2003
, vol. 
100
 (pg. 
14796
-
14799
)
Kremling
A.
, et al.  . 
A feed-forward loop guarantees robust behavior in Escherichia coli carbohydrate uptake
Bioinformatics
 , 
2008
, vol. 
24
 (pg. 
704
-
710
)
Kwon
Y.-K.
Cho
K.-H.
Coherent coupling of feedback loops: a design principle of cell signaling networks
Bioinformatics
 , 
2008
, vol. 
24
 (pg. 
1926
-
1932
)
Kwon
Y.-K.
Cho
K.-H.
Quantitative analysis of robustness and fragility in biological networks based on feedback dynamics
Bioinformatics
 , 
2008
, vol. 
24
 (pg. 
987
-
994
)
Kwon
Y.-K.
, et al.  . 
Investigations into the relationship between feedback loops and functional importance of a signal transduction network based on Boolean network modeling
BMC Bioinformatics
 , 
2007
, vol. 
8
 pg. 
384
 
Li
F.
, et al.  . 
PerturbationAnalyzer: a tool for investigating the effects of concentration perturbation on protein interaction networks
Bioinformatics
 , 
2009
, vol. 
26
 (pg. 
275
-
277
)
Prill
R.J.
, et al.  . 
Dynamic properties of network motifs contribute to biological network organization
PLoS Biol.
 , 
2005
, vol. 
3
 pg. 
e343
 
Rivera
C.
, et al.  . 
NeMo: network module identification in Cytoscape
BMC Bioinformatics
 , 
2010
, vol. 
11
 pg. 
S61
 
Shannon
P.
, et al.  . 
Cytoscape: a software environment for integrated models of biomolecular interaction networks
Genome Res.
 , 
2003
, vol. 
13
 (pg. 
2498
-
2504
)
Shmulevich
I.
, et al.  . 
The role of certain post classes in Boolean network models of genetic networks
Proc. Natl Acad. Sci. USA
 , 
2003
, vol. 
100
 (pg. 
10734
-
10739
)
Taylor
R.J.
, et al.  . 
Network motif analysis of a multi-mode genetic-interaction network
Genome Biol.
 , 
2007
, vol. 
8
 pg. 
R160
 
Zheng
J.
, et al.  . 
SimBoolNet–a Cytoscape plugin for dynamic simulation of signaling networks
Bioinformatics
 , 
2010
, vol. 
26
 (pg. 
141
-
142
)
Zinovyev
A.
, et al.  . 
BiNoM: a Cytoscape plugin for manipulating and analyzing biological networks
Bioinformatics
 , 
2008
, vol. 
24
 (pg. 
876
-
877
)

Author notes

Associate Editor: Alfonso Valencia

Comments

0 Comments