GraphCrunch
GraphCrunch is a comprehensive, parallelizable, and easily extendible open source software tool for analyzing and modeling large biological networks (or graphs); it compares real-world networks against a series of random graph models with respect to a multitude of local and global network properties.[1] It is available here.
Motivation
[edit]Recent technological advances in experimental biology have yielded large amounts of biological network data. Many other real-world phenomena have also been described in terms of large networks (also called graphs), such as various types of social and technological networks. Thus, understanding these complex phenomena has become an important scientific problem that has led to intensive research in network modeling and analyses.
An important step towards understanding biological networks is finding an adequate network model. Evaluating the fit of a model network to the data is a formidable challenge, since network comparisons are computationally infeasible and thus have to rely on heuristics, or "network properties." GraphCrunch automates the process of generating random networks drawn from a series of random graph models and evaluating the fit of the network models to a real-world network with respect to a variety of global and local network properties.
Features
[edit]GraphCrunch performs the following tasks:
1) computes user specified global and local properties of an input real-world network,
2) creates a user specified number of random networks belonging to user specified random graph models,
3) compares how closely each model network reproduces a range of global and local properties (specified in point 1 above) of the real-world network, and
4) produces the statistics of network property similarities between the data and the model networks.
Network models supported by GraphCrunch
[edit]GraphCrunch currently supports five different types of random graph models:
- Erdös-Rényi random graphs;
- random graphs with the same degree distribution as the data;
- Barabási-Albert preferential-attachment scale-free networks;
- n-dimensional geometric random graphs (for all positive integers n); and
- stickiness model networks.
Network properties supported by GraphCrunch
[edit]GraphCrunch currently supports seven global and local network properties:
- degree distribution;
- clustering coefficient;
- clustering spectrum;
- average diameter;
- spectrum of shortest path lengths;
- relative graphlet frequency distance; and
- graphlet degree distribution agreement.
Installation and usage
[edit]Instructions on how to install and run GraphCrunch are available at https://web.archive.org/web/20100717040957/http://www.ics.uci.edu/~bio-nets/graphcrunch/.
Applications
[edit]GraphCrunch has been used to find an optimal network model for protein-protein interaction networks,[2][3] as well as for protein structure networks.[3][4]
References
[edit]- ^ Tijana Milenković, Jason Lai, and Nataša Pržulj, GraphCrunch: a tool for large network analyses, BMC Bioinformatics 2008, 9:70. Highly accessed.
- ^ Oleksii Kuchaiev, Tijana Milenković, Vesna Memisević, Wayne Hayes, and Nataša Pržulj, Topological network alignment uncovers biological function and phylogeny, Journal of the Royal Society Interface, 2010, to appear.
- ^ a b Vesna Memisević, Tijana Milenković, and Nataša Pržulj, An integrative approach to modeling biological networks, Proceedings of the 6th International Symposium on Integrative Bioinformatics, 22–24 March 2010, Cambridge, United Kingdom. Journal of Integrative Bioinformatics, 2010, to appear.
- ^ Tijana Milenković, Ioannis Filippis, Michael Lappe, and Nataša Pržulj, Optimized Null Model for Protein Structure Networks, 2009, PLOS One 4(6): e5967.