Finding local communities in protein networks
Open Access
- 18 September 2009
- journal article
- research article
- Published by Springer Nature in BMC Bioinformatics
- Vol. 10 (1) , 1-14
Abstract
Background: Protein-protein interactions (PPIs) play fundamental roles in nearly all biological processes, and provide major insights into the inner workings of cells. A vast amount of PPI data for various organisms is available from BioGRID and other sources. The identification of communities in PPI networks is of great interest because they often reveal previously unknown functional ties between proteins. A large number of global clustering algorithms have been applied to protein networks, where the entire network is partitioned into clusters. Here we take a different approach by looking for local communities in PPI networks. Results: We develop a tool, named Local Protein Community Finder, which quickly finds a community close to a queried protein in any network available from BioGRID or specified by the user. Our tool uses two new local clustering algorithms Nibble and PageRank-Nibble, which look for a good cluster among the most popular destinations of a short random walk from the queried vertex. The quality of a cluster is determined by proportion of outgoing edges, known as conductance, which is a relative measure particularly useful in undersampled networks. We show that the two local clustering algorithms find communities that not only form excellent clusters, but are also likely to be biologically relevant functional components. We compare the performance of Nibble and PageRank-Nibble to other popular and effective graph partitioning algorithms, and show that they find better clusters in the graph. Moreover, Nibble and PageRank-Nibble find communities that are more functionally coherent. Conclusion: The Local Protein Community Finder, accessible at http://xialab.bu.edu/resources/lpcf, allows the user to quickly find a high-quality community close to a queried protein in any network available from BioGRID or specified by the user. We show that the communities found by our tool form good clusters and are functionally coherent, making our application useful for biologists who wish to investigate functional modules that a particular protein is a part of.Keywords
This publication has 39 references indexed in Scilit:
- VisANT 3.5: multi-scale network visualization, analysis and inference based on the gene ontologyNucleic Acids Research, 2009
- Markov clustering versus affinity propagation for the partitioning of protein interaction graphsBMC Bioinformatics, 2009
- High-Quality Binary Protein Interaction Map of the Yeast Interactome NetworkScience, 2008
- Gene Ontology annotations at SGD: new data sources and annotation methodsNucleic Acids Research, 2007
- Global landscape of protein complexes in the yeast Saccharomyces cerevisiaeNature, 2006
- BioGRID: a general repository for interaction datasetsNucleic Acids Research, 2006
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005
- Protein complexes and functional modules in molecular networksProceedings of the National Academy of Sciences, 2003
- Spectral partitioning with multiple eigenvectorsDiscrete Applied Mathematics, 1999
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998