The review of the acceleration of Smith-Waterman algorithm by using CUDA-enable GPU

摘要

Smith-Waterman (SW) algorithm, which calculates the similarity between two given sequences, is broadly used in bioinformatics research field. However, the time complexity of the SW algorithm prevents it from being used for long sequence alignment. Since SW algorithm is based on dynamic programing, using single instruction multiple data parallel computing algorithm can significantly reduce the computing cost. For this reason, this review introduces three commonly used parallel computing algorithms based on Compute Unified Device Architecture (CUDA) for SW algorithm acceleration as well as illustrates their advantages and disadvantages.