Block aligner: fast and flexible pairwise sequence alignment with SIMD-accelerated adaptive blocks

Daniel Liu, Martin SteineggerbioRxiv 2021 · DOI

TL;DR

This paper introduces "block aligner," a novel algorithm that significantly speeds up pairwise sequence alignment for both DNA and protein sequences. By adaptively shifting and growing computation blocks, it achieves up to 9x faster protein alignment than existing methods while maintaining high accuracy, making it suitable for large-scale bioinformatics tasks.

What Problem Does This Paper Address?

Comparing biological sequences is fundamental to bioinformatics, powering everything from database searches to analyzing millions of sequencing reads. The gold standard for this is the Smith-Waterman-Gotoh (SWG) algorithm, which uses dynamic programming (DP) to find optimal alignments. However, SWG has a quadratic time complexity (O(N*M) for sequences of length N and M), making it prohibitively slow for the massive datasets generated today. While SIMD (Single Instruction Multiple Data) instructions have been used to accelerate alignment, existing SIMD-based methods often struggle with:

  • Specific scoring schemes: Some are optimized for particular scoring models.
  • Large gaps: They can't efficiently handle long insertions or deletions.
  • Quadratic time: They still require computing a significant portion of the DP matrix.
  • Protein alignment complexity: Handling large amino acid substitution matrices adds overhead.

This paper aims to bridge this gap by providing a fast, flexible, and accurate SIMD-accelerated alignment algorithm that can handle these challenges.

Methods

The core innovation is the "block aligner" algorithm. Instead of computing the entire DP matrix, it uses a novel "block" approach. Here's how it works:

  • Adaptive Blocking: The algorithm computes scores within a rectangular block of the DP matrix. This block is then adaptively shifted (right or down) based on where the highest scores are detected. This is inspired by adaptive banding techniques but with a key difference.
  • Block Growing for Gaps: To handle large gaps or regions of low sequence identity, the block aligner can dynamically grow its size. If the alignment score doesn't improve for a certain number of steps (a "Y-drop" heuristic), the block size is doubled, and computation restarts from a previous checkpoint. This allows it to span large gaps without being misled by local score drops.
  • SIMD Acceleration: The computation within these blocks is heavily accelerated using SIMD instructions (specifically AVX2 on x86 CPUs). The paper details how they tile SIMD vectors horizontally and vertically and use prefix scans to resolve dependencies within vectors efficiently.
  • Traceback: For obtaining the actual alignment path (e.g., CIGAR strings), they use a compact 2-bit encoding for trace directions, stored non-temporally to avoid cache pollution.

Crucially, this greedy approach means there's no theoretical guarantee of finding the absolute optimal score, unlike full DP. However, the authors demonstrate that it performs accurately in practice.

Datasets

The authors evaluated block aligner on a variety of datasets:

  • Simulated DNA/Protein Data: Generated with varying lengths, mutation rates, and specifically with inserted random subsequences to test gap handling.
  • Uniclust30 Protein Data: Real-world protein sequences from the Uniclust30 database, used to assess performance on varying sequence identities and coverage.
  • 25 kbp Nanopore Reads: Long DNA sequencing reads, a challenging dataset due to length and potential for gaps.
  • Illumina and 1 kbp Nanopore Reads: Shorter DNA sequencing reads.

They compared their method against several established algorithms, including Rust-bio (scalar full DP), Parasail (Farrar's SIMD), Seqan (Myers' bit-vector), Edlib, static banding methods, and adaptive banding methods.

Key Insights and Ideas

  • Greedy Block Growing is Key for Gaps: The ability to dynamically grow the computation block is a significant improvement over fixed-width banding or naive adaptive banding, allowing the algorithm to robustly handle large gaps and low-identity regions.
  • Accuracy-Speed Trade-off is Manageable: While not guaranteeing optimality, the block aligner's greedy strategy provides a good balance, achieving substantial speedups with minimal accuracy loss on realistic datasets.
  • SIMD Tiling Flexibility: The approach of tiling SIMD vectors both horizontally and vertically, combined with efficient prefix scan, is crucial for handling different alignment scenarios and scoring matrices.
  • Practicality for Real-World Data: The algorithm's design, particularly the score-agnostic Y-drop heuristic and fixed step sizes, makes it user-friendly and effective "out of the box" for diverse biological sequences.

Key Results

  • Speedup: Block aligner achieved up to 9 times faster protein global alignment compared to the popular Farrar's algorithm (Parasail). On sequencing reads, it was about 3 times slower than the highly optimized libgaba but still competitive.
  • Accuracy: On realistic datasets like Uniclust30, the error rate was generally low, especially with higher sequence identity and coverage. For example, on the "uc30 0.95" dataset, the average percent error for wrong scores was 4.4% with a block size of 32-256.
  • Gap Handling: Figure 4a demonstrates that the block growing heuristic effectively spans large gaps in random DNA sequences.
  • Efficiency: On average, block aligner computed only about 40% of the full DP matrix for Uniclust30 proteins when using a block size of 32-256.

Limitations and Future Work

  • Accuracy vs. Step Size: The authors acknowledge a trade-off between accuracy and efficiency related to the step size. A larger step size improves speed by reducing overhead but can slightly lower accuracy.
  • Greedy Nature: Like other greedy algorithms, block aligner can struggle with low-complexity or highly repetitive regions, potentially leading to suboptimal scores. Using larger block sizes can mitigate this but at the cost of speed.
  • Future Work:
    • Optimizing the interaction between computing rectangular regions and controlling block shifting/growing to allow smaller step sizes for better accuracy.
  • Supporting more SIMD instruction sets (AVX-512, ARM Neon) for broader portability and speed.
  • Implementing additional alignment modes, such as position-specific scoring matrices or local alignment, to expand its utility for protein analysis.

Summary updated

Abstract

Abstract Background The Smith-Waterman-Gotoh alignment algorithm is the most popular method for comparing biological sequences. Recently, Single Instruction Multiple Data methods have been used to speed up alignment. However, these algorithms have limitations like being optimized for specific scoring schemes, cannot handle large gaps, or require quadratic time computation. Results We propose a new algorithm called block aligner for aligning nucleotide and protein sequences. It greedily shifts and grows a block of computed scores to span large gaps within the aligned sequences. This greedy approach is able to only compute a fraction of the DP matrix. In exchange for these features, there is no guarantee that the computed scores are accurate compared to full DP. However, in our experiments, we show that block aligner performs accurately on various realistic datasets, and it is up to 9 times faster than the popular Farrar’s algorithm for protein global alignments. Conclusions Our algorithm has applications in computing global alignments and X -drop alignments on proteins and long reads. It is available as a Rust library at https://github.com/Daniel-Liu-c0deb0t/block-aligner .
BibTeX
@misc{liu2021block,
  author = {Daniel Liu and Martin Steinegger},
  title = {{Block aligner: fast and flexible pairwise sequence alignment with SIMD-accelerated adaptive blocks}},
  year = {2021},
  doi = {10.1101/2021.11.08.467651},
  howpublished = {bioRxiv},
}
Figure