论文部分内容阅读
论文首先介绍了双序列比对问题的最基本方法——动态规划全局比对算法，然后学习和研究了几个双序列比对的经典算法，如线性空间的动态规划算法，仿射空隙罚分函数，FASTA启发式算法等。同时，本文还说明了这些算法的优缺点及各自适用范围。然后介绍了多序列比对算法的发展现状，分析了各个算法的优缺点；着重介绍了基于progressive比对的多序列比对算法，总结了该算法存在的局部最优问题。最后，提出了基于progressive多序列比对的优化算法。新算法改进了指导树的构造算法，修改了渐进式比对的计分函数，同时使用两个能够优化比对结果的算法对比对结果进一步提高精度，很大程度上解决的局部最优问题，并改善了多序列比对质量。本文最后给出了一个生物序列比对系统的实现。该系统的多序列比对使用了文中提出的优化算法。