一、说明

        如果存在这样的语句：

• 武松攥紧拳头，朝老虎的眼睛打去。
• 武松朝老虎打去”；

        以上两句话，虽长度不同，其意思是高度相似的。如果按照字符串匹配，将无法说明两个句子意思一样。那么字符串如何匹配才能说明它们是一样的？ Needleman-Wunsch 算法就是解决类似问题的一种。

        Needleman-Wunsch 算法是一种在生物信息学中用于比对蛋白质或核苷酸序列的算法。它是动态规划比较生物序列的首选应用之一。该算法由 Saul B. Needleman 和 Christian D. Wunsch 开发，并于 1970 年发表。该算法本质上将一个大问题（例如整个序列）划分为一系列较小的问题，并使用小问题的解来找到较大问题的最优解。 

        Needleman-Wunsch 算法有时也被称为最优匹配算法或全局对齐技术。 Needleman-Wunsch 算法仍然广泛用于优化全局对齐，特别是当全局对齐的质量至关重要时。该算法为每个可能的对齐分配一个分数，并找到所有可能的具有最高分数的对齐形式。

        生物DNA匹配，必须遵守的规则是：从第一个序列的索引到另一个序列的索引的映射必须是单调递增的，反之亦然，即如果  是来自第一个序列的索引，那么不允许有另一个序列中的两个索引 ，使得索引 与索引 匹配， 索引 与索引 匹配，反之亦然。

二、最大子串匹配算法

2.1最大子串匹配

例如，字符串A=kitten，字符串B=sitting ,那他们的最长公共子串为ittn ，最长公共子串长度为4。（注：最长公共子串不需要连续出现，但一定是出现的顺序一致）.

2.2 字符串和LSC

表示A是由这N个字符组成，;

，表示B是由这M个字符组成，.

2.3 LSC定义

定义1：LCS(A,B)表示字符串A和字符串B的最长公共子串的长度。

很显然， 表示两个字符串没有公共部分。

定义2：其中.

对于有公式:

若，则
若，则
 

2.4 递推原理

        对于任意两个字符串。这里使用两个小 DNA 序列作为示例，如图 1 所示，如两段DNA片段:

                       和            
       如何求它们的最大相似度？

三、运算步骤

3.1 第一步，建立结构表格

        首先建立如图一的得分矩阵。从第一列第一行的位置起始。计算过程从d 【0 , 0】开始，可以是按行计算，每行从左到右，也可以是按列计算，每列从上到下。当然，任何计算过程，只要满足在计算d【 i , j】时d【 i-1 , j】、d 【i-1 , j-1】和d【 i, j-1】都已经被计算这个条件即可。在计算d【 i , j】后，需要保存d 【i , j】是从d【 i-1 , j】、d【 i-1 , j-1】或d【i, j-1】中的哪一个推进的，或保存计算的路径，以便于后续处理。上述计算过程到d 【m , n】结束。

1） 选择得分体系

        接下来我们需要决定如何给每个独立配对打分。从我们的序列中，你可能就能发现最好的序列配对之一：

GCATG-CU
G-ATTACA

我们可以看出每个位置配对都有三种可能情况：匹配， 不匹配与错位（或插入）：

• 匹配： 两个字母相同
• 不匹配：两个字母不相同
• 空缺位：一个字母与另一个序列中的间隔（空白）相匹配

        

2）初始化表格

        这三种得分情况有很多打分标准，从现在开始，我们将使用Needleman 和Wunsch创造的简单体系来进行打分，即匹配得1分，不匹配得-1分，空缺位得-1分。

        1）从第二行第二列的零开始。

        2）逐行移动单元格，计算每个单元格的分数。

        3）通过比较与单元格左侧、顶部或左上角（对角线）相邻的单元格的分数并添加匹配、不匹配或插入缺失的适当分数来计算分数。计算三种可能性中每一种的候选分数：

• 来自顶部或左侧单元格的路径代表一个 indel 配对，因此获取左侧和顶部单元格的分数，并将 indel 的分数添加到每个单元格中。
• 对角线路径表示匹配/不匹配，因此取左上角对角线单元格的分数，如果行和列中的相应碱基（字母）匹配，则添加匹配分数，如果不匹配，则添加不匹配分数。

        单元格的结果分数是三个候选分数中最高的。 鉴于第二行没有“顶部”或“左上”单元格，只有左侧的现有单元格可用于计算每个单元格的分数。因此，每次向右移动都会添加 -1，因为这表示对前一个分数的插入删除。这导致第一行是 0、-1、-2、-3、-4、-5、-6、-7。这同样适用于第一列，因为只能使用每个单元格上方的现有分数。因此结果表是：

	-	G	C	A	T	G	C	G
-	0	-1	-2	-3	-4	-5	-6	-7
G	-1
A	-2
T	-3
T	-4
A	-5
C	-6
A	-7

3.2 第二步，如何逐行填表

从第三行开始，进行实质匹配。第一项是行为G，列为G。

其中X如何填写？该单元格具有三个可能的候选总和：

• 对角线左上角的邻居得分为 0。G 和 G 的配对是匹配的，所以添加匹配的分数：0+1 = 1
• 顶部邻居的得分为 -1，从那里移动代表一个插入缺失，因此添加插入缺失的得分：(-1) + (-1) = (-2)
• 左邻居的得分也为 -1，代表一个插入缺失，也产生 (-2)。

最高的候选人是 1 并被输入到单元格中：

因此出现一个公式：

 是最后分数；

是当前两个字母是否匹配；

是当前cell的左侧分数，上部分数，左上部分数；

在下一个示例中，X 和 Y 的对角线步长表示不匹配：

X填写规则:

• Top: (−2)+(−1) = (−3)
• Left: (+1)+(−1) = (0)
• Top-Left: (−1)+(−1) = (−2)

最后取最大值：X = 0

Y填写规则:

• Top: (1)+(−1) = (0)
• Left: (−2)+(−1) = (−3)
• Top-Left: (−1)+(−1) = (−2)

 最后取最大值：Y = 0

接着按上面同样规律，填写另一个：

最后，填写的评分矩阵如下：

四、匹配链：追踪箭头回到原点

        按照箭头的方向标记从右下角的单元格返回到左上角的单元格的路径。从这条路径开始，序列由以下规则构成：

        对角箭头表示匹配或不匹配，因此列的字母和原始单元格的行的字母将对齐。
水平或垂直箭头表示插入缺失。垂直箭头将间隙（“-”）与行的字母（“side”序列）对齐，水平箭头将间隙与列的字母（“top”序列）对齐。
        如果有多个箭头可供选择，它们代表路线的一个分支。如果两个或多个分支都属于从右下角到左上角单元格的路径，则它们是同样可行的对齐。在这种情况下，请注意将路径作为单独的对齐候选。
        按照这些规则，图 1 中一种可能的对齐候选的步骤是：

G → CG → GCG → -GCG → T-GCG → AT-GCG → CAT-GCG → GCAT-GCG A → CA → ACA → TACA → TTACA → ATTACA → -ATTACA → G-ATTACA ↓(branch) → TGCG → ...→ TACA → ...

匹配分数：将匹配路径的所有分数累加，得到分数为6.

 

总结

以上是生活随笔为你收集整理的语音识别：时间序列的匹配算法（Needleman-Wunsch 算法）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。