The DOI matches its Crossref record; 5 of the 5 references it cites were found in a registry or an index.
Markov clustering versus affinity propagation for the partitioning of protein interaction graphs
Open accessAbstract
BACKGROUND: Genome scale data on protein interactions are generally represented as large networks, or graphs, where hundreds or thousands of proteins are linked to one another. Since proteins tend to function in groups, or complexes, an important goal has been to reliably identify protein complexes from these graphs. This task is commonly executed using clustering procedures, which aim at detecting densely connected regions within the interaction graphs. There exists a wealth of clustering algorithms, some of which have been applied to this problem. One of the most successful clustering procedures in this context has been the Markov Cluster algorithm (MCL), which was recently shown to outperform a number of other procedures, some of which were specifically designed for partitioning protein interactions graphs. A novel promising clustering procedure termed Affinity Propagation (AP) was recently shown to be particularly effective, and much faster than other methods for a variety of problems, but has not yet been applied to partition protein interaction graphs. RESULTS: In this work we compare the performance of the Affinity Propagation (AP) and Markov Clustering (MCL) procedures. To this end we derive an unweighted network of protein-protein interactions from a set of 408 protein complexes from S. cervisiae hand curated in-house, and evaluate the performance of the two clustering algorithms in recalling the annotated complexes. In doing so the parameter space of each algorithm is sampled in order to select optimal values for these parameters, and the robustness of the algorithms is assessed by quantifying the level of complex recall as interactions are randomly added or removed to the network to simulate noise. To evaluate the performance on a weighted protein interaction graph, we also apply the two algorithms to the consolidated protein interaction network of S. cerevisiae, derived from genome scale purification experiments and to versions of this network in which varying proportions of the links have been randomly shuffled. CONCLUSION: Our analysis shows that the MCL procedure is significantly more tolerant to noise and behaves more robustly than the AP algorithm. The advantage of MCL over AP is dramatic for unweighted protein interaction graphs, as AP displays severe convergence problems on the majority of the unweighted graph versions that we tested, whereas MCL continues to identify meaningful clusters, albeit fewer of them, as the level of noise in the graph increases. MCL thus remains the method of choice for identifying protein complexes from binary interaction networks.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Cytoscape: A software Environment for integrated models of biomolecular interaction networks
Shannon, P., Markiel, A., Ozier, O., Baliga, N. S., Wang, J. T., Ramage, D., Amin, N., Schwikowski, B., & Ideker, T. (2003) · Genome Research · doi:10.1101/gr.1239303 · Cited by 51,888
The Elements of Statistical Learning
Hastie, T., Tibshirani, R., & Friedman, J. (2009) · Springer Series in Statistics · doi:10.1007/978-0-387-84858-7 · Cited by 25,970
BioGRID: a general repository for interaction datasets
Stark, C. (2006) · Nucleic Acids Research · doi:10.1093/nar/gkj109 · Cited by 3,960
High-Quality Binary Protein Interaction Map of the Yeast Interactome Network
Yu, H., Braun, P., Yıldırım, M. A., Lemmens, I., Venkatesan, K., Sahalie, J., Hirozane-Kishikawa, T., Gebreab, F., Li, N., Simonis, N., et al. (2008) · Science · doi:10.1126/science.1158684 · Cited by 1,392
Toward a Comprehensive Atlas of the Physical Interactome of Saccharomyces cerevisiae
Collins, S. R., Kemmeren, P., Zhao, X.-C., Greenblatt, J. F., Spencer, F., Holstege, F. C. P., Weissman, J. S., & Krogan, N. J. (2007) · Molecular & Cellular Proteomics · doi:10.1074/mcp.m600381-mcp200 · Cited by 795
Cited by
Using graph theory to analyze biological networks
Pavlopoulos, G. A., Secrier, M., Moschopoulos, C. N., Soldatos, T. G., Kossida, S., Aerts, J., Schneider, R., & Bagos, P. G. (2011) · BioData Mining · doi:10.1186/1756-0381-4-10 · Cited by 791
clusterMaker: a multi-algorithm clustering plugin for Cytoscape
Morris, J. H., Apeltsin, L., Newman, A. M., Baumbach, J., Wittkop, T., Su, G., Bader, G. D., & Ferrin, T. E. (2011) · BMC Bioinformatics · doi:10.1186/1471-2105-12-436 · Cited by 621
APCluster: an R package for affinity propagation clustering
Bodenhofer, U., Kothmeier, A., & Hochreiter, S. (2011) · Bioinformatics · doi:10.1093/bioinformatics/btr406 · Cited by 479
Dynamic Protein-Protein Interaction Wiring of the Human Spliceosome
Hegele, A., Kamburov, A., Grossmann, A., Sourlis, C., Wowro, S., Weimann, M., Will, C. L., Pena, V., Lührmann, R., & Stelzl, U. (2012) · Molecular Cell · doi:10.1016/j.molcel.2011.12.034 · Cited by 414
Identification of a Functional Connectome for Long-Term Fear Memory in Mice
Wheeler, A. L., Teixeira, C. M., Wang, A. H., Xiong, X., Kovacevic, N., Lerch, J. P., McIntosh, A. R., Parkinson, J., & Frankland, P. W. (2013) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1002853 · Cited by 315
Metadata
- Authors
- Vlasblom, J., & Wodak, S. J.
- Venue
- BMC Bioinformatics
- Published
- 2009-03-30
- Volume
- 10
- Issue
- 1
- Pages
- 99-99
- ISSN
- 1471-2105 (ISSN-L)
- OpenAlex
- W2030006812
- Cited by
- 222
- References
- 5
- FWCI
- 6.72
- Type
- journal article
- Language
- en
- Open access
- gold
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Markov clustering versus affinity propagation for the partitioning of protein interaction graphs. https://app.cochat.ai/papers/10.1186/1471-2105-10-99
- The paper
- Vlasblom, J., & Wodak, S. J. (2009). Markov clustering versus affinity propagation for the partitioning of protein interaction graphs. BMC Bioinformatics. https://doi.org/10.1186/1471-2105-10-99
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.