Accelerating BWA-MEM Read Mapping on GPUs.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Next-Generation Sequencing (NGS) generates vast amounts of DNA data, necessitating efficient analysis tools.
• Mapping short DNA reads to a reference genome is a computationally intensive bottleneck in NGS data analysis.
• BWA-MEM and BWA-MEM2 are popular CPU-optimized algorithms for read mapping.

Purpose of the Study:

• To implement the BWA-MEM read mapping algorithm on Graphics Processing Units (GPUs).
• To identify and address challenges in adapting BWA-MEM's algorithms and data structures for GPU architecture.
• To evaluate the performance of the GPU implementation against established CPU-based versions.

Main Methods:

• Developed a GPU implementation of the BWA-MEM algorithm, addressing seeding, seed chaining, Smith-Waterman alignment, memory management, and I/O.
• Conducted performance comparisons using NVIDIA A40, A6000, and A100 GPUs against a 64-thread CPU running BWA-MEM and BWA-MEM2.
• Performed stage-wise analysis to assess speedups in key computational stages.

Main Results:

• Achieved up to 6.8x speedup over BWA-MEM and 3.8x over BWA-MEM2 on high-end GPUs.
• Demonstrated significant speedups in seeding/chaining (up to 4x), Smith-Waterman (up to 2.5x), and SAM output generation (up to 7.9x).
• This represents the first known attempt to implement the entire BWA-MEM program on GPUs.

Conclusions:

• GPU acceleration of BWA-MEM is feasible and offers substantial performance improvements for DNA sequence mapping.
• The developed GPU implementation addresses key computational challenges, providing a faster alternative for NGS data analysis.
• This work paves the way for more efficient genomic data processing pipelines.