ESPRIT-Forest: Parallel clustering of massive amplicon sequence data in subquadratic time

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Genomic sequencing generates vast amounts of data, necessitating efficient analysis methods.
• Hierarchical clustering is a common but computationally intensive first step in sequence analysis.
• Existing methods struggle with the quadratic time and space complexity of large datasets.

Purpose of the Study:

• To develop a novel algorithm for parallel hierarchical clustering of large-scale genomic sequences.
• To overcome the computational limitations of traditional hierarchical clustering methods.
• To maintain high clustering accuracy while significantly reducing time and space complexity.

Main Methods:

• Developed ESPRIT-Forest, a parallel algorithm for hierarchical clustering.
• Utilizes a pseudo-metric based partitioning tree for sub-linear nearest neighbor searching.
• Employs a novel multiple-pair merging criterion for parallel cluster construction.

Main Results:

• ESPRIT-Forest achieves subquadratic time and space complexity.
• Demonstrated high clustering accuracy comparable to standard methods.
• Successfully applied to the Human Microbiome Project dataset, handling millions of sequences.

Conclusions:

• ESPRIT-Forest enables computationally feasible hierarchical clustering of massive sequence datasets.
• Parallel computing with ESPRIT-Forest makes analysis of millions of sequences practical.
• The algorithm offers a significant advancement for large-scale genomic sequence analysis.