The Research Of Pairwise Alignment Algorithm And Parallel Optimization

Pairwise Alignment is the most fundamental problem and a very important studypart in bioinformatics. There are two standards to evaluate algorithm for sequencealignment: one is the operation speed of the algorithm, and the other is the sensitivity ofalignment output. As the accumulation of a great deal of biological data, people putforward a higher requirement for the operation speed of the algorithm. In this way, todevelop high efficiency algorithm becomes the bottleneck in the study of PairwiseAlignment.Needleman-Wunsch algorithm is the primary algorithm in Pairwise Alignment, ithas two steps: firstly, getting distance matrix by dynamic programming, secondly,getting optimal alignment by backtracking which based on distance matrix.Theoretically, getting distance matrix takes most time in Needleman-Wunsch algorithm.For this problem, this paper has parallel optimized Needleman-Wunsch algorithm,based on Multi-Core Architecture. Its basic thought is to use pipelining theory andmultithreading to calculate distance matrix by row. In order to decrease the cost inthread interact, blocking technology is used in this paper to calculate distance matrix.The experimental results of sequence alignment on the real DNA sequence hasshown that the parallel algorithm on Needleman-Wunsch algorithm takes less time andgets high speedup factor.