基于动态规划的Needleman-Wunsch双序列比对算法的分析与研究

摘要

生物序列比对是生物信息学中最基础的研究课题之一.基于动态规划的Needleman-Wunsch双序列比对算法主要采用迭代算法及空位罚分规则对基因序列进行逐一比对,计算二者相似性得分,最后通过回溯分析得出序列之间的最佳比对.虽然该算法可以得到最佳比对结果,但是时间复杂度和空间复杂度较高.首先对原算法进行分析,对计算得分和回溯进行改进.接着设计2次实验,以金黄色葡萄球菌和银葡萄球菌分别作为目标序列和待比对序列,分别生成序列长度范围相同和不同的5组数据进行实验测试.最后通过对新型冠状病毒和S A RS病毒全序列进行比对,进一步验证了改进算法的有效性.实验结果表明,改进后的算法可以缩短序列比对时间,提高序列比对效率.