文 献 综 述 1、 研究背景： 生物序列一般指DNA、RNA序列或蛋白质序列，对它们的研究是近代生命科学中研究中的一个关键而又基本的问题，大量生命现象的奥秘蕴含在其中。

对生物序列进行比对，可以在核酸、氨基酸的层次上对生物序列的相似性进行分析，从而推测比对中的各个序列间结构功能以及进化上的联系。

通过对各种不同类型的生物序列进行比对，可以寻找与确定比对序列的稳定区域与变化规则，发现它们的功能特征和区别，还可以检测新序列与数据库中已知序列的相似性关系（结构和功能），从而为确定新序列的结构和功能信息提供事实根据。

由上可说明，序列比对是计算序列相似性的最常用的方法，而且是基因识别、分子进化、生命起源等研究的基础，对序列相似性的研究于基因结构和功能的研究具有较大的实际意义。

2、 国内外研究现状： 生物序列相似性研究的基础是双序列比对算法[1]，或者说关于生物序列相似性算法的研究是从两条序列相似性比对算法的研究开始的。

Mclntyre和Gibbs首先提出点阵图法，它是一种可视化的双序列相似性比对方法。

然而，随着序列长度和序列的数量增加，序列相似性比对计算复杂度也随之增加，点阵图法[2]已经不够满足了。

Needleman和Wunsch首次使用动态规划方法进行两条序列相似性比对，该算法叫做Needleman-Wunsch算法[3]。

Needleman-Wunsch算法主要用于两条序列相似性比对，其时间复杂度和空间复杂度均是O（mn）。

Hirschberg提出了一种的改进的动态规划序列相似性比对算法-Hirschberg算法[4]，与Needleman-Wunsch算法相比，算法的空间复杂度降低到O（m n），但是其时间复杂度却没有降低仍然是O（mn）。