ESPRIT-Forest: Parallel Clustering of Massive Amplicon Sequence Data in Subquadratic Time
The rapid development of sequencing technology has led to an explosive accumulation of genomic sequence data. Clustering is often the first step to perform in sequence analysis, and hierarchical clustering is one of the most commonly used approaches for this purpose. However, due to its quadratic time and space complexities, it is currently computationally expensive to perform hierarchical clustering of extremely large sequence datasets. We developed a new algorithm called ESPRIT-Forest for parallel hierarchical clustering of sequences. The algorithm achieves subquadratic time and space complexity and maintains a high clustering accuracy comparable to the standard method. The basic idea is to organize sequences into a pseudo-metric based partitioning tree for sub-linear time searching of nearest neighbors, and then use a new multiple-pair merging criterion to construct clusters in parallel using multiple threads. The new algorithm was tested on the human microbiome project (HMP) dataset, currently the largest published microbial 16S rRNA sequence dataset. Our experiment demonstrated that with the power of parallel computing it is now computationally feasible to perform hierarchical clustering analysis of tens of millions of sequences.
Documents
- Source code
- License with Supplementary. ESPRIT-Forest is an open-source program with the Adaptive Public Lincense(APL-1.0). Please kindly show the license notice and the attribution information in your modified work as guided by APL.
- README
