hc-OTU: A Fast and Accurate Method for Clustering Operational Taxonomic Units Based on Homopolymer Compaction
- 26 February 2016
- journal article
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 15 (2) , 441-451
Abstract
To assess the genetic diversity of an environmental sample in metagenomics studies, the amplicon sequences of 16s rRNA genes need to be clustered into operational taxonomic units (OTUs). Many existing tools for OTU clustering trade off between accuracy and computational efficiency. We propose a novel OTU clustering algorithm, hc-OTU, which achieves high accuracy and fast runtime by exploiting homopolymer compaction and k-mer profiling to significantly reduce the computing time for pairwise distances of amplicon sequences. We compare the proposed method with other widely used methods, including UCLUST, CD-HIT, MOTHUR, ESPRIT, ESPRIT-TREE, and CLUSTOM, comprehensively, using nine different experimental datasets and many evaluation metrics, such as normalized mutual information, adjusted Rand index, measure of concordance, and F-score. Our evaluation reveals that the proposed method achieves a level of accuracy comparable to the respective accuracy levels of MOTHUR and ESPRIT-TREE, two widely used OTU clustering methods, while delivering orders-of-magnitude speedups.Keywords
Funding Information
- National Research Foundation of Korea
- Ministry of Science, ICT and Future Planning, MSIP (2011-0009963, 2014M3C9A3063541)
- Industrial Core Technology Development Program (10040176)
- Ministry of Trade, Industry and Energy
- Samsung Electronics Co., Ltd.
- NRF
- Korea government (2013R1A1A1057949, 2014R1A4A1007895)
This publication has 33 references indexed in Scilit:
- CLUSTOM: A Novel Method for Clustering 16S rRNA Next Generation Sequences by Overlap MinimizationPLOS ONE, 2013
- Ultrafast clustering algorithms for metagenomic sequence analysisBriefings in Bioinformatics, 2012
- TBC: A clustering algorithm based on prokaryotic taxonomyJournal of Microbiology, 2012
- UCHIME improves sensitivity and speed of chimera detectionBioinformatics, 2011
- A large-scale benchmark study of existing algorithms for taxonomy-independent microbial community analysisBriefings in Bioinformatics, 2011
- Search and clustering orders of magnitude faster than BLASTBioinformatics, 2010
- ESPRIT: estimating species richness using large collections of 16S rRNA pyrosequencesNucleic Acids Research, 2009
- Microbial diversity in the deep sea and the underexplored “rare biosphere”Proceedings of the National Academy of Sciences, 2006
- Gapped BLAST and PSI-BLAST: a new generation of protein database search programsNucleic Acids Research, 1997
- Comparing partitionsJournal of Classification, 1985