Better Greedy Sequence Clustering with Fast Banded Alignment

Brian Brubach, Jay Ghurye, Mihai Pop, Aravind Srinivasan

TL;DR

This paper introduces a novel, faster greedy clustering algorithm for large genomic datasets, specifically 16S rRNA gene sequences. By combining a specialized trie data structure with a Four Russians speedup for banded alignment, their method achieves near-linear scaling in runtime, significantly outperforming existing quadratic approaches, especially at high similarity thresholds.

What Problem Does This Paper Address?

Clustering biological sequences, particularly 16S rRNA genes into Operational Taxonomic Units (OTUs), is fundamental for understanding microbial communities. Traditional methods involve computationally expensive all-vs-all comparisons and hierarchical clustering, which become infeasible for the massive datasets generated by modern sequencing technologies (billions of short reads). While greedy clustering heuristics offer a practical alternative, their worst-case runtime can still be quadratic. This paper tackles the challenge of efficiently clustering these enormous datasets while maintaining or improving cluster quality, focusing on the critical step of comparing a query sequence against a large database of existing sequences.

Methods

The core innovation lies in a new greedy clustering algorithm that leverages two key techniques:

  • Fast Banded Alignment with Four Russians Speedup: The authors adapt the classical Four Russians speedup, a technique for accelerating dynamic programming computations, to the problem of banded alignment. Banded alignment is a specialized form of edit distance calculation that only considers a narrow "band" around the main diagonal of the dynamic programming table, making it faster when sequences are expected to be highly similar. Their approach uses a modified block function that efficiently stitches together results from overlapping blocks, reducing the computational overhead.
  • Edit Distance Interval Trie (EDIT): To accelerate the "recruitment" step (finding all sequences similar to a cluster center), they introduce a trie-like data structure. This structure is built by partitioning sequences into overlapping intervals of a specific length. Each sequence is then represented by a vector of integer signatures corresponding to these intervals. This trie allows for efficient, depth-first traversal to identify candidate sequences within a specified edit distance, pruning branches that exceed the distance threshold early.

Datasets

The primary dataset used for evaluation was a real-world 16S rRNA gene dataset containing approximately 57 million sequences with 2.7 million distinct sequences. This dataset is representative of the large-scale data encountered in metagenomic studies.

Key Insights and Ideas

  • Linear Scaling is Achievable: The most significant insight is that by carefully optimizing the sequence comparison and recruitment steps, the overall greedy clustering process can achieve near-linear scaling with the dataset size, a major breakthrough for handling massive genomic datasets.
  • Trie-based Recruitment is Efficient: The EDIT data structure effectively prunes the search space during recruitment, drastically reducing the number of actual sequence comparisons needed compared to naive approaches.
  • High Similarity Thresholds Favor the New Method: While existing tools like UCLUST are faster at lower similarity thresholds, the proposed method demonstrates superior performance and scalability at higher similarity thresholds (e.g., 99%), where the banded alignment assumption is more valid.
  • Tighter and Larger Clusters: The algorithm consistently produces clusters that are both tighter (smaller diameter) and larger (more sequences per cluster) than those generated by UCLUST, particularly at high similarity thresholds, suggesting a more accurate and comprehensive grouping of related sequences.

Key Results

  • Runtime: The algorithm's running time grows linearly with the size of the dataset, a significant improvement over the quadratic complexity of traditional methods. At a 99% similarity threshold and with large sample sizes (over 1 million sequences), the new method was up to ten times faster than UCLUST.
  • Cluster Quality: At a 99% similarity threshold, the new method generated significantly larger clusters compared to UCLUST. The edit distance diameter of the clusters produced by the new method was also more constrained, indicating higher homogeneity within clusters.
  • Scalability: The running time of the new method showed low variance and scaled almost linearly, whereas UCLUST's runtime increased dramatically with larger sample sizes and higher similarity thresholds.

Limitations and Future Work

  • Limitations: The paper acknowledges that the current implementation relies on a fixed block size k that is dependent on the maximum distance d. While this is effective, further exploration of optimal k selection could be beneficial. The paper also notes that while the method generates mathematically well-defined clusters, defining biologically meaningful thresholds remains a challenge.
  • Future Work: The authors plan to extend their algorithm to be parallelized, specifically by parallelizing the traversal of tree branches. They also aim to explore methods for efficiently flagging and excluding singleton sequences, which currently dominate the running time. Additionally, they suggest investigating k-mer filters and locality-sensitive hashing for faster singleton identification.

Summary updated

Abstract

Comparing a string to a large set of sequences is a key subroutine in greedy heuristics for clustering genomic data. Clustering 16S rRNA gene sequences into operational taxonomic units (OTUs) is a common method used in studying microbial communities. We present a new approach to greedy clustering using a trie-like data structure and Four Russians speedup. We evaluate the running time of our method in terms of the number of comparisons it makes during clustering and show in experimental results that the number of comparisons grows linearly with the size of the dataset as opposed to the quadratic running time of other methods. We compare the clusters output by our method to the popular greedy clustering tool UCLUST. We show that the clusters we generate can be both tighter and larger.
BibTeX
@inproceedings{brubach2017better,
  author = {Brian Brubach and Jay Ghurye and Mihai Pop and Aravind Srinivasan},
  title = {{Better Greedy Sequence Clustering with Fast Banded Alignment}},
  booktitle = {WABI},
  year = {2017},
  doi = {10.4230/lipics.wabi.2017.3},
}

Loading related content...

Figure