Research On GPU-based Parallel Computing On BLAST Program

Basic local alignment search tool BLAST is a bioinformatics tool used to quickly compare query sequence, and its implementation algorithm is kind of the heuristic. The algorithm has a higher focus on the similarities found in the local alignment, that is, record the maximum-length sequence pairs (MSP) scores, requiring local alignment can not contain spaces. The Position-Specific Iterated BLAST (PSI-BLAST) extend the length of the string of a selected standards in the sequence alignment in the allowed space, the search speed is three times the original algorithm.Aiming at the problem that BLAST can consume a lot of time for large-scale sequence alignments and can not achieve a real-time, combined with GPU high-speed parallelism, we propose to accelerate the BLAST program based on GPU (Graphics Processing Unit, GPU) in parallel. This program with CUDA (Compute Unified Device Architecture, CUDA) unified architecture, which was launched in June 2007 by NVIDIA, turns the implementation process into the process of parallel computing of CUDA thread block, so BLAST's subroutine BLASTx can accelerate the implementation in the GPU, beyond to achieve better results of the optimization at the same time, it also improved the procedures'executing speed.We design and implement a method to optimize BLAST procedures with parallelism, mainly based on GPU parallel computing platform, to turn the serial process of BLAST program into a parallel execution of CUDA thread. The research of parallel computing of BLAST's subroutine BLASTx which is based GPU turns the serial process of BLAST program into a parallel process of CUDA threads. Because of the particular of the comparison of BLASTx, this research keeps the point of GPU parallel computing, distributes the six amino acid sequences to six GPU blocks, so that the parallel between blocks in Grid is achieved. Meanwhile, there is another parallelism in a kernel function, which is the parallel between threads, therefore, after assigning the six amino acid sequences to the six blocks, the operator of the comparison of each amino acid sequence with the protein database can still be parallelized. To distribute the various amino acid sequences and distribute each amino acid sequence to each thread. And each thread executes the task of query protein databases at the same time. So that two levels'parallel operation is achieved. Also, the shared memory in blocks can not meet the huge capacity of the protein database's storage requirement, so to divide the protein database is needed. Only read part of the protein database each time. Based on the above, the time and memory consumption has been greatly reduced in the comparison process. At the same time, the use of GPU to the parallel transplantation of BLAST program is an effective method to solve the need of high-performance BLAST.The article also analyzes the performance of the parallel optimized BLAST program, parallel speedup and efficiency. And finally the test and simulation results are given in this paper. Finally, the paper summarizes the research work, and points out the content and direction of future research.