title: DACE: a scalable DP-means algorithm for clustering extremely large sequence data.
abstract: Advancements in next-generation sequencing technology have produced large amounts of reads at low cost in a short time. In metagenomics, 16S and 18S rRNA gene have been widely used as marker genes to profile diversity of microorganisms in environmental samples. Through clustering of sequencing reads we can determine both number of OTUs and their relative abundance. In many applications, clustering of very large sequencing data with high efficiency and accuracy is essential for downstream analysis.
  
  
  
  Here, we report a scalable D irichlet Process Means (DP-means) a lgorithm for c lustering e xtremely large sequencing data, termed . With an efficient random projection partition strategy for parallel clustering, DACE can cluster billions of sequences within a couple of hours. Experimental results show that DACE runs between 6 and 80 times faster than state-of-the-art programs, while maintaining overall better clustering accuracy. Using 80 cores, DACE clustered the Lake Taihu 16S rRNA gene sequencing data (∼316M reads, 30 GB) in 25 min, and the Ocean TARA Eukaryotic 18S rRNA gene sequencing data (∼500M reads, 88 GB) into ∼100 000 clusters within an hour. When applied to the IGC gene catalogs in human gut microbiome (∼10M genes), DACE produced 9.8M clusters with 52K redundant genes in 1.5 hours of running time.
  
  
  
  DACE is available at https://github.com/tinglab/DACE .
  
  
  
  tingchen@mail.tsinghua.edu.cn or ningchen@mail.tsinghua.edu.cn.
  
  
  
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Bioinformatics Division, Center for Synthetic and Systems Biology, TNLIST, Department of Automation, Tsinghua University, Beijing, China.|Department of Computer Science and Technology, Tsinghua University, Beijing, China.
authors.forename: Linhao
authors.initials: L
authors.lastname: Jiang
authors.affiliation: Program in Computational Biology and Bioinformatics, University of Southern California, Los Angeles, CA, USA.
authors.forename: Yichao
authors.initials: Y
authors.lastname: Dong
authors.affiliation: Bioinformatics Division, Center for Synthetic and Systems Biology, TNLIST, Department of Automation, Tsinghua University, Beijing, China.|Department of Computer Science and Technology, Tsinghua University, Beijing, China.
authors.forename: Ning
authors.initials: N
authors.lastname: Chen
authors.affiliation: Bioinformatics Division, Center for Synthetic and Systems Biology, TNLIST, Department of Automation, Tsinghua University, Beijing, China.|Department of Computer Science and Technology, Tsinghua University, Beijing, China.|Program in Computational Biology and Bioinformatics, University of Southern California, Los Angeles, CA, USA.
authors.forename: Ting
authors.initials: T
authors.lastname: Chen
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D056890:Eukaryota / Q000235:genetics; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D006801:Humans; D056186:Metagenomics / Q000379:methods; D064307:Microbiota / Q000235:genetics; D012336:RNA, Ribosomal, 16S / Q000235:genetics; D012337:RNA, Ribosomal, 18S / Q000235:genetics; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software
chemical_list: D012336:RNA, Ribosomal, 16S; D012337:RNA, Ribosomal, 18S