Protein complex prediction via cost-based clustering. (Supplementary information) Bioinformatics http://www.cs.utoronto.ca/∼juris/data/pp104/ King,A.D. (2004) Graph clustering with restricted neighbourhood search

Motivation: Understanding principles of cellular organiza-tion 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 experi-ments. The increasing amount of available PPI data neces-sitates 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 com-plexes. We have determined functional and graph-theoretic properties of true protein complexes from the MIPS data-base. Based on these properties, we defined filters to dis-tinguish between identified network clusters and true protein complexes. Conclusions: Our application of the cost-based clustering algorithm provides an accurate and scalable method of detect-ing and predicting protein complexes within a PPI network. Availability: The RNSC algorithm and data processing code are available upon request from the authors. Contact