Accelerating Smith-Waterman Alignment for Protein Database Search Using Frequency Distance Filtration Scheme Based on...

Area of Science:

• Bioinformatics
• Computational Biology
• High-Performance Computing

Background:

• The Smith-Waterman (SW) algorithm is crucial for biological sequence database searching.
• Existing GPU-accelerated SW methods primarily use intertask parallelization for protein searches, processing computations sequentially on GPUs.
• This approach limits the full utilization of GPU capabilities.

Purpose of the Study:

• To propose an efficient SW alignment method, CUDA-SWfr, for protein database searching.
• To leverage CPU-GPU collaborative systems and intratask parallelization for enhanced performance.
• To integrate a frequency-based filtration scheme to reduce computational overhead.

Main Methods:

• Developed CUDA-SWfr, a novel SW alignment method utilizing CPU-GPU collaborative processing.
• Implemented intratask parallelization for concurrent SW computations.
• Introduced the Frequency Distance Filtration Scheme (FDFS) executed on the CPU to pre-filter alignments before GPU processing.

Main Results:

• CUDA-SWfr demonstrates significant speed improvements over traditional CPU-based SW methods.
• The method achieves 9.6 times faster performance compared to a CPU-based SW approach without filtration.
• With FDFS, CUDA-SWfr achieves a 96-fold speedup, highlighting the effectiveness of the filtration scheme.

Conclusions:

• CUDA-SWfr offers a highly efficient solution for protein database searching using SW alignment.
• The CPU-GPU collaborative system combined with FDFS dramatically accelerates SW computations.
• This approach effectively utilizes GPU resources through intratask parallelization for improved bioinformatics analyses.