Abstract
The Smith-Waterman algorithm is the gold standard for local sequence alignment in bioinformatics but is limited by high computational costs. This paper describes an implementation of the Double Affine Smith-Waterman (DASW) algorithm on commodity GPU hardware using the OpenGL API. By reimagining dynamic programming as a fragment shading task and utilizing diagonal processing to manage data dependencies, the authors achieved a throughput of over 241 million cells per second. This represents a 2x speedup over highly optimized CPU software and a 4.7x improvement over standard implementations, highlighting the viability of GPUs as cost-effective accelerators for genomic research.
Introduction
Sequence comparison is essential for identifying functional, structural, or evolutionary relationships between biological sequences. While the Smith-Waterman algorithm provides optimal sensitivity for local alignment, its reliance on dynamic programming (DP) makes it computationally expensive, especially as genomic databases grow. Traditional CPUs struggle with the $O(mn)$ complexity of the algorithm. While specialized hardware like FPGAs offers performance gains, they are often prohibitively expensive and difficult to program. This study explores the use of standard graphics processing units (GPUs) as a high-performance, low-cost alternative for accelerating the Double Affine Smith-Waterman (DASW) algorithm.
Methods
The implementation utilizes the Double Affine Smith-Waterman (DASW) model, which employs two affine gap penalties to better reflect biological realities such as long insertions or deletions. In 2006, before the advent of general-purpose GPU computing frameworks like CUDA, the authors utilized the OpenGL API and GLSL (shading language) to perform general-purpose computation.
The alignment process was mapped to the standard graphics pipeline:
- Geometry Transformation: Quadrilaterals were defined to represent the computational domain.
- Fragment Rasterization: The GPU's fragment processors were used to evaluate the DP recurrence relations.
- Diagonal Processing: To address the data dependencies inherent in DP (where a cell $(i, j)$ depends on $(i-1, j)$, $(i, j-1)$, and $(i-1, j-1)$), the table was processed diagonally. All cells on a single diagonal are independent and can be computed in parallel.
- Data Management: 16-bit floating-point numbers were used to optimize memory bandwidth, and data for multiple DP cells were packed into single pixels to maximize throughput.
To maintain high GPU utilization, multiple target sequences were concatenated into a single long string, allowing the GPU to avoid idling during the processing of smaller sequences.
Results
The system was evaluated by aligning a query sequence of 16,384 amino acids against a database of 983 protein sequences (totaling 462,862 amino acids), resulting in approximately 7.5 billion DP cell computations. The GPU implementation was compared against osearch34 (standard Smith-Waterman) and ssearch34 (optimized SWAT heuristic) from the FastA suite.
The GPU implementation demonstrated significant performance advantages. In "Score Only" mode (ASM), the GPU reached a throughput of 241.12 million cells per second.
As shown in the table, the GPU (ASM) was 2x faster than the best-optimized CPU software (ssearch34) and nearly 4.7x faster than the standard osearch34 implementation. Furthermore, the authors noted that a $500 GPU outperformed a $600 Intel Pentium D processor, providing a superior performance-to-price ratio.
Discussion and Conclusion
While the results are promising, the implementation faced bottlenecks related to internal memory bandwidth. Although the GPU had a peak theoretical performance of 313 GFLOPS, the memory-intensive nature of DASW limited actual performance to approximately 70 GFLOPS. Additionally, the 256MB of on-board memory limited the sequence lengths feasible for the "Trace Back" (ATM) mode.
Despite these limitations, the study successfully demonstrated that commodity GPUs can serve as powerful SIMD engines for bioinformatics. Future work includes scaling this approach to GPU clusters and applying the parallel DP framework to other optimization problems in computational biology.
Summary updated