序列比对是现代生物信息学中一个最基本的研究课题。通过多序列比对,可以预测新序列的结构和功能,分析序列之间的同源关系,以及进行系统发育分析。本文首先介绍了序列比对涉及的基本问题:空位罚分,替换矩阵和比对结果评价标准。接着,主要介绍了两种序列比对算法:A*算法和斜线比对算法求多序列比对。理论上Needleman–Wunsch算法可以很容易地应用于多条序列中产生分值最优的比对,但是随着序列条数的增长,算法的复杂性成指数增长,而且算法不能扩展到多于三条序列。而A*算法利用合理的启发式函数限制多序列比对的搜索空间。用这种方法,即使是八条序列,每条序列含有几百氨基酸残基也可以同时比对。首先,该算法将多序列比对问题转化为求最短路径问题,利用A*算法可以在找到最短路径的同时有效地降低时间复杂度。本文将A*算法应用于多序列比对,选择有效的预测函数和边界值,最大限度的缩小搜索空间。并且从程序性能和算法性能上努力做出改进:找更接近的边界值;利用哈希链表代替简单链表提高程序的节点查找时间。最后,讨论了算法在测试例子中的应用,并且与经常使用的比对方法产生的结果比较。实验结果表明:设置边界值(BOUND)和利用哈稀链表代替简单链表后,程序的执行速度比未改进之前提高了好几倍。理论上讲,只要选择合适的目标函数和打分矩阵,计算出的结果应该是非常理想的;然而,实际情况与理想值之间还有较大的差距,还有待于预测函数以及目标函数进一步的改进。但是该算法的潜能是非常大的,一旦打分矩阵和目标函数的设定方面获得突破,其前景将不可限量。在本文中,接着介绍了另一个不同的序列比对的方法,即斜线比对算法。不同于比较单个的残基,它使用免空格段段比对算法比较随机长度的序列片段。特别地,该算法不使用任何空格罚分。通过定义关于斜线位置的集合,它把比对看成一个一致的等价关系。在寻找斜线段阶段,尝试使用新的方法。即先将两条序列比对,然后只在两两最优比对部分查找。在对算法的总体性能影响不太大的情况下,有效地提高了程序的执行速度。实验表明:该算法是一种有效的局部多序列比对算法,非常适合产生生物信息学上的有某种特定意义的比对。