Reaseach On Pairwise Sequence Alignment Needleman-Wunsch Algorithm

With the implementation of the human genome project(HGP),the relevant data of biology is growing rapidly,but how to deal with these large amounts of data has become a difficult problem for biological scientists.At present,the comparison and analysis of gene sequences have become one of the main research contents in biological information processing.In the pairwise sequence alignment algorithm,Needleman-Wunsch algorithm based on dynamic programming is the most basic algorithm.Although this algorithm can obtain the optimal result of the pairwise sequence alignment,it has high time complexity and high space complexity,all of which are O(n*m)(n and m respectively represent two sequences length).Therefore,it is difficult to achieve the actual biological sequence alignment.In this thesis,the author mainly analyzes the Needleman-Wunsch algorithm based on the idea of dynamic programming,and puts forward an improved algorithm of Needleman-Wunsch algorithm.Through a large number of experiments,the run time of the improved Needleman-Wunsch algorithm and the original Needleman-Wunsch algorithm is compared.The experimental results show that the improved algorithm of Needleman-Wunsch can effectively reduce the running time of the original Needleman-Wunsch algorithm when the total score and accuracy of sequence alignment are invariant.In this thesis,the research content and the main work are as follows:(1)To understand the research status quo of pairwise sequence alignment.At the same time,The author studies the results of the Needleman-Wunsch algorithm for pairwise sequence alignment,and analyzes the possible problems of the algorithm.(2)The biggest problem of Needleman-Wunsch algorithm for pairwise sequence alignment is that there is a very high time complexity and space complexity.In this thesis,the author proposes an improved algorithm for the running time of Needleman-Wunsch algorithm in the case of the same space complexity.That is,when filling the cost matrix,if the corresponding base is the same,do not have to compute the values in three directions,then ask for their maximum values,but assign the values in the diagonal direction to the current values,to solve the current value.To a certain extent,the running time is reduced,and the operation efficiency is improved.(3)Looking for the biological gene sequence from the NCBI database and doing a lot of experiments,so as to analyze the sequence alignment results of the improved Needleman-Wunsch algorithm.The experimental results verify that the improved Needleman-Wunsch algorithm is superior to the original Needleman-Wunsch algorithm in time.