Accelign: a GPU-based Library for Accelerating Pairwise Sequence Alignment

Felix Kallenborn, Fawaz Dabbaghie, Martin Steinegger, Bertil SchmidtbioRxiv 2025 · DOI

TL;DR

The ever-growing volume of biological sequence data demands faster alignment algorithms. Accelign is a new GPU-accelerated library that significantly speeds up pairwise sequence alignment for DNA, RNA, and proteins, outperforming existing CPU and GPU solutions and offering flexible, scalable performance.

What Problem Does This Paper Address?

The explosion of high-throughput sequencing technologies has led to an unprecedented surge in biological data. A fundamental task in analyzing this data is pairwise sequence alignment, which compares two sequences to find similarities. This is often done using dynamic programming (DP) algorithms, which have a quadratic time complexity ($O(n \cdot m)$ where $n$ and $m$ are sequence lengths). This quadratic complexity makes them a major bottleneck in many bioinformatics pipelines, especially when dealing with massive datasets. While various parallel implementations exist for CPUs, GPUs, and FPGAs, current GPU solutions often lack flexibility, being narrowly optimized for specific sequence types, alignment paradigms, or scoring schemes. This limits their applicability and requires significant architectural changes to adapt them to new problems.

Methods

Accelign tackles this by providing a flexible, GPU-accelerated library for various pairwise sequence alignment algorithms. Its core innovation lies in a wavefront parallelization strategy that can be adapted to different DP algorithms. This strategy leverages in-register computation and warp-level primitives (like shfl_down_sync and shfl_up_sync) to minimize memory traffic and maximize instruction throughput.

Key methodological aspects include:

  • Unified Core Algorithm: A single core algorithm is specialized for different alignment types (local, global, semi-global), scoring schemes (linear/affine gaps, substitution matrices, PSSMs), and sequence data types (DNA, RNA, protein).
  • Optimized Kernels: Specialized kernels are developed for different data types (e.g., 32-bit float, 16-bit half2, 8-bit uint8x4) and GPU architectures (leveraging features like Half2 Arithmetic, Max3 Instructions, and DPX instructions on newer NVIDIA GPUs).
  • Memory Management: Efficient use of on-chip shared memory and thread-local registers is prioritized to reduce reliance on slower global memory. Techniques like matrix tiling are employed for handling long sequences.
  • Flexible Scoring: Support for both standard substitution matrices and Position Specific Scoring Matrices (PSSMs) is integrated.
  • Multi-GPU Support: The library is designed to scale linearly with the number of GPUs, allowing for increased processing speeds on multi-GPU nodes.
  • Start/End Position Calculation: While full traceback is not provided, Accelign can compute the start and end coordinates of alignments, which can then be used by external libraries for traceback.

Datasets

The paper evaluates Accelign using:

  • Simulated Datasets: Used for theoretical peak performance evaluation and initial benchmarking across different GPU architectures.
  • Real-World Datasets:
    • Illumina Short Reads: Used for a short-read alignment case study, comparing against reference genomes.
  • Nanopore Reads: Used to evaluate performance on longer, potentially noisier reads.
  • UniRef50 Protein Database: Used for protein database scanning (homology search) with a set of real-world protein queries.
  • HIV Subtype O Assembly: Used for HIV read mapping to assess performance on evolutionarily divergent sequences.

The paper also references existing benchmarks and datasets used by competing libraries.

Key Insights and Ideas

  • Wavefront Parallelism is Key: The wavefront approach, combined with efficient inter-thread communication via warp shuffles, is crucial for maximizing GPU utilization in DP computations.
  • In-Register Computation is Paramount: Keeping intermediate DP values in registers, rather than constantly accessing global memory, dramatically boosts performance.
  • Flexibility Doesn't Have to Mean Slow: Accelign demonstrates that a single, adaptable core algorithm can achieve high performance across diverse alignment tasks, unlike many specialized GPU libraries.
  • Newer GPUs Offer Significant Gains: The performance improvements seen with Blackwell and Hopper architectures highlight the importance of leveraging specialized hardware instructions for DP.
  • PSSMs Can Outperform Substitution Matrices: For one-to-all alignments, PSSMs offer a significant performance advantage, especially for shorter sequences, due to better memory access patterns.
  • Data Transfer is a Bottleneck (Sometimes): While GPU compute is fast, data transfer between CPU and GPU can still limit overall performance, especially on systems with slower interconnects. Accelign's ability to accept contiguous data buffers helps mitigate this.

Key Results

  • Peak Performance: Achieved up to 16.1 TCUPS (Trillions of Cell Updates Per Second) on a single RTX PRO 6000 Blackwell GPU for global alignment.
  • Speedups:
    • Demonstrated significant speedups over prior CPU-based (SeqAn, Parasail, BSalign, EdLib, KSW2, WFA2, A*PA2) and GPU-based (ADEPT, GASAL2) libraries.
  • Outperformed highly customized algorithms like WFA-GPU and CUDASW++4.0 in several benchmarks.
  • Achieved up to 2.6x to 3.4x faster performance than A100 GPUs and 1.5x to 1.9x faster than L40S GPUs on a specific kernel.
  • Efficiency: Achieved up to 77% of theoretical peak performance on a Blackwell GPU, indicating a compute-bound implementation.
  • Case Study Success:
    • Short-read alignment: Accelign was faster than competing libraries and handled data transfer more efficiently.
  • Protein database scanning: Outperformed CUDASW++4.0 and CPU-based BLASTP, especially with 8-bit integer computations.
  • HIV read mapping: Aligned significantly more sequences than BWA for evolutionarily divergent data, highlighting the benefit of exact alignment.
  • Scalability: Performance scales linearly with the number of GPUs.

Limitations and Future Work

  • Traceback Not Supported: Accelign currently computes alignment scores and start/end positions but not full traceback paths. This is a significant limitation for many applications.
  • 16-bit Accuracy Concerns: While 16-bit types offer speedups, they can lead to inaccuracies for scores outside a certain range. The authors suggest using 32-bit types if a wider range is needed.
  • Memory Usage for Large Alphabets: For types like half2 or short2, memory usage grows quadratically with alphabet size, limiting practical application for very large alphabets without low-memory variants.
  • Future Work:
    • GPU-Accelerated Traceback: This is identified as a key extension to address the current limitation.
  • Dynamic Time Warping: The library's generic parallelization strategy could be extended to other DP-based algorithms like dynamic time warping.
  • Profile HMMs and Profile-to-Profile Alignments: These are also suggested as potential extensions.
  • Improved Partitioning Schemes: More advanced partitioning strategies for multi-GPU setups could further enhance load balancing.

Summary updated

Abstract

Abstract Background The continually increasing volume of sequence data results in a growing demand for fast implementations of core algorithms. Computation of pairwise alignments based on dynamic programming is an important part in many bioinformatics pipelines and a major contributor to overall runtime due to the associated quadratic time complexity. This motivates the need for a library of efficient implementations on modern GPUs for a variety of alignment algorithms for different types of sequence data including DNA, RNA, and proteins. Results Accelign is a library of accelerated pairwise sequence alignment algorithms for CUDA-enabled GPUs. Its parallelization strategy is based on a common wavefront design that can be adapted to support a variety of dynamic programming algorithms: local, global, and semi-global alignment of genomic and protein sequences with a variety of commonly used scoring schemes supporting one-to-one, one-to-many or all-to-all pairwise sequence alignments. This leads to a peak performance between 16.1 TCUPS and 9.1 TCUPS for computing optimal global alignment scores with linear gaps and affine gap penalties on a single RTX PRO 6000 Blackwell GPU, respectively. In addition, our library demonstrates significant speedups in several real-world case studies over prior CPU-based (SeqAn, Parasail, BSalign) and GPU-based libraries (ADEPT, GASAL2), and can even outperform highly customized algorithms (WFA-GPU, CUDASW++4.0). Furthermore, the performance of our approach scales linearly with the number of employed GPUs, which makes it feasible to exploit multi-GPU nodes for increased processing speeds. Conclusion Accelign provides significant speedups for commonly used pairwise alignment algorithms compared to prior implementations. It is freely available at https://github.com/fkallen/Accelign .
BibTeX
@misc{kallenborn2025accelign,
  author = {Felix Kallenborn and Fawaz Dabbaghie and Martin Steinegger and Bertil Schmidt},
  title = {{Accelign: a GPU-based Library for Accelerating Pairwise Sequence Alignment}},
  year = {2025},
  doi = {10.64898/2025.12.17.694868},
  howpublished = {bioRxiv},
}
Figure