Semiglobal Sequence Alignment with Gaps Using GPU.

Area of Science:

• Bioinformatics
• Computational Biology
• High-Performance Computing

Background:

• Genome re-sequencing requires assembling short reads using a reference sequence.
• Existing algorithms address single or bounded gaps, with some GPU acceleration for single gaps.
• Pair-wise semiglobal sequence alignment with gaps is crucial for sequence assembly.

Purpose of the Study:

• To propose and evaluate GPUGapsMis, a novel GPU-based algorithm for pair-wise semiglobal sequence alignment with a bounded number of gaps.
• To compare the performance of the GPU-based algorithm against a CPU-based counterpart (CPUGapsMis).
• To investigate optimal GPU utilization strategies, including hybrid and fully GPU models for alignment and backtracking phases.

Main Methods:

• Implementation of GPUGapsMis, a GPU-accelerated algorithm for sequence alignment with gaps.
• Comparative performance analysis between GPUGapsMis and CPUGapsMis on a CPU.
• Evaluation of different GPU models (hybrid vs. fully GPU) and parallelization strategies (single vs. multiple sequences).

Main Results:

• The alignment phase of GPUGapsMis demonstrates significant parallelization potential, achieving a peak speedup of 11x.
• Performing the sequential backtracking phase on the GPU is more efficient than returning to the CPU.
• GPUGapsMis achieves a peak speedup of 10.4x compared to CPUGapsMis when both phases are GPU-executed.
• The developed algorithm shows performance improvements over existing GPU implementations.

Conclusions:

• GPU-based acceleration is highly effective for the pair-wise semiglobal sequence alignment problem with bounded gaps.
• A fully GPU-based approach for both alignment and backtracking phases yields optimal performance gains.
• GPUGapsMis offers a substantial speedup for genome re-sequencing tasks, improving upon prior GPU implementations.