论文摘要
序列比对是现代生物信息学中一个最基本的研究课题。随着生物数据库快速持续的增长,对多序列比对算法的敏感性和运算速度提出了更高的要求,开发具有高敏感性和高效率的算法成为当今研究的重点。本文提出一个新的算法KMDMSA,它能在保持原来比对精度的前提下,降低比对的时间复杂度。本文首先介绍了序列比对涉及的基本问题:空位罚分,替换矩阵和比对结果评价标准。接着对基于渐进方法构建的多序列比对算法ClustalW进行了深入的研究。然后通过对这些算法的分析,对当前最流行的渐进比对提出了改进。MAFFT最早将分治思想应用到序列比对。它把快速傅立叶变换应用到序列比对,使得两序列比对的时间复杂度从O（L2）降低到O（LlgL）。通过把k-mer应用在序列比对中,并结合分治思想,本文提出了一个新的多序列比对方法:KMDMSA。它通过快速的识别同源区域,把比对问题分成子问题予以解决。而寻找同源片断的时间复杂度也从O（LlgL）降低到O（L）。为了降低时间和空间复杂度,该方法包含两个技术:k-mer查找和压缩字母。为了验证比对效果,把KMDMSA的性能同大多数当前流行的方法作以比较。实验结果表明KMDMSA和其他方法具有可比的精度,而时间上却有更小的开销。这也证明该方法是有效的多序列比对方法。