生物序列局部联配中的马赛克问题的一种解决方法

摘要：

生物信息学中,对各种生物大分子序列进行分析是一件非常基本的工作,Smith Waterman算法是目前最重要的一种局部联配算法,该算法先用迭代方法计算出两个序列的所有可能相似性比较的分值,然后通过动态规划的方法回溯寻找最优相似性比较.但将此算法用于同源长序列的局部联配时,经常会出现马赛克问题(相似度很低的保守区域夹在两个相似度很高的区域中间).在分析问题成因的基础上,提出利用动态加速扣分策略解决马赛克问题,即在计算得分矩阵的过程中,如果存在保守区域,则加大扣分的力度,争取在离开保守区域前让得分为0,从而将保守区域切断.实验结果表明,动态加速扣分策略顺利解决了序列局部联配中的马赛克问题,并且没有显著增加算法的时间复杂度和空间复杂度.

关键词： 生物序列联配 Smith Waterman算法 马赛克问题 动态加速扣分策略 生物信息学

作者: 黄均才 佘堃 周明天

作者单位: 电子科技大学,计算机学院,电子科技大学-卫士通联合实验室(成都);华东交通大学,经管学院(南昌) 电子科技大学,计算机学院,电子科技大学-卫士通联合实验室(成都)

会议类型: 国内会议

会议名称: 2003中国计算机大会

会议地点: 北京

会议语种:中文

页码: 811-815

在线出版日期: 2003-11-01（万方平台首次上网日期，不代表论文的发表时间）