ESPRIT-Tree: Hierarchical Clustering Analysis of Millions of 16S rRNA Pyrosequences in Quasi-linear Time
Taxonomy independent analysis plays an essential role in microbial community analysis. Hierarchical clustering is one of the most widely employed approaches to finding OTUs, 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, and 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 dataset 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 average-linkage based hierarchical clustering algorithm. The algorithm is freely available upon request. Please send an email to Dr. Yijun Sun at yijunsun@buffalo.edu with your name, email address and affiliations.
Publication
Y. Cai* and Y. Sun*, ESPRIT-Tree: Hierarchical Clustering Analysis of Millions of 16S rRNA Pyrosequences in Quasilinear Time, Nucleic Acids Research, vol. 39, no. 14, e95, 2011.
Documents
- Manuscript and supplement accepted by Nucleic Acids Research
- User guide
- Program source code
- Simulation data and code used in the benchmark study
