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

Wei Chen, Yongmei Cheng, Clarence Zhang, Shaowu Zhang, Hongyu Zhao

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

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.

Original languageEnglish
Pages (from-to)347-355
Number of pages9
JournalJournal of Microbiological Methods
Volume94
Issue number3
DOIs
StatePublished - Sep 2013

Keywords

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

Fingerprint

Dive into the research topics of 'MSClust: A Multi-Seeds based Clustering algorithm for microbiome profiling using 16S rRNA sequence'. Together they form a unique fingerprint.

Cite this