CoChat

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 access
Steinegger, Martin, Söding, Johannes · 2018 · Nature Communications

Published 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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1038/s41467-018-04964-5

Cites

32 of 32 references verified0 citation errors · 0 not checkable

Statistics

Figures

Fig. 1 Overview of linear-time clustering algorithm. (1) For each sequence Linclust selects m k-mers (with the lowest hash function values). It sorts the k-mers alphabetically in quasi-linear time to find the groups of sequences sharing a k-mer (colored sets) and (2) it selects the longest sequence per k-mer group as center. (3,4) It compares each sequence (in three consecutively slower and more sensitive steps) only with the center sequences it shares a k-mer with, not with all sequences it shares a k-mer with. It therefore needs to compute at most m comparisons per sequence and mN in total. Pairs that pass the clustering criteria are linked by an edge. (5) The sequences are clustered in time O(mN) using a greedy incremental algorithm that finds clusters whose members all have an edge with a representative sequence. For a more details see Fig. 5
Fig. 1 Overview of linear-time clustering algorithm. (1) For each sequence Linclust selects m k-mers (with the lowest hash function values). It sorts the k-mers alphabetically in quasi-linear time to find the groups of sequences sharing a k-mer (colored sets) and (2) it selects the longest sequence per k-mer group as center. (3,4) It compares each sequence (in three consecutively slower and more sensitive steps) only with the center sequences it shares a k-mer with, not with all sequences it shares a k-mer with. It therefore needs to compute at most m comparisons per sequence and mN in total. Pairs that pass the clustering criteria are linked by an edge. (5) The sequences are clustered in time O(mN) using a greedy incremental algorithm that finds clusters whose members all have an edge with a representative sequence. For a more details see Fig. 5CC BY · PubMed Central
Fig. 2 Linclust and Linclust/MMseqs2 manifest unique linear scaling of runtime with sequence set size. a Runtime versus input set size on linear scales. The plotting symbols indicate the sequence identity threshold for clustering of 90%, 70%, and 50%. The curves are fits with a power law, bNa. For comparison, we include runtimes of all-against-all searches using sequence search tools DIAMOND, RAPsearch2, and MASH. Runtimes were measured on a server with two Intel Xeon E5-2640v3 8-core CPUs and 128 GB RAM. b Same as (a) but on log-log scales. c Average number of sequences per cluster at 90%, 70%, and 50% sequence identity. Larger average cluster sizes imply higher sensitivities to detect similar sequences
Fig. 2 Linclust and Linclust/MMseqs2 manifest unique linear scaling of runtime with sequence set size. a Runtime versus input set size on linear scales. The plotting symbols indicate the sequence identity threshold for clustering of 90%, 70%, and 50%. The curves are fits with a power law, bNa. For comparison, we include runtimes of all-against-all searches using sequence search tools DIAMOND, RAPsearch2, and MASH. Runtimes were measured on a server with two Intel Xeon E5-2640v3 8-core CPUs and 128 GB RAM. b Same as (a) but on log-log scales. c Average number of sequences per cluster at 90%, 70%, and 50% sequence identity. Larger average cluster sizes imply higher sensitivities to detect similar sequencesCC BY · PubMed Central
Fig. 3 Cumulative distance distribution between representative sequences. We clustered the test set of 123 million sequences at three different sequence identity thresholds (a–c at 50%, 70%, and 90%, respectively). For each clustering, we randomly sampled 1000 representative cluster sequences, compared them to all representative sequences of the clustering, and plotted the fraction whose best match (excluding self-matches) with minimum sequence coverage of 90% had a sequence identity above the x-value. The y-value at the clustering threshold (dashed line) is the fraction of false negatives, pairs of sequences whose similarity was overlooked by the clustering method
Fig. 3 Cumulative distance distribution between representative sequences. We clustered the test set of 123 million sequences at three different sequence identity thresholds (a–c at 50%, 70%, and 90%, respectively). For each clustering, we randomly sampled 1000 representative cluster sequences, compared them to all representative sequences of the clustering, and plotted the fraction whose best match (excluding self-matches) with minimum sequence coverage of 90% had a sequence identity above the x-value. The y-value at the clustering threshold (dashed line) is the fraction of false negatives, pairs of sequences whose similarity was overlooked by the clustering methodCC BY · PubMed Central
Fig. 4 Cluster consistency of GO molecular functional and Pfam annotations. a Cluster annotation consistency of GO functional annotations inferred from experiments (EXP_F). “Mean” and “worst” refers to the mean and the minimum annotation similarity between each representative sequence and all other cluster members. Plotting symbols indicate the sequence identity threshold for clustering. CD-HIT was only run at 90% sequence identity due to run time constraints. Linclust-m80 was only run at 50% sequence identity. b Same as (a) but using manually and computationally assigned functional GO annotations. c Consistency of Pfam annotation from the representative sequences to the cluster members
Fig. 4 Cluster consistency of GO molecular functional and Pfam annotations. a Cluster annotation consistency of GO functional annotations inferred from experiments (EXP_F). “Mean” and “worst” refers to the mean and the minimum annotation similarity between each representative sequence and all other cluster members. Plotting symbols indicate the sequence identity threshold for clustering. CD-HIT was only run at 90% sequence identity due to run time constraints. Linclust-m80 was only run at 50% sequence identity. b Same as (a) but using manually and computationally assigned functional GO annotations. c Consistency of Pfam annotation from the representative sequences to the cluster membersCC BY · PubMed Central
Fig. 5 Linear-time clustering algorithm. Steps 1 and 2 find exact k-mer matches between the N input sequences that are extended in step 3 and 4. (1) Linclust selects in each sequence the m (default: 20) k-mers with the lowest hash function values, as this tends to select the same k-mers across homologous sequences. It uses a reduced alphabet of 13 letters for the k-mers and sets k between 10 and 14 depending on the sequence set size and the sequence identity threshold. It generates a table in which each of the mN lines consists of the k-mer, the sequence identifier, and the position of the k-mer in the sequence. (2) Linclust sorts the table by k-mer in quasi-linear time, which identifies groups of sequences sharing the same k-mer (large shaded boxes). For each k-mer group, it selects the longest sequence as center. It thereby tends to select the same sequences as center among groups sharing sequences. (3) It merges k-mer groups with the same center sequence together (1: red + cyan and 5: orange + blue) and compares each group member to the center sequence in two steps: by global Hamming distance and by gapless local alignment extending the k-mer match. (4) Sequences above a score cut-off in step 3 are aligned to their center sequence using gapped local sequence alignment. Sequence pairs that satisfy the clustering criteria (e.g., on the E-value, sequence similarity, and sequence coverage) are linked by an edge. (5) The greedy incremental algorithm finds a clustering such that each input sequence has an edge to its cluster’s representative sequence. Note that the number of sequence pairs compared in steps 3 and 4 is less than mN, resulting in a linear time complexity
Fig. 5 Linear-time clustering algorithm. Steps 1 and 2 find exact k-mer matches between the N input sequences that are extended in step 3 and 4. (1) Linclust selects in each sequence the m (default: 20) k-mers with the lowest hash function values, as this tends to select the same k-mers across homologous sequences. It uses a reduced alphabet of 13 letters for the k-mers and sets k between 10 and 14 depending on the sequence set size and the sequence identity threshold. It generates a table in which each of the mN lines consists of the k-mer, the sequence identifier, and the position of the k-mer in the sequence. (2) Linclust sorts the table by k-mer in quasi-linear time, which identifies groups of sequences sharing the same k-mer (large shaded boxes). For each k-mer group, it selects the longest sequence as center. It thereby tends to select the same sequences as center among groups sharing sequences. (3) It merges k-mer groups with the same center sequence together (1: red + cyan and 5: orange + blue) and compares each group member to the center sequence in two steps: by global Hamming distance and by gapless local alignment extending the k-mer match. (4) Sequences above a score cut-off in step 3 are aligned to their center sequence using gapped local sequence alignment. Sequence pairs that satisfy the clustering criteria (e.g., on the E-value, sequence similarity, and sequence coverage) are linked by an edge. (5) The greedy incremental algorithm finds a clustering such that each input sequence has an edge to its cluster’s representative sequence. Note that the number of sequence pairs compared in steps 3 and 4 is less than mN, resulting in a linear time complexityCC BY · PubMed Central

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.

A few free checks a day · papers already verified open instantly · results are public

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

Show all 32 references

Research works printed but not linked: 2

  1. Marshall J. A. & Rafsky L. C. Exact clustering in linear time. Preprint at https://arxiv.org/abs/1702.05425 (2017). · arXiv
  2. Wang, J. Shen, H. T., Song, J. & Ji., J. Hashing for similarity search: a survey. Preprint at https://arxiv.org/abs/1408.2927 (2014). · arXiv

Cited by

See all 931

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)
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
Licence
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.