The focus of Bioinformatics research is usually on two aspects—genomics and proteomics, specifically, it’s starting from nucleic acid and protein sequences, analyzing the structural and functional biological information expressed in the sequences. Biological sequence alignment is one of the common problems, the Needleman-Wunsch algorithm based on dynamic programming is the most basic algorithm, and Edit Distance(Levenshtein Distance) algorithm is also widely used in DNA sequence alignment. Nowadays, there are large amount of improvements on the Needleman-Wunsch algorithm, while few on Edit Distance algorithm, so this paper focuses on revealing the effects of parallel design on optimizing the Edit Distance algorithm, and it also compares the two algorithms’ different significances in DNA sequence alignment objectively.

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.

Proteins are amino acid chains that acquire their biological and biochemical properties by folding into unique 3-dimensional structures. The biological function of a protein is dependent on the protein folding into the correct, or "native", state. At present, there are so many ideas to predict the structure of the protein folding. This paper first present the concept of protein folding and how is significant to study protein fold prediction. In this paper we join the simulated annealing factor into Parallel Genetic Algorithm and use this hybrid Parallel GA to predict the structure of protein fold. The revised algorithm is more efficient than traditional Genetic Algorithm and simulated annealing algorithm.