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

【Abstract】 The Smith Waterman algorithm for local sequence alignment is one of the most well-known algorithm in computational molecular biology.However,the alignment sometimes produces a mosaic of well conserved fragments artificially connected by poorly conserved or even unrelated fragments.This may lead to problems in comparison of long genomic sequences and comparative gene prediction.In this paper we propose a new strategy of dynamic accelerated penalty to fix this problem.In the process of computing similarity matrix,if similarity value is larger than the pre-specified threshold X then starting our strategy,when related character mismatches,then penalizing more than others until similarity value is 0 or the process ends.Test results show that this algorithm has better performance by comparison to the standard Smith Waterman while dose not increase signally the computational complexity both in time and space.更多还原