Bioinformatics Advance Access originally published online on June 4, 2004
Bioinformatics 2004 20(17):3013-3020; doi:10.1093/bioinformatics/bth351
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Bioinformatics vol. 20 issue 17 © Oxford University Press 2004; all rights reserved.
Protein complex prediction via cost-based clustering
ulj 1
1 Department of Computer Science, University of Toronto, Toronto, M5S 3G4, Canada and 2 Ontario Cancer Institute, Division of Cancer Informatics, Toronto, M5G 2M9, Canada
Received on April 6, 2004; revised on May 5, 2004; accepted on May 14, 2004
Advance Access Publication June 4, 2004
Motivation: Understanding principles of cellular organization and function can be enhanced if we detect known and predict still undiscovered protein complexes within the cell's protein–protein interaction (PPI) network. Such predictions may be used as an inexpensive tool to direct biological experiments. The increasing amount of available PPI data necessitates an accurate and scalable approach to protein complex identification.
Results: We have developed the Restricted Neighborhood Search Clustering Algorithm (RNSC) to efficiently partition networks into clusters using a cost function. We applied this cost-based clustering algorithm to PPI networks of Saccharomyces cerevisiae, Drosophila melanogaster and Caenorhabditis elegans to identify and predict protein complexes. We have determined functional and graph-theoretic properties of true protein complexes from the MIPS database. Based on these properties, we defined filters to distinguish between identified network clusters and true protein complexes.
Conclusions: Our application of the cost-based clustering algorithm provides an accurate and scalable method of detecting and predicting protein complexes within a PPI network.
Availability: The RNSC algorithm and data processing code are available upon request from the authors.
Supplementary Information: Supplementary data are available at http://www.cs.utoronto.ca/~juris/data/ppi04/
Contact: ij{at}uhnres.utoronto.ca
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  T. Milenkovic, V. Memisevic, A. K. Ganesan, and N. Przulj Systems-level cancer gene identification from protein interaction network topology applied to melanogenesis-related functional genomics data J R Soc Interface, March 6, 2010; 7(44): 423 - 437. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. H. Jung, B. Hyun, W.-H. Jang, H.-Y. Hur, and D.-S. Han Protein complex prediction based on simultaneous protein interaction network Bioinformatics, February 1, 2010; 26(3): 385 - 391. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 M. Mutwil, B. Usadel, M. Schutte, A. Loraine, O. Ebenhoh, and S. Persson Assembly of an Interactive Correlation Network for the Arabidopsis Genome Using a Novel Heuristic Clustering Algorithm Plant Physiology, January 1, 2010; 152(1): 29 - 43. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. Song and M. Singh How and when should interactome-derived clusters be used to predict functional modules and protein function? Bioinformatics, December 1, 2009; 25(23): 3143 - 3150. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
G. A. Pavlopoulos, C. N. Moschopoulos, S. D. Hooper, R. Schneider, and S. Kossida jClust: a clustering and visualization toolbox Bioinformatics, August 1, 2009; 25(15): 1994 - 1996. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 H. Chen, L. Ding, Z. Wu, T. Yu, L. Dhanapalan, and J. Y. Chen Semantic web for integrated network analysis in biomedicine Brief Bioinform, March 1, 2009; 10(2): 177 - 192. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
Y. Qi, F. Balem, C. Faloutsos, J. Klein-Seetharaman, and Z. Bar-Joseph Protein complex identification by supervised graph local clustering Bioinformatics, July 1, 2008; 24(13): i250 - i268. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. Brohee, K. Faust, G. Lima-Mendez, O. Sand, R. Janky, G. Vanderstocken, Y. Deville, and J. van Helden NeAT: a toolbox for the analysis of biological networks, clusters, classes and pathways Nucleic Acids Res., July 1, 2008; 36(suppl_2): W444 - W451. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. Ucar, I. Neuhaus, P. Ross-MacDonald, C. Tilford, S. Parthasarathy, N. Siemers, and R.-R. Ji Construction of a reference gene association network from multiple profiling data: application to data analysis Bioinformatics, October 15, 2007; 23(20): 2716 - 2724. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. Aittokallio and B. Schwikowski Graph-based methods for analysing networks in cell biology Brief Bioinform, September 1, 2006; 7(3): 243 - 255. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
N. Przulj, D. G. Corneil, and I. Jurisica Efficient estimation of graphlet frequency distributions in protein-protein interaction networks Bioinformatics, April 15, 2006; 22(8): 974 - 980. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
H. Yu, A. Paccanaro, V. Trifonov, and M. Gerstein Predicting interactions in protein networks by completing defective cliques Bioinformatics, April 1, 2006; 22(7): 823 - 829. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J. B Pereira-Leal, E. D Levy, and S. A Teichmann The origins and evolution of functional modules: lessons from protein complexes Phil Trans R Soc B, March 29, 2006; 361(1467): 507 - 517. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
X. Wu, L. Zhu, J. Guo, D.-Y. Zhang, and K. Lin Prediction of yeast protein-protein interaction network: insights from the Gene Ontology and annotations. Nucleic Acids Res., January 1, 2006; 34(7): 2137 - 2150. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 R. Albert Scale-free networks in cell biology J. Cell Sci., November 1, 2005; 118(21): 4947 - 4957. [Abstract] [Full Text] [PDF]
|
|