Parallelization of Needleman-Wunsch Algorithm Based on Software Pipelining

Sequence alignment is one of the most important algorithms that analyzing massive biological information. In modern bioinformatics, it plays an important role in field of serching for similar sequences, predicting sequence information of unkown sequence, looking for specific position of sequence, predicting protein structure and so on. Needleman-Wunsch algorithm is the earliest global alignment algorithm, it gets widely application with its accuracy, however, it has a high time complexity and its speed is slower. This paper adopts software pipelining technique to optimize Needleman-Wunsch algorithm with parallelization, and OpenMP which is the industrialized standard of shared memory programming is used to parallelize it. The performance of Needlelman-Wunsch algorithm can get a great improvement with the optimization.