Protein complex prediction via cost-based clustering

By Andrew D. King, Natasa Przulj, Igor Jurisica. Bioinform., 2004

680 citations recorded by the source corpus.

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.

Subfields: Molecular Biology

View Paper: https://www.semanticscholar.org/paper/3346bf49318ffc5a9c39c95a435c2dd53292f2f2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

1. Roded Sharan
2. Igor Ulitsky
3. Ron Shamir
4. Min Wu
5. Xiaoli Li
6. Chee Keong Kwoh
7. See-Kiong Ng
8. Haiyuan Yu

Citations in the corpus

• Using graph theory to analyze biological networks (2011, background): “Restricted Neighborhood Search Cluster Algorithm [140]: It tries to find low cost clustering by composing first an initial random clustering.”
• Network-based prediction of protein function (2007, methodology): “The restricted neighborhood search clustering (RNSC) algorithm proposed by King et al (2004) partitions the node set of the network into clusters based on a cost function that is used to evaluate the partitioning.”
• Computational approaches for detecting protein complexes from protein interaction networks: a survey (2010, methodology): “Relatively few complexes are predicted by RNSC and its results depended heavily on the quality of the initial clustering which is random or user-defined.”
• Evaluation of clustering algorithms for protein-protein interaction networks (2006, methodology): “Developper King AD Van Dongen S Bader GD and Hogue CWV Blatt M, Wiseman S, Domany E References [21] [35] [19] [18]”
• Global Functional Atlas of Escherichia coli Encompassing Previously Uncharacterized Proteins (2009, methodology): “], alternative clustering algorithms comparable to MCL in terms of accuracy, such as the Restricted Neighborhood Search Cluster algorithm [”
• Detecting overlapping protein complexes in protein-protein interaction networks (2012, methodology): “According to the suggestions of the authors of the algorithm [17], a size limit of 4 was used.”
• Review of Drug Repositioning Approaches and Resources (2018, background): “As disease pathways can be constructed from protein-protein interaction (PPI) network analysis [59], a protein-protein interaction (PPI) network, as a homogeneous network, is often employed in some approaches [22, 60, 61] used to identify drug targets involved with multiple pathways.”
• Scale-free networks in cell biology (2005, background): “Interaction motifs and themes can be exploited to predict individual interactions given sometimes-uncertain experimental evidence or to give a short list of candidates for experimental testing (Albert and Albert, 2004; King et al., 2004; Wong et al., 2004).”