The DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
Clustering huge protein sequence sets in linear time
Open accessPublished version of a preprint
Abstract
Metagenomic datasets contain billions of protein sequences that could greatly enhance large-scale functional annotation and structure prediction. Utilizing this enormous resource would require reducing its redundancy by similarity clustering. However, clustering hundreds of millions of sequences is impractical using current algorithms because their runtimes scale as the input set size N times the number of clusters K, which is typically of similar order as N, resulting in runtimes that increase almost quadratically with N. We developed Linclust, the first clustering algorithm whose runtime scales as N, independent of K. It can also cluster datasets several times larger than the available main memory. We cluster 1.6 billion metagenomic sequence fragments in 10 h on a single server to 50% sequence identity, >1000 times faster than has been possible before. Linclust will help to unlock the great wealth contained in metagenomic and genomic sequence databases.
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
Figures





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
Basic local alignment search tool
Altschul, S. F., Gish, W., Miller, W., Myers, E. W., & Lipman, D. J. (1990) · Journal of Molecular Biology · doi:10.1006/jmbi.1990.9999 · Cited by 98,669 · cited 1×
“For each clustering run, we searched with BLAST [15] a random sample of 1 000 representative sequences against all representative sequences of the clustering.”
MethodSearch and clustering orders of magnitude faster than BLAST
Edgar, R. C. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq461 · Cited by 20,826
Fast and sensitive protein alignment using DIAMOND
Buchfink, B., Xie, C., & Huson, D. H. (2015) · Nature Methods · doi:10.1038/nmeth.3176 · Cited by 14,201 · cited 3×
“At 50% identity, Linclust clusters the 123 million sequences 10 times faster than Linclust/MMseqs2 and, by extrapolation, 2300 times faster than UCLUST, 720 times faster than MMseqs, 4600 times faster than CD-HIT, 1600 times faster than DIAMOND [12], 69 000 times faster than MASH [13], and 26 000 times faster than RAP…”
BackgroundInfluentialProdigal: prokaryotic gene recognition and translation initiation site identification
Hyatt, D., Chen, G.-L., LoCascio, P. F., Land, M. L., Larimer, F. W., & Hauser, L. J. (2010) · BMC Bioinformatics · doi:10.1186/1471-2105-11-119 · Cited by 12,587
Cd-hit: a fast program for clustering and comparing large sets of protein or nucleotide sequences
Li, W., & Godzik, A. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btl158 · Cited by 11,410 · cited 1×
“Similar to the k-mer prefilter used in CD-HIT, UCLUST, kclust and MMseqs [8, 11, 26, 27], the preclustering reduces the number of comparisons by a large factor F using the slow, exact measure, but the time complexity of the ex240 act distance calculation O(N(2)/F ) is still quadratic in N .”
MethodCd-hit: Accelerated for clustering the next-generation sequencing data
Fu, L., Niu, B., Zhu, Z., Wu, S., & Li, W. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts565 · Cited by 11,175 · cited 15×
“By increasing m from 20 to 80, Linclust takes only 1.5 to 2 times longer but attains a sensitivity similar to UCLUST (pink in Fig.”
MethodInfluentialThe Pfam protein families database: towards a more sustainable future
Finn, R. D., Coggill, P., Eberhardt, R. Y., Eddy, S. R., Mistry, J., Mitchell, A. L., Potter, S. C., Punta, M., Qureshi, M., Sangrador-Vegas, A., et al. (2016) · Nucleic Acids Research · doi:10.1093/nar/gkv1344 · Cited by 5,975 · cited 1×
“4a,b) and Pfam domain annotations [18] (Fig.”
MMseqs2 enables sensitive protein sequence searching for the analysis of massive data sets
Steinegger, M., & Söding, J. (2017) · Nature Biotechnology · doi:10.1038/nbt.3988 · Cited by 4,840
Self-citationThe Universal Protein Resource (UniProt)
Bairoch, A. (2004) · Nucleic Acids Research · doi:10.1093/nar/gki070 · Cited by 3,774 · cited 1×
“, 100}, we determined these thresholds empirically on 4 million local alignments sampled from an all-against-all comparison of the UniProt database [31].”
MethodGene Ontology Consortium: going forward
The Gene Ontology Consortium (2015) · Nucleic Acids Research · doi:10.1093/nar/gku1179 · Cited by 3,492 · cited 2×
“We assess Gene Ontology (GO) annotations [17] (Fig.”
BackgroundMethod
Research works printed but not linked: 2
Cited by
Highly accurate protein structure prediction with AlphaFold
Jumper, J., Evans, R., Pritzel, A., Green, T., Figurnov, M., Ronneberger, O., Tunyasuvunakool, K., Bates, R., Žídek, A., Potapenko, A., et al. (2021) · Nature · doi:10.1038/s41586-021-03819-2 · Cited by 43,764
Self-citationColabFold - Making protein folding accessible to all
Mirdita, M., Schütze, K., Moriwaki, Y., Heo, L., Ovchinnikov, S., & Steinegger, M. (2021) · doi:10.1101/2021.08.15.456425 · Cited by 9,391
“To update the database we searched the proteins from the SMAG (eukaryotes) 14 , MetaEuk (eukaryotes) 13 , TOPAZ (eukaryotes) 15 , MGV (DNA viruses) 16 , GPD (bacteriophages) 17 and an updated version of MetaClust 18 against the BFD/MGnify centroids using MMseqs2 and assigned each sequence to the respective cluster if…”
MethodInfluentialSelf-citationUniProt: the universal protein knowledgebase in 2021
The UniProt Consortium, Bateman, A., Martin, M.-J., Orchard, S., Magrane, M., Agivetova, R., Ahmad, S., Alpi, E., Bowler-Barnett, E. H., Britto, R., et al. (2021) · Nucleic Acids Research · doi:10.1093/nar/gkaa1100 · Cited by 6,372
“We have adopted the MMseqs2 algorithm to improve the speed of UniRef production (11), decreasing the time taken to perform UniRef50 clustering from four weeks to 60 hours, and improved procedures to compute proteome clusters and identify representative proteomes, pan proteomes, and core and…”
MethodMMseqs2 enables sensitive protein sequence searching for the analysis of massive data sets
Steinegger, M., & Söding, J. (2017) · Nature Biotechnology · doi:10.1038/nbt.3988 · Cited by 4,840
Self-citationProtein complex prediction with AlphaFold-Multimer
Evans, R., O’Neill, M., Pritzel, A., Antropova, N., Senior, A., Green, T., Žídek, A., Bates, R., Blackwell, S., Yim, J., et al. (2021) · doi:10.1101/2021.10.04.463034 · Cited by 3,808
“Moreover, we add extra positional encodings denoting whether a given pair of amino acids corresponds to different chains and whether they belong to different homomer or heteromer chains.”
Background
Metadata
- Authors
- Steinegger, M., & Söding, J.
- Affiliations
- Seoul National University (KR)
- Max Planck Institute for Biophysical Chemistry (DE)
- Corresponding author
- Steinegger, Martin
- Söding, Johannes
- Venue
- Nature Communications
- Published
- 2018-06-29
- Volume
- 9
- Issue
- 1
- Pages
- 2542-2542
- ISSN
- 2041-1723 (ISSN-L)
- PMC
- PMC6026198
- OpenAlex
- W2953008890
- Cited by
- 875
- References
- 32
- Citations by year
- 2026: 110 · 2025: 154 · 2024: 168 · 2023: 123 · 2022: 111 · 2021: 129 · 2020: 52 · 2019: 28
- FWCI
- 18.49
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Licence
- cc-by
- creativecommons.org/licenses/by/4.0 (tdm)
- creativecommons.org/licenses/by/4.0 (vor)
- Locations
- Nature Communications (publishedVersion, cc-by)
- Europe PMC (PubMed Central) (publishedVersion, cc-by)
- PubMed Central (publishedVersion, cc-by)
- PubMed (publishedVersion)
- OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion)
- mediaTUM (Technical University of Munich) (submittedVersion, other-oa)
- GoeScholar The Publication Server of the Georg-August-Universität Göttingen (Georg-August-Universität Göttingen) (submittedVersion, cc-by)
- Seoul National University Open Repository (Seoul National University) (submittedVersion)
- Funders
- U.S. Department of Energy
- Joint Genome Institute
- Seoul National University
- Horizon 2020 Framework Programme (685778)
- Topics
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Fractal and DNA sequence analysis
- Keywords
- protein sequence clustering, metagenomics, functional annotation, memory-efficient clustering, sequence similarity
- MeSH terms
- Algorithms, Animals, DNA, Humans, Prokaryotic Cells, Proteins, Cluster Analysis, Genome, Sequence Analysis, DNA, Computational Biology, Databases, Nucleic Acid, Databases, Protein, Metagenomics, Datasets as Topic
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: Clustering huge protein sequence sets in linear time. https://app.cochat.ai/papers/10.1038/s41467-018-04964-5
- The paper
- Steinegger, M., & Söding, J. (2018). Clustering huge protein sequence sets in linear time. Nature Communications. https://doi.org/10.1038/s41467-018-04964-5
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.