论文部分内容阅读
生物信息学中，Smith Waterman算法用于同源长序列的局部联配时，经常会出现马赛克问题（相似度很低的保守区域夹在两个相似度很高的区域中间）。在分析问题成因的基础上，提出利用动态加速扣分策略解决马赛克问题，即在计算得分矩阵的过程中．如果存在保守区域，则加大扣分的力度，争取在离开保守区域前让得分为0，从而将保守区域切断。实验结果表明，动态加速扣分策略顺利解决了序列局部联配中的马赛克问题，并且没有显著增加算法的时间复杂度和空间复杂度。