关键词: 序列比对, 动态规划, 相似性

Abstract: Sequence alignment is one of the most fundamental research problems in bioinformatics. The pairwise alignment Needleman-Wunsch based on dynamic programming mainly uses the iterative algorithm and the vacancy penalty rule to compare gene sequences one by one, calculates their similarity score, and finally obtains the best alignment between sequences through backtracking analysis. Although the algorithm can get the best result, it has high time and space complexity. Firstly, the original algorithm is analyzed and improved from the aspects of calculation score and backtracking. Secondly, two experiments are designed. In the experiments, Staphylococcus aureus is used as the target sequence, and Staphylococcus aureus is used as the counterpart sequence. Five groups of experiments with the same and different sequence length range are conducted. Finally, the novel coronavirus and SARS virus sequences are compared to verify the effectiveness of the algorithm. The experimental results show that the improved algorithm can reduce the sequence alignment time and improve the efficiency of sequence alignment.

Key words: sequence alignment, dynamic programming, identity