title: MSClust: A Multi-Seeds based Clustering algorithm for microbiome profiling using 16S rRNA sequence.
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.
authors.affiliation: College of Automation, Northwestern Polytechnical University, 710072 Xi'an, China.
authors.forename: Wei
authors.initials: W
authors.lastname: Chen
authors.forename: Yongmei
authors.initials: Y
authors.lastname: Cheng
authors.forename: Clarence
authors.initials: C
authors.lastname: Zhang
authors.forename: Shaowu
authors.initials: S
authors.lastname: Zhang
authors.forename: Hongyu
authors.initials: H
authors.lastname: Zhao
mesh_terms: D000465:Algorithms; D001419:Bacteria / Q000145:classification / Q000235:genetics; D016000:Cluster Analysis; D004269:DNA, Bacterial / Q000032:analysis / Q000235:genetics; D030541:Databases, Genetic; D064307:Microbiota; D010802:Phylogeny; D012336:RNA, Ribosomal, 16S; D017422:Sequence Analysis, DNA / Q000379:methods*
chemical_list: D004269:DNA, Bacterial; D012336:RNA, Ribosomal, 16S
keywords: 16S rRNA reads; Clustering algorithms; Next-generation sequencing; Operational taxonomic unit (OTU); Seeds-selection
references.citation: Bioinformatics. 2006 Jul 1;22(13):1658-9
references.pmid: 16731699
references.citation: Appl Environ Microbiol. 2009 Dec;75(23):7537-41
references.pmid: 19801464
references.citation: Environ Microbiol. 2010 Jul;12(7):1889-98
references.pmid: 20236171
references.citation: Bioinformatics. 2010 Apr 15;26(8):1105-11
references.pmid: 20185405
references.citation: Brief Bioinform. 2012 Jan;13(1):107-21
references.pmid: 21525143
references.citation: Nature. 2009 Jan 22;457(7228):480-4
references.pmid: 19043404
references.citation: BMC Bioinformatics. 2011 Dec 14;12:473
references.pmid: 22168258
references.citation: Bioinformatics. 2011 Mar 1;27(5):611-8
references.pmid: 21233169
references.citation: Nucleic Acids Res. 2009 Jan;37(Database issue):D141-5
references.pmid: 19004872
references.citation: BMC Bioinformatics. 2011 Jun 30;12:271
references.pmid: 21718538
references.citation: PLoS Comput Biol. 2011 Jan 20;7(1):e1001061
references.pmid: 21283775
references.citation: Appl Environ Microbiol. 2005 Mar;71(3):1501-6
references.pmid: 15746353
references.citation: Nucleic Acids Res. 2011 Aug;39(14):e95
references.pmid: 21596775
references.citation: Bioinformatics. 2010 Oct 1;26(19):2460-1
references.pmid: 20709691
references.citation: Appl Environ Microbiol. 2011 May;77(10):3219-26
references.pmid: 21421784
references.citation: BMC Res Notes. 2011 Oct 26;4:449
references.pmid: 22029428
references.citation: Proc Natl Acad Sci U S A. 2006 Aug 8;103(32):12115-20
references.pmid: 16880384
references.citation: BMC Bioinformatics. 2010 Dec 17;11:601
references.pmid: 21167044
references.citation: Nucleic Acids Res. 2009 Jun;37(10):e76
references.pmid: 19417062
references.citation: Genome Biol. 2007;8(7):R143
references.pmid: 17659080