The Research Of Distributed Parallel Optimization Of Pairwise Sequence Alignment Needleman-Wunsch Algorithm

It is one of the important contents of bioinformatics that the relationship between different sequences is excavated by sequence alignment algorithm. In many of the sequence alignment algorithm, based on dynamic programming sequence alignment algorithm of the Needleman-Wunsch algorithm with optimal characteristics of the, but it has a higher time and space complexity, and with the rapid development of sequencing technology and gene sequence data year by year refers to the number of growth trend of rapid increase. Currently most researchers through the method of high-performance multi-core computation to solve these problems in front of.In combination with the expensive of high performance computing devices and the limited resources, as well as the characteristics of the data is dependent in the Needleman-Wunch algorithm, it is difficult to use the ordinary parallel technology. Therefore, this paper puts forward the distributed parallel algorithm based on the MPI programming technology in heterogeneous cluster environment. The distributed parallel task scheduling algorithm based on divisible load theory to compare the score matrix. By determining the optimal number of iterations and child nodes for subsequence length to make full use of various nodes compute resources, making the implementation of continuous makes calculation task. This paper also make improvement about the procss of the filling and back, through the LIFO strategy to make the integral algorithm to optimize communication in filling process, and to reduce the complexity of time and space of the overall algorithm.Through the experimental data shows that the parallel algorithm proposed in the paper is less than the single serial and the other parallel algorithm in the running time,and getting the desired effect. At the same time, the environment of the algorithm has the simple structure, and the practicability is strong.