Design And Implementation Of GPU-based Fast Sequence Alignment Software

The basic problem of protein sequence alignment is to compare the similarity or dissimilarity of biological gene symbol sequences,which is one of the representative problems of bioinformatics.So far,the algorithm of sequence alignment includes the Needleman-Wunsch algorithm and Smith-Waterman algorithm and other normal sequence alignment,mainly for primary structure and secondary structure alignemnt.However,with the increasing scale of biological sequence data,it is a hot research to improve the efficiency of sequence alignment algorithm.Using the parallel processing capability of GPU(Graphics Processing Unit),the parallel algorithm based on GPU-based profile-profile sequence alignment is very important for rapid analysis of protein sequences.GPU-based rapid sequence alignment software uses C language programming and CUDA function library development in Linux operating system.Firstly,explain the necessity and feasibility of software development through in-depth analysis of GPU parallel computing and sequence alignment algorithm at home and abroad research status and technical characteristics.Secondly,from the functional requirements,carry out the software function modules,such as program preparation,files read and write,algorithm preparation,sequence alignment,etc.detailed design.Thirdly,in-depth analysis of GPU features and algorithm features to describe the concrete implementation of GPU acceleration sequence alignment algorithm From the algorithm parallelism,sub-kernel function,storage space allocation,set the number of threads and the number of blocks and so on.Using DataSet contained 53634 sequences to test the software.Experimental analyses how sequence number,sequence length and block's number influence the accelerating effect.Results show that,with the same parameters and data,the maximum speedup of the algorithm is 23 and the average speedup is above 10 comparing the running time of algorithm on GPU and CPU.