Sequence alignment is a fundamental task for computational genomics research. We develop G-Aligner, which adopts the GPU as a hardware accelerator to speed up the sequence alignment process. A leading CPU-based alignment tool is based on the Bi-BWT index; however, a direct implementation of this algorithm on the GPU cannot fully utilize the hardware power due to its irregular algorithmic structure. To better utilize the GPU hardware resource, we propose a filtering-verification algorithm employing both the Bi-BWT search and direct matching. We further improve this algorithm on the GPU through various optimizations, e.g., the split of a large kernel, the warp based implementation to avoid user-level synchronization. As a result, G-Aligner outperforms another state-of-the-art GPU-accelerated alignment tools SOAP3 by 1.8–3.5 times for in-memory sequence alignment.
Mian Lu, Yuwei Tan, Ge Bai and Qiong Luo. High-performance short sequence alignment with GPU acceleration. Distributed and Parallel Databases. Volume 30, Numbers 5-6, pp 385-399, 2012. [doi: 10.1007/s10619-012-7099-x]