Cargando…

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 com...

Descripción completa

Detalles Bibliográficos
Autores principales: Kuchaiev, Oleksii, Stevanović, Aleksandar, Hayes, Wayne, Pržulj, Nataša
Formato: Texto
Lenguaje:English
Publicado: BioMed Central 2011
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3036622/
https://www.ncbi.nlm.nih.gov/pubmed/21244715
http://dx.doi.org/10.1186/1471-2105-12-24
_version_ 1782197876462452736
author Kuchaiev, Oleksii
Stevanović, Aleksandar
Hayes, Wayne
Pržulj, Nataša
author_facet Kuchaiev, Oleksii
Stevanović, Aleksandar
Hayes, Wayne
Pržulj, Nataša
author_sort Kuchaiev, Oleksii
collection PubMed
description 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.
format Text
id pubmed-3036622
institution National Center for Biotechnology Information
language English
publishDate 2011
publisher BioMed Central
record_format MEDLINE/PubMed
spelling pubmed-30366222011-02-10 GraphCrunch 2: Software tool for network modeling, alignment and clustering Kuchaiev, Oleksii Stevanović, Aleksandar Hayes, Wayne Pržulj, Nataša BMC Bioinformatics Software 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. BioMed Central 2011-01-19 /pmc/articles/PMC3036622/ /pubmed/21244715 http://dx.doi.org/10.1186/1471-2105-12-24 Text en Copyright © 2011 Kuchaiev et al; licensee BioMed Central Ltd. https://creativecommons.org/licenses/by/2.0/This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0 (https://creativecommons.org/licenses/by/2.0/) ), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Software
Kuchaiev, Oleksii
Stevanović, Aleksandar
Hayes, Wayne
Pržulj, Nataša
GraphCrunch 2: Software tool for network modeling, alignment and clustering
title GraphCrunch 2: Software tool for network modeling, alignment and clustering
title_full GraphCrunch 2: Software tool for network modeling, alignment and clustering
title_fullStr GraphCrunch 2: Software tool for network modeling, alignment and clustering
title_full_unstemmed GraphCrunch 2: Software tool for network modeling, alignment and clustering
title_short GraphCrunch 2: Software tool for network modeling, alignment and clustering
title_sort graphcrunch 2: software tool for network modeling, alignment and clustering
topic Software
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3036622/
https://www.ncbi.nlm.nih.gov/pubmed/21244715
http://dx.doi.org/10.1186/1471-2105-12-24
work_keys_str_mv AT kuchaievoleksii graphcrunch2softwaretoolfornetworkmodelingalignmentandclustering
AT stevanovicaleksandar graphcrunch2softwaretoolfornetworkmodelingalignmentandclustering
AT hayeswayne graphcrunch2softwaretoolfornetworkmodelingalignmentandclustering
AT przuljnatasa graphcrunch2softwaretoolfornetworkmodelingalignmentandclustering