CUDA-MAFFT: Accelerating MAFFT on CUDA-enabled graphics hardware

Multiple sequence alignment (MSA) constitutes an extremely powerful tool for many biological applications including phylogenetic tree estimation, secondary structure prediction, and critical residue identification. However, aligning large biological sequences with popular tools such as MAFFT requires long runtimes on sequential architectures. Due to the ever increasing sizes of sequence databases, there is increasing demand to accelerate this task. In this paper, we demonstrate how Graphic Processing Units (GPUs), powered by the Compute Unified Device Architecture (CUDA), can be used as an efficient computational platform to accelerate the MAFFT algorithm. To fully exploit the GPU´s capabilities for accelerating MAFFT, we have optimized the sequence data organization to eliminate the bandwidth bottleneck of memory access, and designed a memory allocation and reuse strategy to make full use of limited memory of GPUs. Our implementation achieves speedup up to 19.58 and 4.14 on an NVIDIA Tesla C2050 GPU compared to the sequential and multi-thread MAFFT 7.017, respectively.