Clustering huge protein sequence sets in linear time

By Martin Steinegger, Johannes Söding. 2017

848 citations recorded by the source corpus.

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. Billions of metagenomic and genomic sequences fill up public datasets, which makes similarity clustering an important and time-critical analysis step. Here, the authors develop Linclust, an algorithm with linear time complexity that can cluster over a billion sequences within hours on a single server.

Subfields: Artificial Intelligence, Molecular Biology, Algorithms & Complexity, Computational Biology & Bioinformatics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

In Algorithms & Complexity

In Computational Biology & Bioinformatics

Citations in the corpus

Analysis of several key factors influencing deep learning-based inter-residue contact prediction (2019, background): “6 billion metagenomic sequence fragments with 50% sequence identity (Steinegger and Soding, 2018).”
Accelerating Protein Design Using Autoregressive Generative Models (2019, methodology): “Due to the large number of sequences in the llama immune repertoire, sequence weights were approximated using Linclust (Steinegger & S¨oding, 2018) by clustering sequences at both 80% and 90% sequence identity thresholds.”
ColabFold: making protein folding accessible to all (2022, methodology): “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 res”
ProtTrans: Towards Cracking the Language of Life’s Code Through Self-Supervised Deep Learning and High Performance Computing (2020, methodology): “LMs were trained on the largest protein database ever used for this purpose, namely BFD [36], which was more than an order of magnitude larger than UniProt [37], the standard in the field.”
MGnify: the microbiome analysis resource in 2020 (2019, methodology): “To better understand the redundancy within the MGnify protein database, and to provide a more manageable dataset for users, we have used Linclust from the MMseqs (51) suite to cluster the sequences using 90% thresholds for overlap (of the shortest sequence) and sequence identity.”
Fast, accurate antibody structure prediction from deep learning on massive set of natural antibodies (2022, methodology): “108 To produce a diverse set of structures for data augmentation, we clustered (35) the paired and unpaired partitions 109 of the Observed Antibody Space (31) at 40% and 70% sequence identity, respectively.”
UniProt: the universal protein knowledgebase in 2021 (2020, methodology): “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…”