GeniOmics

Public knowledge document

Clustering huge protein sequence sets in linear time.

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.

Open platform knowledge

Clustering huge protein sequence sets in linear time.

> 商业许可源文 · EUROPE_PMC · [CC-BY](https://creativecommons.org/licenses/by/)

书目信息

  • 引用：Steinegger M, Söding J. (2018). Clustering huge protein sequence sets in linear time. Nature communications. PMID 29959318 · PMC6026198 · DOI 10.1038/s41467-018-04964-5
  • 证据类型：PRIMARY_RESEARCH
  • 主题：metagenomics
  • 被引次数（采集时）：652
  • 原始记录：[Europe PMC](https://europepmc.org/article/MED/29959318)
  • 来源许可：[CC-BY](https://creativecommons.org/licenses/by/)

    • 作者摘要（按来源许可复用）

    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.

    合规说明

    本页保存的是来源文献书目信息及其在 CC-BY 许可下公开的作者摘要。除去除来源 HTML 标签和规范化空白外，摘要未作内容改写。本页不代表 GeniOmics 的医学建议；原文版权、署名和许可仍归原权利人，请通过原始记录核对最新版本、更正或撤稿状态。

    Clustering huge protein sequence sets in linear time. · GeniOmics