Efficient algorithms for accurate hierarchical clustering of huge datasets: tackling the entire protein space
Open accessThe DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.
Abstract
Motivation: UPGMA (average linking) is probably the most popular algorithm for hierarchical data clustering, especially in computational biology. However, UPGMA requires the entire dissimilarity matrix in memory. Due to this prohibitive requirement, UPGMA is not scalable to very large datasets. Application: We present a novel class of memory-constrained UPGMA (MC-UPGMA) algorithms. Given any practical memory size constraint, this framework guarantees the correct clustering solution without explicitly requiring all dissimilarities in memory. The algorithms are general and are applicable to any dataset. We present a data-dependent characterization of hardness and clustering efficiency. The presented concepts are applicable to any agglomerative clustering formulation. Results: We apply our algorithm to the entire collection of protein sequences, to automatically build a comprehensive evolutionary-driven hierarchy of proteins from sequence alone. The newly created tree captures protein families better than state-of-the-art large-scale methods such as CluSTr, ProtoNet4 or single-linkage clustering. We demonstrate that leveraging the entire mass embodied in all sequence similarities allows to significantly improve on current protein family clusterings which are unable to directly tackle the sheer mass of this data. Furthermore, we argue that non-metric constraints are an inherent complexity of the sequence space and should not be overlooked. The robustness of UPGMA allows significant improvement, especially for multidomain proteins, and for large or divergent families. Availability: A comprehensive tree built from all UniProt sequence similarities, together with navigation and classification tools will be made available as part of the ProtoNet service. A C++ implementation of the algorithm is available on request. Contact: lonshy@cs.huji.ac.il
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
UniRef: comprehensive and non-redundant UniProt reference clusters
Suzek, B. E., Huang, H., McGarvey, P., Mazumder, R., & Wu, C. H. (2007) · Bioinformatics · doi:10.1093/bioinformatics/btm098 · Cited by 1,613
Cited by
Ribosomal Database Project: data and tools for high throughput rRNA analysis
Cole, J. R., Wang, Q., Fish, J. A., Chai, B., McGarrell, D. M., Sun, Y., Brown, C. T., Porras-Alfaro, A., Kuske, C. R., & Tiedje, J. M. (2014) · Nucleic Acids Research · doi:10.1093/nar/gkt1244 · Cited by 4,367
A Deep Learning Approach to Antibiotic Discovery
Stokes, J. M., Yang, K., Swanson, K., Jin, W., Cubillos-Ruiz, A., Donghia, N. M., MacNair, C. R., French, S., Carfrae, L. A., Bloom-Ackermann, Z., et al. (2020) · Cell · doi:10.1016/j.cell.2020.01.021 · Cited by 2,463
UniRef clusters: a comprehensive and scalable alternative for improving sequence similarity searches
Suzek, B. E., Wang, Y., Huang, H., McGarvey, P. B., Wu, C. H., & the UniProt Consortium (2015) · Bioinformatics · doi:10.1093/bioinformatics/btu739 · Cited by 1,928
CAVER 3.0: A Tool for the Analysis of Transport Pathways in Dynamic Protein Structures
Chovancova, E., Pavelka, A., Benes, P., Strnad, O., Brezovsky, J., Kozlikova, B., Gora, A., Sustr, V., Klvana, M., Medek, P., et al. (2012) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1002708 · Cited by 1,411
New insights from uncultivated genomes of the global human gut microbiome
Nayfach, S., Shi, Z. J., Seshadri, R., Pollard, K. S., & Kyrpides, N. C. (2019) · Nature · doi:10.1038/s41586-019-1058-x · Cited by 737
Metadata
- Authors
- Loewenstein, Y., Portugaly, E., Fromer, M., & Linial, M.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2008-07-01
- Volume
- 24
- Issue
- 13
- Pages
- i41-i49
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2151370125
- Cited by
- 147
- References
- 1
- FWCI
- 3.10
- Type
- journal article
- Language
- en
- Open access
- hybrid
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: Efficient algorithms for accurate hierarchical clustering of huge datasets: tackling the entire protein space. https://app.cochat.ai/papers/10.1093/bioinformatics/btn174
- The paper
- Loewenstein, Y., Portugaly, E., Fromer, M., & Linial, M. (2008). Efficient algorithms for accurate hierarchical clustering of huge datasets: tackling the entire protein space. Bioinformatics. https://doi.org/10.1093/bioinformatics/btn174
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.