Accelerating Smith-Waterman Alignment for Protein Database Search Using Frequency Distance Filtration Scheme Based on CPU-GPU Collaborative System

Yu Liu; Yang Hong; Chun-Yuan Lin; Che-Lun Hung

doi:10.1155/2015/761063

Accelerating Smith-Waterman Alignment for Protein Database Search Using Frequency Distance Filtration Scheme Based on CPU-GPU Collaborative System

Int J Genomics. 2015:2015:761063. doi: 10.1155/2015/761063. Epub 2015 Oct 19.

Authors

Yu Liu¹, Yang Hong¹, Chun-Yuan Lin², Che-Lun Hung³

Affiliations

¹ School of Electronic Information Engineering, Tianjin University, Tianjin 300072, China.
² Department of Computer Science and Information Engineering, Chang Gung University, Taoyuan 33302, Taiwan.
³ Department of Computer Science and Communication Engineering, Providence University, Taichung 43301, Taiwan.

Abstract

The Smith-Waterman (SW) algorithm has been widely utilized for searching biological sequence databases in bioinformatics. Recently, several works have adopted the graphic card with Graphic Processing Units (GPUs) and their associated CUDA model to enhance the performance of SW computations. However, these works mainly focused on the protein database search by using the intertask parallelization technique, and only using the GPU capability to do the SW computations one by one. Hence, in this paper, we will propose an efficient SW alignment method, called CUDA-SWfr, for the protein database search by using the intratask parallelization technique based on a CPU-GPU collaborative system. Before doing the SW computations on GPU, a procedure is applied on CPU by using the frequency distance filtration scheme (FDFS) to eliminate the unnecessary alignments. The experimental results indicate that CUDA-SWfr runs 9.6 times and 96 times faster than the CPU-based SW method without and with FDFS, respectively.