系列的变异可以变换为另一条序列，那么这两条序列之间的距离为这些变异的加权值之和的最小值。
相似度（similarity）给定两条序列，对应位置的相似之处赋予一定的分值（或权值），那么这两个序列的
相似度为这些权值之和的最大值。
编辑距离（Edit Distance）两条序列之间的编辑距离是一条序列经过一系列的编辑操作（插入、删除和替 换）转变为另一条序列所需要的操作的最小次数。相对应于每一个操作赋予一个分值（或权值），通常插入和 删除（indel）的分值是相同的，利用联配的算法，求出最小分值（或最大的负分值），即为这两条序列之间 的编辑距离。由于在进化过程中，绝大部分的变化是由上述三种局部变异造成的，因此编辑距离能够粗略地 用来测定两个序列之间发生变异的次数。
方法。例如可以这样定义记分函数：σ (x, x) = +2, σ (x, y) = σ (x,−) = σ (−, y) = −1。 定义 2：给定两条序列S= s1…sn和T=t1…tm。那么我们用|S|来表示S的长度，S[i]表示序列S的第i个字符。
如果序列S和T相同，则必须满足： （1） | S | = | T |； （2） S[i] = T[i]，(0＜i≤| S | )； 定义 3：如果S和T是两个序列，那么S和T的全局联配（alignment）A可以用序列S’和T’来表示，其中： （1） | S’ | = | T’ |； （2） 将S’和T’中的空字符除去后所得到的序列分别为S和T，（例S = “a c b c d b”，T = “c a d b d”，那么
Smith_Waterman算法主要有两部分组成[13]：⑴、计算所给定的两个序列整个的相似分值，并得到一个相 似度矩阵（similarity matrix），也称做动态规划矩阵或得分矩阵；⑵根据相似度矩阵，按照动态规划的方法回 溯寻找最优的联配。
引入的动态规划思想是：如果一条路径终止于最佳路径上的一点，那么这条路径本身就是起点到这个中 间点的最佳路径，也就是说任何一个终止于最佳路径上的一点的次级路径必然就是终止于这一点的最佳路径 本身[9]。这样最佳路径就可以通过把各个最佳的次级路径连接起来而得到。在基本的Needleman-Wunsch算法 表达中，最佳联配必然对每个序列都有始至终的，即从搜索空间的左上角直至右下角，也就是说它搜索全局 的联配。
生物序列相似性的比较
张法
本文主要介绍了两条序列相似性的比较问题。我们首先从该问题的生物学动机入手，说明解决这一问题的实际应用意义， 然后给出该问题的定义以及问题的分类。从第二节开始分别介绍和分析全局联配问题、局部联配问题、End space-free alignment 问题和空位处罚的算法。通过以上这些内容的介绍，揭示该问题（两条序列的相似性比较）算法的核心内容是 动态规划（Dynamic Programming）。 实际上动态规划是生物信息学中一个最流行的编程方法[1]。序列的比较、基因的识别、蛋白质序列重排以及蛋白质结构和 功能的分析等等诸多生物信息学中的问题都可以通过动态规划的方法解决[2][3][4]。 关于两条序列相似性的比较问题，在最近的研究中，Abdullah N. Arslan等[5]在动态规划算法的基础上提出了一种新的方 法，解决了在序列局部联配的最优排列中经常出现的马赛克问题（在最优排列中间经常出现的相似度很低的保守区域）； Jeremy Buhler[6]把hash表方法引入到基因组序列的局部联配问题中，同时提高了原有算法的效率和质量；David Sankoff[1] 和Robert Giegerich[2]对生物信息学中的动态规划思想进行了系统的分析和总结。由此可见动态规划方法仍然是生物序列 分析的一种有效的工具。
但是它们有一定的相似性。那么如何判断这两条序列之间的相似性呢？
定义 1：如果 x 和 y 是两个任意的字符，那么σ (x, y) 表示字符 x 和 y 在进行比较时所得的分值，称为一
个记分函数。记分函数包括了当 x 为空字符或 y 为空字符的情况，在序列中一个所谓的空字符表示序列在此 位置可能缺失了一个字符，我们用“—”来表示这种缺失。在不同的算法当中，记分函数可以有不同的记分
原始的算法：
输入：两个序列 S 和 T，其中 | S | = | T | = n; 输出：S 和 T 的最优联配
Begin
for i = 0 to n do for (序列 S 的所有的子序列 A，其中| A | = i ) do for (序列 T 的所有的子序列 B，其中| B | = i ) do
定义 4：对于两个序列 S 和 T，它们的全局最优联配 A 是指在 S 和 T 的所有相似性比较中最高分值 Score 所对应的联配。
序列联配算法的主要目标是如何寻找出序列间的最优相似性的比较。那么我们如何找到两个序列 S 和 T 的全局最优联配呢？
2.1 全局最优联配原始算法
假设给定两个序列 ACGC 和 ACT，两者之间的联配可能为：
1.2 概念和问题的定义
1.2.1 常用的一些概念 如果从两个不同的生物体中提取出来的两条相似的 DNA 序列，在生物学中可以理解为它们来自于同一 个祖先的 DNA。根据这一原理，并且考虑到在进化过程中发生变异的可能性，同一家族在同一时代的种 类之间会出现差异。这些差异可以分为以下三种情况：
¾ 插入（Insertion）在序列中插入一个或多个字符 ¾ 删除（Deletion）从序列中删除一个或多个字符 ¾ 替换（Substitution）用一个序列替换另一个序列
1目前关于“alignment” 一词有“联配”、“比对”、“对比”、“对排”、“阵排列”等好几种译法，本文采用“联配”这种译法。
输入：给定两条具有相同长度的序列 S 和 T 输出：两条序列之间的最大相似度（差异），并找出最佳的排列。 问题 2：局部排列（Local Alignment）条 输入：两条序列 S 和 T（两者的长度可能不同） 输出：S 的一条子序列和 T 的一条子序列的最大相似度（最小差异），并找出具有最大相似度的
1 生物学的动机和问题的定义
1.1Байду номын сангаас动机
在生物学的研究中，有一种常用的方法，就是通过比较分析获取有用的信息和知识。分子生物学家已经 认识到，将未知序列同已知序列进行比较分析是一个强有力的研究手段。生物学领域中绝大部分的问题
在计算机科学领域中主要体现为序列或字符串的问题[7-9]，例如： ⑴、 通过一些序列片段的重叠来重新构造一条 DNA 的长序列 ⑵、 通过大量试验获得的验证数据来确定其物理和遗传的映射图 ⑶、 DNA 序列的排序（Sorting）、恢复（Retrieving）和比较（Comparing） ⑷、 比较两条或多条 DNA 序列的相似性 ⑸、 在数据库中搜索相应的序列或子序列 ⑹、 找出蛋白质序列或 DNA 序列中信息学方面的因素 ⑺、 测定出经常出现的核苷的模型（或模式） 上述的许多问题都着眼于在不通过进行任何实验的前提下，了解蛋白质的功能或结构。当需要鉴别某一 基因或确定其功能时，我们可以在已知蛋白质的数据库中搜索相似的蛋白质序列，以此来确定其功能。 其所依据的原理是：相似的序列产生结构或功能相似的蛋白质。实际上，考虑到蛋白质折叠中的各种不 确定因素，如果两条蛋白质序列的相似性大于 30％，则可以认为这两条序列所表示的蛋白质具有相似的 三维结构。
两条子序列。 问题 3：End space-free alignment
输入：两条序列 S 和 T（两者的长度可能不同） 输出：从这两条序列中找到一条最优的序列，序列中的某一部分是 S 或 T 中一条序列的前缀，
而另一部分可能是另一条序列的后缀。 问题 4：空位处罚（Gap penalty）
定义：在单个序列的排列中，空位指仅仅包括空格的子序列。在序列中每引入一个空位，联配 的分值都会有所扣除。
S’ = “a c - - b c d b”， T’ = “- c a d b - d –” ）； 联配就是把序列S’和T’上下罗列起来，相应的位置进行一一的比较。联配A的分值Score可以用如下的公
式来表示：
l
∑ Score = σ (S '[i],T '[i]) 其中l = | S’ | = | T’ |; i =1
⑴
令|
S’
|
=
n，其中，
S
' [k
]
=
⎧A[k],1 ≤ k ≤ ⎩⎨−,i < k ≤ n
i
;
⑵
令|
T’
|
=
n，其中，
T
'
[k
]
=
⎧B[k],1 ≤ k ≤ ⎩⎨−,i < k ≤ n
i
;
⑶ 比较S’[ k ]和 T’[ k ]，1≤ k ≤n，得到此次联配的分值;
返回最大分值所代表的联配；
End. 算法分析 这个算法的正确性是非常明显的，但是这一算法也是非常耗时的，算法的时间复杂度为O(22n)。如果n = 20，该算法的运算次数为 240，而几乎所有的生物序列的平均长度都在 103的数量级范围内，所以这种算法毫 无实用价值。
序列的联配1（alignment）两个或多个符号序列按字母比较，尽可能确切地反映它们之间的相似或相异， 成为序列的联配。
1.2.2 问题的定义与分类 生物序列的分析对于分子生物学而言是一个十分重要的工具。近年来随着生物数据库的快速增长，对生 物数据快速准确的大规模分析变得非常的重要和迫切。生物序列分析面临许多计算任务，一些相关的讨论包 括[10][11][12]： 1. 序列相似性的比较
输入：两条长度不同的序列 S 和 T 输出：考虑到空位处罚的情况，给出这两条序列的相似度和与此相对应的排列。
２ 全局联配（Global Alignment）
在生物序列的长期演化过程中，原本相同的序列由于其中一条序列缺失（或者增加）几个片段，或某段
子序列发生了位置的变化等，从而导致它们之间产生差异，因此这两条序列不一定能够进行精确的匹配，