用动态扣分策略消除序列局部联配中的马赛克问题

1引言 生物信息学中,对各种生物大分子序列进行分析是一件非常基本的工作,Paul A.Rota[1]通过测定SARS(又名非典型性肺炎)病毒的基因组序列,找到了含有制造蛋白质指令的部分基因,其中包括公认的制造四种蛋白质的基因,证实了非典病毒是一种全新的冠状病毒,这一成果将有助于加快诊断、治疗和预防非典的步伐.

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

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