Protein complex prediction via cost-based clustering.
BACKGROUND
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.
King
A D
AD
Department of Computer Science, University of Toronto, Toronto, M5S 3G4, Canada.
Przulj
N
N
Jurisica
I
I
D000465:Algorithms; D000818:Animals; D029742:Caenorhabditis elegans Proteins / Q000378:metabolism; D016000:Cluster Analysis; D003198:Computer Simulation; D029721:Drosophila Proteins / Q000378:metabolism; D008954:Models, Biological; D009097:Multienzyme Complexes / Q000378:metabolism; D025941:Protein Interaction Mapping / Q000379:methods*; D011506:Proteins / Q000378:metabolism*; D029701:Saccharomyces cerevisiae Proteins / Q000378:metabolism; D015398:Signal Transduction / Q000502:physiology*
D029742:Caenorhabditis elegans Proteins; D029721:Drosophila Proteins; D009097:Multienzyme Complexes; D011506:Proteins; D029701:Saccharomyces cerevisiae Proteins