Format

Send to:

Choose Destination
See comment in PubMed Commons below
J Microbiol Methods. 2013 Sep;94(3):347-55. doi: 10.1016/j.mimet.2013.07.004. Epub 2013 Jul 28.

MSClust: A Multi-Seeds based Clustering algorithm for microbiome profiling using 16S rRNA sequence.

Author information

  • 1College of Automation, Northwestern Polytechnical University, 710072 Xi'an, China.

Abstract

Recent developments of next generation sequencing technologies have led to rapid accumulation of 16S rRNA sequences for microbiome profiling. One key step in data processing is to cluster short sequences into operational taxonomic units (OTUs). Although many methods have been proposed for OTU inferences, a major challenge is the balance between inference accuracy and computational efficiency, where inference accuracy is often sacrificed to accommodate the need to analyze large numbers of sequences. Inspired by the hierarchical clustering method and a modified greedy network clustering algorithm, we propose a novel multi-seeds based heuristic clustering method, named MSClust, for OTU inference. MSClust first adaptively selects multi-seeds instead of one seed for each candidate cluster, and the reads are then processed using a greedy clustering strategy. Through many numerical examples, we demonstrate that MSClust enjoys less memory usage, and better biological accuracy compared to existing heuristic clustering methods while preserving efficiency and scalability.

© 2013 Elsevier B.V. All rights reserved.

KEYWORDS:

16S rRNA reads; Clustering algorithms; Next-generation sequencing; Operational taxonomic unit (OTU); Seeds-selection

PMID:
23899776
[PubMed - indexed for MEDLINE]
PMCID:
PMC3895816
Free PMC Article
PubMed Commons home

PubMed Commons

0 comments
How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for Elsevier Science Icon for PubMed Central
    Loading ...
    Write to the Help Desk