GraphCrunch 2: Software tool for network modeling, alignment and clustering.
BACKGROUND
Recent advancements in experimental biotechnology have produced large amounts of protein-protein interaction (PPI) data. The topology of PPI networks is believed to have a strong link to their function. Hence, the abundance of PPI data for many organisms stimulates the development of computational techniques for the modeling, comparison, alignment, and clustering of networks. In addition, finding representative models for PPI networks will improve our understanding of the cell just as a model of gravity has helped us understand planetary motion. To decide if a model is representative, we need quantitative comparisons of model networks to real ones. However, exact network comparison is computationally intractable and therefore several heuristics have been used instead. Some of these heuristics are easily computable "network properties," such as the degree distribution, or the clustering coefficient. An important special case of network comparison is the network alignment problem. Analogous to sequence alignment, this problem asks to find the "best" mapping between regions in two networks. It is expected that network alignment might have as strong an impact on our understanding of biology as sequence alignment has had. Topology-based clustering of nodes in PPI networks is another example of an important network analysis problem that can uncover relationships between interaction patterns and phenotype.


RESULTS
We introduce the GraphCrunch 2 software tool, which addresses these problems. It is a significant extension of GraphCrunch which implements the most popular random network models and compares them with the data networks with respect to many network properties. Also, GraphCrunch 2 implements the GRAph ALigner algorithm ("GRAAL") for purely topological network alignment. GRAAL can align any pair of networks and exposes large, dense, contiguous regions of topological and functional similarities far larger than any other existing tool. Finally, GraphCruch 2 implements an algorithm for clustering nodes within a network based solely on their topological similarities. Using GraphCrunch 2, we demonstrate that eukaryotic and viral PPI networks may belong to different graph model families and show that topology-based clustering can reveal important functional similarities between proteins within yeast and human PPI networks.


CONCLUSIONS
GraphCrunch 2 is a software tool that implements the latest research on biological network analysis. It parallelizes computationally intensive tasks to fully utilize the potential of modern multi-core CPUs. It is open-source and freely available for research use. It runs under the Windows and Linux platforms.
Department of Computer Science, University of California, Irvine, CA, USA.
Oleksii
O
Kuchaiev
Aleksandar
A
Stevanović
Wayne
W
Hayes
Nataša
N
Pržulj
D000465:Algorithms; D016000:Cluster Analysis; D006801:Humans; D008954:Models, Biological; D025941:Protein Interaction Mapping / Q000379:methods*; D016415:Sequence Alignment; D012984:Software; D014764:Viral Proteins / Q000378:metabolism
D014764:Viral Proteins
Nucleic Acids Res. 2004 Jul 1;32(Web Server issue):W83-8
15215356
Cancer Inform. 2010 Jun 30;9:121-37
20628593
Bioinformatics. 2006 May 1;22(9):1152-3
16455747
Bioinformatics. 2009 Jun 15;25(12):i259-67
19477997
Nature. 2006 Mar 30;440(7084):631-6
16429126
Nature. 2005 Nov 3;438(7064):108-12
16267557
Cancer Inform. 2008;6:257-73
19259413
Nat Methods. 2009 Jan;6(1):47-54
19123269
Proteins. 2008 Aug 15;72(3):1030-7
18300252
Bioinformatics. 2004 Jul 22;20(11):1746-58
15001476
Science. 2004 Jan 23;303(5657):540-3
14704431
Bioinformatics. 2004 Dec 12;20(18):3508-15
15284103
BMC Bioinformatics. 2008 Mar 27;9:172
18371197
Bioinformatics. 2005 Sep 1;21(17):3572-4
16020473
Pac Symp Biocomput. 2010;:178-89
19908370
Bioinformatics. 2006 Dec 1;22(23):2968-70
17021160
BMC Bioinformatics. 2004 Feb 19;5:17
15028117
J R Soc Interface. 2010 Mar 6;7(44):423-37
19625303
J R Soc Interface. 2006 Oct 22;3(10):711-6
16971339
Proc Natl Acad Sci U S A. 2004 Oct 12;101(41):14689-94
15448202
Bioinformatics. 2005 Aug 15;21(16):3401-8
15985496
BMC Bioinformatics. 2008 Jan 30;9:70
18230190
Nucleic Acids Res. 2004 Jan 14;32(1):328-37
14724320
Bioinformatics. 2004 Dec 12;20(18):3710-5
15297299
Cell. 2005 Sep 23;122(6):957-68
16169070
Nature. 2000 Feb 10;403(6770):623-7
10688190
Bioinformatics. 2007 Jan 15;23(2):e177-83
17237089
Nat Genet. 2000 May;25(1):25-9
10802651
Genome Res. 2006 Sep;16(9):1169-81
16899655
PLoS Pathog. 2009 Sep;5(9):e1000570
19730696
Nature. 2006 Mar 30;440(7084):637-43
16554755
Genome Res. 2003 Nov;13(11):2498-504
14597658
Mol Cell Proteomics. 2007 Mar;6(3):439-50
17200106
Science. 2004 Mar 5;303(5663):1538-42
15001784
Proc Natl Acad Sci U S A. 2006 Jul 18;103(29):10967-72
16835301
Science. 1999 Oct 15;286(5439):509-12
10521342
Nucleic Acids Res. 2002 Apr 1;30(7):1575-84
11917018
Proc Natl Acad Sci U S A. 2005 Feb 8;102(6):1974-9
15687504
Science. 2003 Dec 5;302(5651):1727-36
14605208
Proc Natl Acad Sci U S A. 2000 Feb 1;97(3):1143-7
10655498
PLoS Comput Biol. 2009 Aug;5(8):e1000454
19662157
BMC Syst Biol. 2010 Jun 15;4:84
20550706
Nature. 2005 Oct 20;437(7062):1173-8
16189514
Science. 2002 Oct 25;298(5594):824-7
12399590
J R Soc Interface. 2010 Sep 6;7(50):1341-54
20236959