Implementation of CUDA GPU-based parallel computing on Smith-Waterman algorithm to sequence database searches

摘要

In bioinformatics, one of the goldstandard algorithms to compute the optimal similarity score between sequences in a sequence database searches is Smith-Waterman algorithm that uses dynamic programming. This algorithm has a quadratic time complexity which requires a long computation time for large-sized data. In this issue, parallel computing is essential for sequence database searches in order to reduce the running time and to increase the performance. In this paper, we discuss the parallel implementation of Smith-Waterman algorithm in GPU using CUDA C programming language with NVCC compiler on Linux environment. Furthermore, we run the performance analysis using three parallelization models, including Inter-task Parallelization, Intra-task Parallelization, and a combination of both models. Based on the simulation results, a combination of both models has better performance than the others. In addition the parallelization using combination of both models achieves an average speed-up of 313x and an average efficiency with a factor of 0.93.