title: ESPRIT-Tree: hierarchical clustering analysis of millions of 16S rRNA pyrosequences in quasilinear computational time.
abstract: Taxonomy-independent analysis plays an essential role in microbial community analysis. Hierarchical clustering is one of the most widely employed approaches to finding operational taxonomic units, the basis for many downstream analyses. Most existing algorithms have quadratic space and computational complexities, and thus can be used only for small or medium-scale problems. We propose a new online learning-based algorithm that simultaneously addresses the space and computational issues of prior work. The basic idea is to partition a sequence space into a set of subspaces using a partition tree constructed using a pseudometric, then recursively refine a clustering structure in these subspaces. The technique relies on new methods for fast closest-pair searching and efficient dynamic insertion and deletion of tree nodes. To avoid exhaustive computation of pairwise distances between clusters, we represent each cluster of sequences as a probabilistic sequence, and define a set of operations to align these probabilistic sequences and compute genetic distances between them. We present analyses of space and computational complexity, and demonstrate the effectiveness of our new algorithm using a human gut microbiota data set with over one million sequences. The new algorithm exhibits a quasilinear time and space complexity comparable to greedy heuristic clustering algorithms, while achieving a similar accuracy to the standard hierarchical clustering algorithm.
authors: Interdisciplinary Center for Biotechnology Research University of Florida, Gainesville, FL 32610, USA.
authors: Yunpeng
authors: Y
authors: Cai
authors: Yijun
authors: Y
authors: Sun
references: Appl Environ Microbiol. 2005 Mar;71(3):1501-6
references: 15746353
references: IEEE Trans Pattern Anal Mach Intell. 2006 Nov;28(11):1875-81
references: 17063692
references: Appl Environ Microbiol. 2009 Dec;75(23):7537-41
references: 19801464
references: PLoS Biol. 2008 Nov 18;6(11):e280
references: 19018661
references: Bioinformatics. 2010 Oct 1;26(19):2460-1
references: 20709691
references: Appl Environ Microbiol. 1997 Jul;63(7):2647-53
references: 9212415
references: Nature. 2009 Jan 22;457(7228):480-4
references: 19043404
references: J Comput Biol. 2000 Feb-Apr;7(1-2):203-14
references: 10890397
references: Nucleic Acids Res. 2009 Jan;37(Database issue):D141-5
references: 19004872
references: BMC Bioinformatics. 2010 Mar 24;11:152
references: 20334679
references: PLoS Genet. 2008 Nov;4(11):e1000255
references: 19023400
references: Bioinformatics. 2006 Jul 1;22(13):1658-9
references: 16731699
references: Lancet. 2003 Aug 9;362(9382):433-9
references: 12927430
references: Environ Microbiol. 2010 Jul;12(7):1889-98
references: 20236171
references: Appl Environ Microbiol. 2007 Aug;73(16):5261-7
references: 17586664
references: Brief Bioinform. 2012 Jan;13(1):107-21
references: 21525143
references: Proc Natl Acad Sci U S A. 2006 Aug 8;103(32):12115-20
references: 16880384
references: J Mol Biol. 1970 Mar;48(3):443-53
references: 5420325
references: Nucleic Acids Res. 2009 Jun;37(10):e76
references: 19417062
references: Environ Microbiol. 2002 Nov;4(11):654-66
references: 12460273
references: Proc Natl Acad Sci U S A. 1998 Dec 8;95(25):14863-8
references: 9843981
references: Science. 2007 Oct 5;318(5847):97-100
references: 17916733
references: Nucleic Acids Res. 2010 Dec;38(22):e205
references: 20929878
references: Nat Methods. 2009 Sep;6(9):639-41
references: 19668203
references: Nat Methods. 2010 May;7(5):335-6
references: 20383131
references: Genome Res. 2009 Dec;19(12):2317-23
references: 19819907
references: Science. 2005 Jun 10;308(5728):1635-8
references: 15831718
references: J Mol Biol. 1990 Oct 5;215(3):403-10
references: 2231712
references: Nucleic Acids Res. 2004 Mar 19;32(5):1792-7
references: 15034147