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.

Figure 1.

PBP tree. A PBP tree partitions an input space into a set of non-overlapped hyperspherical regions at various distance levels indicated by circles with different colors (a), and organizes input sequences in a tree-like hierarchical structure (b). Each point in (a) represents a sequence, and the color of a node in (b) corresponds to the color of a circle in (a). For ease of presentation, the leaf nodes are omitted, and a root node is created that includes all descendent nodes. The partition, though not necessarily reflecting the true structure of a data set as shown in (a), can significantly accelerate a clustering process by removing most unnecessary sequence alignment operations and distance computation.

Figure 2.

(a) NMI scores of four methods evaluated at 10 distance levels. (b) Box-plot of the maximum NMI scores of four methods. The species assignments of input sequences were used as ground truth.

Figure 3.

(a) NMI scores of four methods evaluated at 14 distance levels. (b) Box-plot of the maximum NMI scores of four methods. The genus assignments of input sequences were used as ground truth.

Figure 4.

Scalability of ESPRIT-Tree, CDHIT and UCLUST performed on a human gut microbiota data set with a varying number of sequences ranging from 1K to 1.1M. The empirical complexity and confidence interval (CI) are also reported.