论文部分内容阅读
序列比对是生物信息学中一项重要的基础性研究课题，它的最基本任务之一是进行多序列比对，目前还没有一个最佳的多序列比对算法。本文提出使用遗传算法和粒子群优化算法来解决多序列比对问题。 首先分析了空位罚分、替换矩阵和目标函数对序列比对的影响，具体实现了SP和COFFEE目标函数。然后研究并实现了双序列比对的精确算法--动态规划算法，并对基于渐进方法构建的多序列比对算法-Clustal w进行了深入分析。接着通过对多序列比对算法的现状的研究以及对遗传算法和粒子群优化算法特点等的分析，提出基于遗传算法的多序列比对算法MSAGA(a Genetic Algorithm dedicated for Multiple SequenceAlignments)和基于粒子群优化算法的多序列比对算法MSAPSO(a Particle SwarmOptimization dedicated for Multiple Sequence Alignments)，并分别实现了基于SP和COFFEE目标函数的MSAGA和MSAPSO，两种算法复杂度都只与进化代数和种群大小有关。最后用基准多序列比对库BAliBASE中的用例对算法进行测试，结果表明MSAGA和MSAPSO算法在解决基因序列比对问题上是有效的。