生物信息学是用计算机来处理和研究生物信息的一门新兴学科,其中,序列相似性比较是生物信息处理中最基本的一个问题。如何获得结果更准确,时间空间效率更高的序列相似性比较算法是生物信息学研究工作者的一个重要的课题。生物序列相似性比较算法在生物信息学中占有重要的地位。论文首先讨论了最早提出的,也是最基本的生物序列相似性比较算法——两序列全局相似性比较动态规划算法;然后,通过对生物序列的演化模型进行讨论,推导出生物序列演化关系计算和序列相似性比较计算的一致性;最后我们根据三条线索叙述序列相似性比较算法领域从七十年代到现在的发展过程以及最新的研究成果。接着论文讨论了动态规划序列相似性比较算法的各种优化研究。在实际应用中,动态规划算法的空间复杂度是限制问题规模的瓶颈。论文提出一种新的序列联配算法FastAlignment(FA),FA算法的时间复杂度和空间复杂度介于基本动态规划算法和Hirschberg算法之间,通过对算法参数k的调节,可以在不同存储条件下以最小时间开销解决序列联配问题。论文也讨论了动态规划算法的可并行性,研究了两种在SMP计算机上实现的动态规划并行方法,分析了在SMP机群系统中,如何通过分割数据的方法实现机群系统上算法的并行优化。基于动态规划的序列联配算法需要一种非交叉的属性,而子序列发生重排和倒置的序列相似性比较正好具有交叉属性。论文具体讨论了序列重排和倒置问题,提出了一种序列相似性比较的新算法,该算法克服了动态规划算法的非交叉属性。论文中分析了新算法的时间和空间需求,提出了对新算法进行并行优化的方法。论文的最后讨论了两个与序列相似性比较算法相关的工具程序——PHRAP程序和BLAST程序,其中PHRAP程序用于对DNA测序过程中产生的子序列片断进行拼接,BLAST程序用于在生物序列数据库中进行序列相似性检索。我们给出了这两个程序进行并行化的一些方法以及实现。