做局域网网站教程hao爱做网站

做局域网网站教程,hao爱做网站,外链工具下载,wap免费建站程序序列对齐序列对齐问题是一个经常用到的问题。大部分的拼写工具都会进行拼写校验来纠正拼写错误#xff0c;例如图中工具将错误单词#xff08;呈现为 “O-CURRANCE”#xff09;与正确单词 “OCCURRENCE” 进行对齐#xff0c;其中竖线 “|” 代表对应位置的字符完全匹配。…序列对齐序列对齐问题是一个经常用到的问题。大部分的拼写工具都会进行拼写校验来纠正拼写错误例如图中工具将错误单词呈现为 “O-CURRANCE”与正确单词 “OCCURRENCE” 进行对齐其中竖线 “|” 代表对应位置的字符完全匹配。该对齐结果表明错误单词 “OCURRANCE” 与正确单词 “OCCURRENCE” 高度相似 —— 错误单词是通过插入、删除、字符突变等操作从正确单词生成的即拼写工具据此识别错误并提供纠正建议。错误类型对齐的核心用途序列对齐是用来描述 “错误单词从正确单词生成” 的过程这个过程会用到 4 种操作插入Insertion、删除Deletion、匹配Match、突变Mutation。对齐的实现方式统一序列长度为了用上述操作描述生成过程需要让 “错误序列记为 S” 和 “正确序列记为 T” 长度一致 —— 通过在合适位置添加空格 “-”将 S 改写为 S、T 改写为 T使得 |S| |T|长度相同。示例S 是 “O-CURR-ANCE”T 是 “OCCURRE-NCE”空格 “-” 让两者长度统一中间竖线代表对齐关系。空格 “-” 的含义生成过程的解释对齐后通过 S 和 T 中 “空格的位置”可以解释 S 从 T 生成的过程若 \(S[i] -\)代表 T 的第 i 位被删除了若 \(T[i] -\)代表 S 的第 i 位是插入的字母其他情况S 的第 i 位是 T 第 i 位的复制可能带有突变。得分计算某个正确序列可能会有多个不同的错误序列因此我们需要一种计算方法来衡量不同错误序列的偏差程度。得分的计算方式每个生成过程的可能性用线性函数计算总得分总得分 (s(T, S)是 “每个对齐位置 i 的得分 s(T[i], S[i]) 的总和从 i1 到 S 的长度公式为单位置的得分规则简单设定对 s(a,b)a 是 T 的位b 是 S 的位的得分规则做了简化定义匹配Matcha 和 b 相同得 1比如 s(C,C)1突变Mutationa 和 b 不同得 - 1比如 s(E,A)-1插入 / 删除Insertion/Deletion其中一个是空格 “-”得 - 3比如 s(C,-)-3。我们可以看到该计分方式下对缺少或者添加字母的惩罚是远高于写错的。下面看几个例子候选词 1OCCURRENCE对齐处理将错误词处理为 SO-CURRANCE、正确词处理为 TOCCURRENCE通过空格统一长度并对齐得分计算依据 “匹配 1、突变 - 1、插入 / 删除 - 3” 的规则计算对齐得分s(T,S) 1 - 3 1111 - 1 111 4候选词 2OCCUPATION对齐处理将错误词处理为 SOC-URRA---NCE、正确词处理为 TOCCU-PATION--通过空格统一长度并对齐得分计算同样按规则对齐得分s(T,S) 11 - 3 1 - 3 - 1 1 - 3 - 3 - 3 1 - 3 - 3 -14从上面的例子我们也可以发现一个情况不同的对齐方式也会对序列的得分有所影响由此通过序列对齐可判断 “OCCURRENCE” 转化为错误拼写 “OCURRANCE” 的最可能操作组合插入 / 删除 / 突变。下面再看几个例子对齐 1对齐形式错误词处理为 SO-CURRANCE正确词处理为 TOCCURRENCE得分计算s(T,S) 1 - 3 1111 - 1 111 4。对齐 2对齐形式错误词处理为 SO-CURR-ANCE正确词处理为 TOCCURRE-NCE得分计算s(T,S) 1 - 3 1111 - 3 - 3 111 -1。由于对齐 1 的得分4远高于对齐 2-1因此对齐 1 对应的操作是 “OCCURRENCE” 生成 “OCURRANCE” 的真实过程。由此我们可以判断出该拼写的错误类型即“删除”。问题概述INPUT给定两个序列 T 和 S其中 T 的长度为 m记为 |T|mS 的长度为 n记为 |S|n。OUTPUT找到 T 与 S 的一个对齐方式使得预先定义的得分函数取值最大化。序列的元素采用下标索引即T_1 为 T 的第 1 个元素T_m 为最后 1 个元素。寻找最优子结构通过在序列中插入空格 “-” 表示 “S 从 T 生成” 的过程将求解对齐的过程转化为多阶段决策过程每个决策阶段需选择 3 种操作之一匹配 / 突变Match/Mutation让 T 的第 i 位(T_i与 S 的第 j 位S_j对齐插入Insertion让 S 的第 j 位S_j与空格 “-” 对齐删除Deletion让 T 的第 i 位T_i与空格 “-” 对齐。以 “OCURRANCE”S和 “OCCURRENCE”T为例展示三种操作对应的对齐形式匹配 / 突变S 与 T 的对应字符直接对齐插入S 的字符与 T 的 “-” 对齐删除S 的 “-” 与 T 的字符对齐。从这个例子我们可以看出对于两个序列的对齐问题最后一个元素要么是匹配 / 突变、要么是插入、要么是删除。我们可以以此来将其分解成三个子问题场景 1匹配 / 突变S_n来自T_mT 的最后一位→ 子问题对齐 T 的前缀T[1..m-1]与 S 的前缀S[1..n-1]场景 2插入S_n是插入操作→ 子问题对齐 T 的完整序列T[1..m]与 S 的前缀S[1..n-1]场景 3删除S_n来自 T 的前缀T[1..m-1]→ 子问题对齐 T 的前缀T[1..m-1]与 S 的完整序列S[1..n]。子问题的通用定义将子问题抽象为 “对齐 T 的前缀T[1..i]与 S 的前缀S[1..j]”并将该子问题的 最优得分即最大化得分函数的结果记为OPT(i,j)。最优子结构性质递归公式原问题的最优解可由子问题的最优解推导因此OPT(i,j)是以下三种情况的最大值对应三种操作的得分 子问题得分其中s(a,b)是之前定义的 “单位置得分函数”匹配 1、突变 - 1、插入 / 删除 - 3。算法由此我们就可以写出这个问题的算法这里我解释一下初始化的部分计算 OPT[i,0] -3 × i表示 “T 的前缀T[1..i]与空序列对齐”空序列等价于全空格因此 T 的每个元素对应删除操作得分 - 3i 个元素的总得分是 -3i。同样的计算 OPT[0,j] -3 × j表示 “S 的前缀S[1..j]与空序列对齐”S 的每个元素对应插入操作得分 - 3j 个元素的总得分是 -3j。下面看一下OPT表的更新过程首先是初始化该图说明了为什么要引入第一行/列其实就是为了最后能有一个递归出口。下面我们详细说明一下该表如何更新重述一遍OPT(i,j)表示“T 的前 i 个字符” 与 “Y 的前 j 个字符” 对齐的最优得分。因此红圈就表示OPT(OC, OCUR)。计算公式为操作 1匹配 / 突变T 的第 i 个字符与 S 的第 j 个字符对齐逻辑T 的第 i 个字符此处 T 的第 2 个字符是C与 S 的第 j 个字符此处 S 的第 4 个字符是R对齐得分由 “子问题OPT(i-1,j-1)的得分 该位置的匹配 / 突变得分” 决定。计算子问题OPT(i-1,j-1)OPT(1,3)T 的前 1 个字符O与 S 的前 3 个字符OCU对齐的得分对应矩阵 “第 1 行、第 3 列” 的单元格得分是-5匹配 / 突变得分C与R不匹配属于突变得分-1操作 1 的总得分-5 (-1) -6。操作 2删除T 的第 i 个字符与空格对齐逻辑T 的第 i 个字符C被删除得分由 “子问题OPT(i-1,j)的得分 删除操作得分-3” 决定。计算子问题OPT(i-1,j)OPT(1,4)T 的前 1 个字符O与 S 的前 4 个字符OCUR对齐的得分对应矩阵 “第 1 行、第 4 列” 的单元格得分是-8操作 2 的总得分-8 (-3) -11。操作 3插入S 的第 j 个字符与空格对齐逻辑S 的第 j 个字符R是插入的得分由 “子问题OPT(i,j-1)的得分 插入操作得分-3” 决定。计算子问题OPT(i,j-1)OPT(2,3)T 的前 2 个字符OC与 S 的前 3 个字符OCU对齐的得分对应矩阵 “第 2 行、第 3 列” 的单元格得分是-1操作 3 的总得分-1 (-3) -4。取 3 种操作得分的最大值max(-6, -11, -4) -4这就是OPT(2,4)即OPT(OC, OCUR)的得分对应矩阵中 “第 2 行、第 4 列” 的单元格值。最终对齐形式S O-CURRANCE、T OCCURRENCE验证了 “该错误序列与正确序列的最优对齐得分是 4”即对应最可能的生成过程。回溯我们可以从OPT表中通过反向遍历来得到最优对齐形式以 “TOCCURRENCE、SOCURRANCE” 的得分矩阵为例从最终得分单元格红色圈出的 “4”对应 OPT(m,n)开始沿红色圈出的路径反向遍历OPT表每一步回溯对应一种对齐操作匹配 / 插入 / 删除最终得到具体对齐结果S O-CURRANCE、T OCCURRENCE即之前拼写纠错的最优对齐形式。