On the robustness of graph-based clustering to random network alterations
Open accessPublished version of a preprint
Abstract
Biological functions emerge from complex and dynamic networks of protein-protein interactions. Because these protein-protein interaction networks, or interactomes, represent pairwise connections within a hierarchically organized system, it is often useful to identify higher-order associations embedded within them, such as multimember protein complexes. Graph-based clustering techniques are widely used to accomplish this goal, and dozens of field-specific and general clustering algorithms exist. However, interactomes can be prone to errors, especially when inferred from high-throughput biochemical assays. Therefore, robustness to network-level noise is an important criterion. Here, we tested the robustness of a range of graph-based clustering algorithms in the presence of noise, including algorithms common across domains and those specific to protein networks. Strikingly, we found that all of the clustering algorithms tested here markedly amplified network-level noise. Randomly rewiring only 1% of network edges yielded more than a 50% change in clustering results. Moreover, we found the impact of network noise on individual clusters was not uniform: some clusters were consistently robust to injected noise, whereas others were not. Therefore we developed the clust.perturb R package and Shiny web application to measure the reproducibility of clusters by randomly perturbing the network. We show that clust.perturb results are predictive of real-world cluster stability: poorly reproducible clusters as identified by clust.perturb are significantly less likely to be reclustered across experiments. We conclude that graph-based clustering amplifies noise in protein interaction networks, but quantifying the robustness of a cluster to network noise can separate stable protein complexes from spurious associations.
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
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.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Clustering analysis of networks is sensitive to network noise, and biochemical experimental challenges as well as cell-to-cell variation can contribute to this issue.
“Clustering analysis of networks is sensitive to network noise (Stacey et al., 2020), and biochemical experimental challenges as well as cell-to-cell variation can contribute to this issue.”
From Mapping the multiscale structure of biological systems (2021) · cites this paper as Stacey et al., 2020
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Fast unfolding of communities in large networks
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. (2008) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2008/10/p10008 · Cited by 21,424 · see citing works
Advances in Neural Information Processing Systems 25
Zhang, Y., Sutton, C. A., Storkey, A., & Zoubin Ghahramani, A. (2012) · Cited by 12,653 · see citing works
Data clustering: 50 years beyond K-means
Jain, A. K. (2009) · Pattern Recognition Letters · doi:10.1016/j.patrec.2009.09.011 · Cited by 9,622 · see citing works
DrugBank 5.0: a major update to the DrugBank database for 2018
Wishart, D. S., Feunang, Y. D., Guo, A. C., Lo, E. J., Marcu, A., Grant, J. R., Sajed, T., Johnson, D., Li, C., Sayeeda, Z., et al. (2018) · Nucleic Acids Research · doi:10.1093/nar/gkx1037 · Cited by 8,404 · see citing works
Hubert, L., & Arabie, P. (1985) · Journal of Classification · doi:10.1007/bf01908075 · Cited by 8,219 · see citing works
An automated method for finding molecular complexes in large protein interaction networks
Bader, G. D., & Hogue, C. W. V. (2003) · BMC Bioinformatics · doi:10.1186/1471-2105-4-2 · Cited by 6,112 · see citing works
From Louvain to Leiden: guaranteeing well-connected communities
Traag, V. A., Waltman, L., & van Eck, N. J. (2019) · Scientific Reports · doi:10.1038/s41598-019-41695-z · Cited by 5,635 · see citing works
Leskovec, J., Kleinberg, J. M., & Faloutsos, C. (2007) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1217299.1217301 · Cited by 2,494 · see citing works
Computing Communities in Large Networks Using Random Walks
Pons, P., & Matthieu Latapy, B. (2005) · Lecture notes in computer science · doi:10.1007/11569596_31 · Cited by 2,147 · see citing works
A Comprehensive Survey of Clustering Algorithms
Xu, D., & Tian, Y. (2015) · Annals of Data Science · doi:10.1007/s40745-015-0040-1 · Cited by 1,939 · see citing works
Learning to Discover Social Circles in Ego Networks
Leskovec, J., & McAuley, J. (2012) · neural information processing systems · Cited by 1,701 · see citing works
Graph Clustering by Flow Simulation
van Dongen, S. M. (2000) · Cited by 1,604 · see citing works
The BioGRID interaction database: 2019 update
Oughtred, R., Stark, C., Breitkreutz, B., Rust, J., Boucher, L., Chang, C., Kolas, N. K., O’Donnell, L., Leung, G. C., McAdam, R. F., et al. (2018) · Nucleic Acids Research · doi:10.1093/nar/gky1079 · Cited by 1,440 · see citing works
CORUM: the comprehensive resource of mammalian protein complexes—2009
Ruepp, A., Wägele, B., Lechner, M., Brauner, B., Dunger-Kaltenbach, I., Fobo, G., Frishman, G., Montrone, C., & Mewes, H. (2009) · Nucleic Acids Research · doi:10.1093/nar/gkp914 · Cited by 1,320 · see citing works
Detecting overlapping protein complexes in protein-protein interaction networks
Nepusz, T., Yu, H., & Paccanaro, A. (2012) · Nature Methods · doi:10.1038/nmeth.1938 · Cited by 1,233 · see citing works
A reference map of the human binary protein interactome
Luck, K., Kim, D.-K., Lambourne, L., Spirohn, K., Begg, B. E., Bian, W., Brignall, R., Cafarelli, T., Campos-Laborie, F. J., Charloteaux, B., et al. (2020) · Nature · doi:10.1038/s41586-020-2188-x · Cited by 1,197 · see citing works
Dual proteome-scale networks reveal cell-specific remodeling of the human interactome
Huttlin, E. L., Bruckner, R. J., Navarrete-Perea, J., Cannon, J. R., Baltier, K., Gebreab, F., Gygi, M. P., Thornock, A., Zarraga, G., Tam, S., et al. (2020) · doi:10.1101/2020.01.19.905109 · Cited by 960 · see citing works
Encyclopedia of Machine Learning and Data Mining
Webb, G. I., & Sammut, C. (2017) · Springer eBooks · doi:10.1007/978-1-4899-7687-1 · Cited by 926 · see citing works
Evaluation of clustering algorithms for protein-protein interaction networks
Brohée, S., & van Helden, J. (2006) · BMC Bioinformatics · doi:10.1186/1471-2105-7-488 · Cited by 891 · see citing works
A Census of Human Soluble Protein Complexes
Havugimana, P. C., Hart, T., Nepusz, T., Yang, H., Turinsky, A. L., Li, Z., Wang, P. I., Boutz, D. R., Fong, V., Phanse, S., et al. (2012) · Cell · doi:10.1016/j.cell.2012.08.011 · Cited by 843 · see citing works
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 · see citing works
Local Higher-Order Graph Clustering
Yin, H., Benson, A. R., Leskovec, J., & Gleich, D. F. (2017) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3097983.3098069 · Cited by 620 · see citing works
CORUM: the comprehensive resource of mammalian protein complexes—2019
Giurgiu, M., Reinhard, J., Brauner, B., Dunger-Kaltenbach, I., Fobo, G., Frishman, G., Montrone, C., & Ruepp, A. (2019) · Nucleic Acids Research · doi:10.1093/nar/gky973 · Cited by 595 · see citing works
Panorama of ancient metazoan macromolecular complexes
Wan, C., Borgeson, B., Phanse, S., Tu, F., Drew, K., Clark, G. W., Xiong, X., Kagan, O., Kwan, J., Bezginov, A., et al. (2015) · Nature · doi:10.1038/nature14877 · Cited by 521 · see citing works
A high-throughput approach for measuring temporal changes in the interactome
Kristensen, A. R., Gsponer, J., & Foster, L. J. (2012) · Nature Methods · doi:10.1038/nmeth.2131 · Cited by 332 · see citing works
Self-citationNormalized Mutual Information to evaluate overlapping community finding algorithmsPreprint
McDaid, A. F., Greene, D., & Hurley, N. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1110.2515 · Cited by 233 · see citing works
Markov clustering versus affinity propagation for the partitioning of protein interaction graphs
Vlasblom, J., & Wodak, S. J. (2009) · BMC Bioinformatics · doi:10.1186/1471-2105-10-99 · Cited by 223 · see citing works
Comparison of clustering tools in R for medium-sized 10x Genomics single-cell RNA-sequencing data
Freytag, S., Tian, L., Lönnstedt, I., Ng, M., & Bahlo, M. (2018) · F1000Research · doi:10.12688/f1000research.15809.1 · Cited by 220 · see citing works
Drew, K., Lee, C., Huizar, R. L., Tu, F., Borgeson, B., McWhite, C. D., Ma, Y., Wallingford, J. B., & Marcotte, E. M. (2017) · Molecular Systems Biology · doi:10.15252/msb.20167490 · Cited by 191 · see citing works
Comparison of clustering tools in R for medium-sized 10x Genomics single-cell RNA-sequencing data
Freytag, S., Tian, L., Lönnstedt, I. M., et al. (2018) · F1000Research · doi:10.12688/f1000research.15809.2 · Cited by 159 · see citing works
Jin, X. Y., & Han, J. (2010) · Encyclopedia of Machine Learning · doi:10.1007/978-0-387-30164-8_426 · Cited by 154 · see citing works
EPIC: software toolkit for elution profile-based inference of protein complexes
Hu, L. Z., Goebels, F., Tan, J. H., Wolf, E. J., Kuzmanov, U., Wan, C., Phanse, S., Xu, C., Schertzberg, M., Fraser, A. G., et al. (2019) · Nature Methods · doi:10.1038/s41592-019-0461-4 · Cited by 94 · see citing works
A rapid and accurate approach for prediction of interactomes from co-elution data (PrInCE)
Stacey, R. G., Skinnider, M. A., Scott, N. E., & Foster, L. J. (2017) · BMC Bioinformatics · doi:10.1186/s12859-017-1865-8 · Cited by 65 · see citing works
Self-citationAl‐Razgan, M., & Domeniconi, C. (2006) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972764.23 · Cited by 64 · see citing works
Gates, A. J., & Ahn, Y. (2019) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.2598681 · Cited by 63 · see citing works
Interactome disassembly during apoptosis occurs independent of caspase cleavage
Scott, N. E., Rogers, L. D., Prudova, A., Brown, N. F., Fortelny, N., Overall, C. M., & Foster, L. J. (2017) · Molecular Systems Biology · doi:10.15252/msb.20167067 · Cited by 55 · see citing works
Self-citationDynamic rewiring of the human interactome by interferon signaling
Kerr, C. H., Skinnider, M. A., Madero, A. M., Andrews, D. D. T., Stacey, R. G., Chan, Q. W. T., Stoynov, N., Jan, E., & Foster, L. J. (2020) · Genome biology · doi:10.1186/s13059-020-02050-y · Cited by 37 · see citing works
Self-citationGenomic data integration systematically biases interactome mapping
Skinnider, M. A., Stacey, R. G., & Foster, L. J. (2018) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1006474 · Cited by 35 · see citing works
Self-citationContext-specific interactions in literature-curated protein interaction databases
Stacey, R. G., Skinnider, M. A., Chik, J. H. L., & Foster, L. J. (2018) · BMC Genomics · doi:10.1186/s12864-018-5139-2 · Cited by 33 · see citing works
Self-citationAccounting for noise when clustering biological data
Sloutsky, R., Jiménez, N., Swamidass, S. J., & Naegle, K. M. (2012) · Briefings in Bioinformatics · doi:10.1093/bib/bbs057 · Cited by 31 · see citing works
Scott, N. E., Brown, L., Kristensen, A. R., & Foster, L. J. (2014) · Journal of Proteomics · doi:10.1016/j.jprot.2014.10.024 · Cited by 25 · see citing works
Self-citationOn comparing clusterings: an element-centric framework unifies overlaps and hierarchyPreprint
Gates, A. J., Wood, I. B., Hetrick, W. P., et al. (2017) · arXiv (Cornell University) · Cited by 7 · see citing works
Dynamic rewiring of the human interactome by interferon signallingPreprint
Kerr, C. H., Skinnider, M. A., Madero, A. M., Andrews, D. D. T., Stacey, R. G., Chan, Q. W. T., Stoynov, N., Jan, E., & Foster, L. J. (2019) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/766808 · Cited by 4 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
Mapping the multiscale structure of biological systems
Schaffer, L. V., & Ideker, T. (2021) · Cell Systems · doi:10.1016/j.cels.2021.05.012 · Cited by 75 · see citing works
- Authors
- Stacey, R. G., Skinnider, M. A., & Foster, L. J.
- Affiliations
- University of British Columbia (CA)
- Corresponding author
- Stacey, R. Greg
- Venue
- Molecular & Cellular Proteomics
- Publisher
- Elsevier BV
- Published
- 2021
- Volume
- 20
- Pages
- 100002
- ISSN
- 1535-9476 (ISSN-L)
- PMC
- PMC7896145
- OpenAlex
- W3095905314
- Cited by
- 11
- References
- 45
- Citations by year
- 2026: 1 · 2024: 2 · 2023: 3 · 2022: 1 · 2021: 4
- FWCI
- 0.65
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- Locations
- Molecular & Cellular Proteomics (publishedVersion, cc-by)
- bioRxiv (Cold Spring Harbor Laboratory) (acceptedVersion, cc-by-nc)
- PubMed Central (publishedVersion, cc-by)
- PubMed (publishedVersion)
- Funders
- Genome Canada
- Canadian Institutes of Health Research
- Topics
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Bioinformatics and Genomic Networks
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Gene Regulatory Network Analysis
- Keywords
- graph clustering, protein-protein interaction network, network noise, cluster robustness, protein complexes, network perturbation, spurious association, clustering algorithm comparison
- MeSH terms
- Algorithms, Humans, Software, Reproducibility of Results, Cluster Analysis, Protein Interaction Maps
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
