在分子生物学和基因组分析中,蛋白质序列和DNA序列的比对是一种重要的分析工具.多序列比对问题是NP完全问题,这就是说,任何研究快而完全算法的企图都将面临极大困难.求解多序列比对问题可以看成是在一个有向无环图中寻找两点间的最短路径,求解此类问题众所周知的方法是动态规划方法,但是使用动态规划方法得到最优比对需要消耗大量的时间和空间,对于规模较大的情形,原封不动地照搬动态规划方法求解从现实角度是不可能的. 首先,提出了一种称之为基于竞争策略的快速多序列比对近似算法,多序列比对算法分为同时比对算法和非同时比对算法,该算法为一同时比对算法.使用该算法对基因库Balibase2.01中的序列簇进行了测试,并将实验结果与著名的同时比对算法MSA进行了比较,实验结果表明该算法是一种十分高效的同时比对算法. 其次,在基于竞争策略的多序列比对算法的基础上采用分治策略对比对结果进行了进一步的处理,也就是进行优化.采用了一定的方法将原问题转化成了几个子问题,然后对每个子问题采用原算法进行求解,最后将各个子问题的结果组合起来作为原问题的解.同样采用此戊化方法对Ballbase2.01中的序列簇进行了测试,并将优化后的结果与原结果进行了对比,实验结果表明这种优化是有效的.