Bioinformatics Advance Access originally published online on November 15, 2007
Bioinformatics 2008 24(2):282-284; doi:10.1093/bioinformatics/btm554
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Computing topological parameters of biological networks
Department of Computational Biology and Applied Algorithmics, Max Planck Institute for Informatics, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany
*To whom correspondence should be addressed.
 |
ABSTRACT |
|---|
 TOP ABSTRACT 1 INTRODUCTION2 PROGRAM OVERVIEW3 CONCLUSIONSACKNOWLEDGEMENTSREFERENCES |
|---|
Summary: Rapidly increasing amounts of molecular interaction data are being produced by various experimental techniques and computational prediction methods. In order to gain insight into the organization and structure of the resultant large complex networks formed by the interacting molecules, we have developed the versatile Cytoscape plugin NetworkAnalyzer. It computes and displays a comprehensive set of topological parameters, which includes the number of nodes, edges, and connected components, the network diameter, radius, density, centralization, heterogeneity, and clustering coefficient, the characteristic path length, and the distributions of node degrees, neighborhood connectivities, average clustering coefficients, and shortest path lengths. NetworkAnalyzer can be applied to both directed and undirected networks and also contains extra functionality to construct the intersection or union of two networks. It is an interactive and highly customizable application that requires no expert knowledge in graph theory from the user.
Availability: NetworkAnalyzer can be downloaded via the Cytoscape web site: http://www.cytoscape.org
Contact: mario.albrecht{at}mpi-inf.mpg.de
Supplementary information: Supplementary data are available at Bioinformatics online.
|
1 INTRODUCTION |
|---|
|
TOPABSTRACT1 INTRODUCTION2 PROGRAM OVERVIEW3 CONCLUSIONSACKNOWLEDGEMENTSREFERENCES |
|---|
In recent years, high-throughput experiments have produced large networks of interacting molecules, which are represented as nodes linked by edges in complex graphs (Albrecht et al., 2005; Ramírez et al., 2007; Zhu et al., 2007). In this context, the characterization of biological networks by means of graph-topological properties has become very popular for gaining insight into the global network structure (Albert, 2005; Almaas, 2007; Barabasi and Oltvai, 2004; Dong and Horvath, 2007; Zhu et al., 2007). However, general software libraries for graph analysis such as JUNG (http://jung.sourceforge.net/), LEDA (http://algorithmic-solutions.com/enleda.htm), NetworkX (https://networkx.lanl.gov/) and yFiles (http://www.yworks.com/) are not easily applied by the biological user. Other applications like Pajek (Batagelj and Mrvar, 1998) require expert knowledge in graph theory on the user side. Specialized tools for the analysis of biological networks like CentiBiN (Junker et al., 2006), tYNA/TopNet (Yip et al., 2006; Yu et al., 2004) and VisANT (Hu et al., 2005) calculate only a limited set of topological parameters.
Therefore, we have developed NetworkAnalyzer, a user-friendly Java plugin for Cytoscape (Shannon et al., 2003), which is an established free open-source software platform for the visualization and analysis of molecular interaction networks (Shannon et al., 2003). An initial release of NetworkAnalyzer was made available in January 2006. In the following, we describe the basic functionality of NetworkAnalyzer and numerous extensions and improvements of the next major release.
|
2 PROGRAM OVERVIEW |
|---|
|
TOPABSTRACT1 INTRODUCTION2 PROGRAM OVERVIEW3 CONCLUSIONSACKNOWLEDGEMENTSREFERENCES |
|---|
NetworkAnalyzer efficiently computes a large number of topological network parameters for directed and undirected networks loaded into Cytoscape. The user can decide whether directed edges should be treated as undirected for the analysis. The computed simple and complex topology parameters are represented as single values and distributions, respectively. Simple parameters are the number of nodes, edges, self-loops, and connected components, the average number of neighbors, the network diameter, radius, density, centralization, heterogeneity, and clustering coefficient, the number of shortest paths, and the characteristic path length. Complex parameters are distributions of node degrees, neighborhood connectivities, average clustering coefficients, topological coefficients, shortest path lengths, and shared neighbors of two nodes. NetworkAnalyzer utilizes the free Java libraries JFreeChart (http://jfree.org/jfreechart/) and Batik (http://xmlgraphics.apache.org/batik/) to display the distributions as histograms or scatter plots (Fig. 1) and to export them as chart images in the formats JPG/PNG/SVG or as tables in plain text files. Details on the formal definitions of all topological parameters are given in the online help page of the plugin. To ensure the validity of the calculations performed by NetworkAnalyzer, the computed parameters were compared with those obtained from Pajek, TopNet, and using the Python graph library NetworkX.
|
While the majority of the topological parameters included in NetworkAnalyzer is already well known and frequently used in the literature, our plugin additionally computes some novel network properties. In particular, we have extended the original definition of neighborhood connectivity (Maslov and Sneppen, 2002) to directed networks by introducing three types of related connectivity parameters, see Supplementary Data for more details. NetworkAnalyzer is also capable of enumerating the shared neighbors of all node pairs in a network. As an application of that, the Supplementary Data describes the use of the shared neighbors distribution to detect bias in the topology of predicted human networks of protein–protein interactions in comparison to experimentally derived networks.
Further unique features of NetworkAnalyzer comprise various visual settings of the obtained diagrams (Fig. 1). The user has the option of switching between histogram or scatter plot of the computed distributions and between linear or logarithmic scales for any of the two displayed diagram axes. Gridlines can be enabled or disabled, and a power law can be fitted to resultant distributions. Additionally, the title of the chart diagram, the labels of the axes, and the colors of the scatter points and gridlines can be configured.
Topology parameters computed for network nodes are stored as node attributes in the Cytoscape data structure. Thus, users can easily apply the visual mapping settings of Cytoscape to highlight any parameter on the screen (see online tutorial). For example, the clustering coefficient may be visualized proportional to the node size, and the node color may be related to its degree. Another useful application of NetworkAnalyzer is the selection of nodes based on any of the calculated attributes. This enables Cytoscape users to examine, for instance, structural perturbations in a network caused by the removal of nodes with high degrees.
In NetworkAnalyzer, the complete set of simple and complex parameters is referred to as network statistics. Once calculated and displayed, the network statistics can be saved into and reloaded from a text file in order to avoid recomputation. The comparison of multiple network topologies can easily be achieved by the parallel inspection of the computed statistics for different networks. Optional user settings can be stored and reloaded. Users can customize the appearance of the results by choosing between two alternative dialog interfaces, the compact one shown in Fig. 1 and an expandable interface. Aside from parameter computations, NetworkAnalyzer offers a useful set of network modifications and supports the construction of the intersection, union, and difference of two networks, the extraction of connected components as new separate networks, and the removal of self-loops.
|
3 CONCLUSIONS |
|---|
|
TOPABSTRACT1 INTRODUCTION2 PROGRAM OVERVIEW3 CONCLUSIONSACKNOWLEDGEMENTSREFERENCES |
|---|
NetworkAnalyzer is a versatile and user-friendly tool for the analysis of biological and other networks. This plugin is well integrated into Cytoscape and computes a comprehensive list of simple and complex topology parameters using efficient graph algorithms. It incorporates useful visualization settings to display and export the resulting distributions and adds node attributes for the results.
|
ACKNOWLEDGEMENTS |
|---|
|
TOPABSTRACT1 INTRODUCTION2 PROGRAM OVERVIEW3 CONCLUSIONSACKNOWLEDGEMENTSREFERENCES |
|---|
Part of this work has been financially supported by the German National Genome Research Network (NGFN) and the German Research Foundation (DFG), contract number KFO 129/1-1. The research has been conducted in the context of the BioSapiens Network of Excellence funded by the European Commission under grant number LSHG-CT-2003-503265.
Conflict of Interest: none declared.
|
FOOTNOTES |
|---|
Associate Editor: Martin Bishop
Received on June 16, 2007; revised on October 8, 2007; accepted on November 1, 2007
|
REFERENCES |
|---|
|
TOPABSTRACT1 INTRODUCTION2 PROGRAM OVERVIEW3 CONCLUSIONSACKNOWLEDGEMENTSREFERENCES |
|---|
Albert R. Scale-free networks in cell biology. J. Cell Sci. (2005) 118:4947–4957.
Albrecht M, et al. Decomposing protein networks into domain-domain interactions. Bioinformatics (2005) 21(Suppl. 2):ii220–ii221.[Abstract]
Almaas E. Biological impacts and context of network theory. J. Exp. Biol. (2007) 210:1548–1558.
Barabasi AL, Oltvai ZN. Network biology: understanding the cell's functional organization. Nat. Rev. Genet. (2004) 5:101–113.[CrossRef][Web of Science][Medline]
Batagelj V, Mrvar A. Pajek – program for large network analysis. Connections (1998) 21:47–57.
Dong J, Horvath S. Understanding network concepts in modules. BMC Syst. Biol. (2007) 1:24.[CrossRef][Medline]
Hu Z, et al. VisANT: data-integrating visual framework for biological networks and modules. Nucleic Acids Res. (2005) 33:W352–W357.
Junker BH, et al. Exploration of biological network centralities with CentiBiN. BMC Bioinformatics (2006) 7:219.[CrossRef][Medline]
Lim J, et al. A protein-protein interaction network for human inherited ataxias and disorders of purkinje cell degeneration. Cell (2006) 125:801–814.[CrossRef][Web of Science][Medline]
Maslov S, Sneppen K. Specificity and stability in topology of protein networks. Science (2002) 296:910–913.
Ramírez F, et al. Computational analysis of human protein interaction networks. Proteomics (2007) 7:2541–2552.[CrossRef][Web of Science][Medline]
Shannon P, et al. Cytoscape: a software environment for integrated models of biomolecular interaction networks. Genome Res. (2003) 13:2498–2504.
Yip KY, et al. The tYNA platform for comparative interactomics: a web tool for managing, comparing and mining multiple networks. Bioinformatics (2006) 22:2968–2970.
Yu H, et al. TopNet: a tool for comparing biological sub-networks, correlating protein properties with topological statistics. Nucleic Acids Res. (2004) 32:328–337.
Zhu X, et al. Getting connected: analysis and principles of biological networks. Genes Dev. (2007) 21:1010–1024.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  G. Scardoni, M. Petterlini, and C. Laudanna Analyzing biological network parameters with CentiScaPe Bioinformatics, November 1, 2009; 25(21): 2857 - 2859. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J. Gu, Y. Wang, and T. Lilburn A Comparative Genomics, Network-Based Approach to Understanding Virulence in Vibrio cholerae J. Bacteriol., October 15, 2009; 191(20): 6262 - 6272. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 Y. Hayashi, T. Senda, N. Sano, and M. Horikoshi Theoretical framework for the histone modification network: modifications in the unstructured histone tails form a robust scale-free network Genes Cells, July 1, 2009; 14(7): 789 - 806. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 P. Minguez, S. Gotz, D. Montaner, F. Al-Shahrour, and J. Dopazo SNOW, a web-based tool for the statistical analysis of protein-protein interaction networks Nucleic Acids Res., July 1, 2009; 37(suppl_2): W109 - W114. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. H. Beck, I. Espinosa, B. Edris, R. Li, K. Montgomery, S. Zhu, S. Varma, R. J. Marinelli, M. van de Rijn, and R. B. West The Macrophage Colony-Stimulating Factor 1 Response Signature in Breast Carcinoma Clin. Cancer Res., February 1, 2009; 15(3): 778 - 787. [Abstract] [Full Text] [PDF]
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||