Evaluation of clustering algorithms for protein-protein interaction networks

By Sylvain Brohée, Jacques van Helden. BMC Bioinformatics, 2006

940 citations recorded by the source corpus.

BackgroundProtein interactions are crucial components of all cellular processes. Recently, high-throughput methods have been developed to obtain a global description of the interactome (the whole network of protein interactions for a given organism). In 2002, the yeast interactome was estimated to contain up to 80,000 potential interactions. This estimate is based on the integration of data sets obtained by various methods (mass spectrometry, two-hybrid methods, genetic studies). High-throughput methods are known, however, to yield a non-negligible rate of false positives, and to miss a fraction of existing interactions.The interactome can be represented as a graph where nodes correspond with proteins and edges with pairwise interactions. In recent years clustering methods have been developed and applied in order to extract relevant modules from such graphs. These algorithms require the specification of parameters that may drastically affect the results. In this paper we present a comparative assessment of four algorithms: Markov Clustering (MCL), Restricted Neighborhood Search Clustering (RNSC), Super Paramagnetic Clustering (SPC), and Molecular Complex Detection (MCODE).ResultsA test graph was built on the basis of 220 complexes annotated in the MIPS database. To evaluate the robustness to false positives and false negatives, we derived 41 altered graphs by randomly removing edges from or adding edges to the test graph in various proportions.Each clustering algorithm was applied to these graphs with various parameter settings, and the clusters were compared with the annotated complexes.We analyzed the sensitivity of the algorithms to the parameters and determined their optimal parameter values.We also evaluated their robustness to alterations of the test graph.We then applied the four algorithms to six graphs obtained from high-throughput experiments and compared the resulting clusters with the annotated complexes.ConclusionThis analysis shows that MCL is remarkably robust to graph alterations. In the tests of robustness, RNSC is more sensitive to edge deletion but less sensitive to the use of suboptimal parameter values. The other two algorithms are clearly weaker under most conditions.The analysis of high-throughput data supports the superiority of MCL for the extraction of complexes from interaction networks.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/b75a0cccad7ff4a5a840c5a3683724ec938775dd

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

In Statistical and Nonlinear Physics

Citations in the corpus

Clustering algorithms: A comparative approach (2016, methodology): “A systematic quantitative evaluation of four graph-based clustering methods was performed in [27].”
Using graph theory to analyze biological networks (2011, background): “Very often we encounter articles that compare similar algorithms using different datasets and come to very diverse conclusions and results i.e [142,143].”
Graph Clustering Via a Discrete Uncoupling Process (2008, background): “Other proteinrelated MCL applications in bioinformatics are large scale sequence space analysis [19, 37], hybrid MCL/single-link clustering [29], orthologous groups [41], kinase proteins [24], secreted proteins [7], eye proteins [39], mobile genetic elements [40], protein interaction networks [5, 54”
Computational approaches for detecting protein complexes from protein interaction networks: a survey (2010, methodology): “F = 2 × Precision × Recall / (Precision + Recall ) (6) Sensitivity, positive predictive value and accuracy Recently, sensitivity (Sn ), positive predictive value (PPV) and accuracy (Acc ) have also been proposed to evaluate the accuracy of the prediction methods [32,36].”
PINA v2.0: mining interactome modules (2011, methodology): “We selected molecular complex detection (MCODE) method (6) and Markov clustering (MCL) method (5) as representatives from each category (19), and applied them to the interactomes from each of the six species.”
Using MCL to extract clusters from networks. (2012, methodology): “It has subsequently been used, among others, for detecting orthologous groups [6], predicting protein complexes from protein interaction networks [7,8], clustering of genes according to their expression profiles [9–11], and clustering of scientific documents [12].”
Network-based prediction of protein function (2007, positive): “Although the ﬁeld has advanced considerably in recent years on the methodological side, comprehensive comparisons of the plethora of available annotation methods, similar to that performed by Brohee and van Helden (2006), are greatly in need.”
A core-attachment based method to detect protein complexes in PPI networks (2009, background): “Coverage rate Coverage rate [27,53] is applied to show how many proteins in the real complexes can be covered by the predicted complexes.”
Network visualization and analysis of gene expression data using BioLayout Express3D (2009, methodology): “21| If the 2D button on the menu bar is clicked, then the graph will be converted to a 2D representation of the 3D graph.”
Detecting overlapping protein complexes in protein-protein interaction networks (2012, methodology): “2 Caveats of the clustering-wise separation To solve some of the problems of the clustering-wise sensitivity and positive predictive value measures, Brohée and van Helden [2] have also suggested the clustering-wise separation measure as an alternative metric.”
Protein networks in disease. (2008, methodology): “Beyond enriched motifs, methods have been devised to identify all sorts of network structures, such as densely connected network regions (for review, see Brohee and van Helden 2006 ), which are suggestive of protein complexes, and paths of interactions connecting membrane proteins to transcription ”