English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Clustering huge protein sequence sets in linear time.

MPS-Authors
/persons/resource/persons200525

Steinegger,  M.
Research Group of Computational Biology, MPI for Biophysical Chemistry, Max Planck Society;

/persons/resource/persons128572

Söding,  J.
Research Group of Computational Biology, MPI for Biophysical Chemistry, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

2609064.pdf
(Publisher version), 2MB

Supplementary Material (public)

2609064_Suppl_1.pdf
(Supplementary material), 997KB

2609064_Suppl_2.pdf
(Supplementary material), 400KB

Citation

Steinegger, M., & Söding, J. (2018). Clustering huge protein sequence sets in linear time. Nature Communications, 9: 2542. doi:10.1038/s41467-018-04964-5.


Cite as: http://hdl.handle.net/21.11116/0000-0001-9887-B
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.