algorithm - Smith-Waterman 算法路径检测说明

Question

我将 Smith-Waterman 算法用于一本书的家庭作业，制作了一个值表。一旦我了解了如何获取值，构建表格就很容易了，但现在我很难从表格中确定最佳比对序列。

表格示例是按照公式生成的

min(  (i+1, j+1)+penalty)
      (i+1, j)+2)
      (i, j+1)+2))

在书中的伪代码中，如果 i==j 则 penalty 的值为 0，否则为 1。

前 4 行和前 4 列看起来像这样，不匹配扣 1 分，空缺扣 2 分。 :

14   12   10   8
15   13   11   9
16   14   12   10
17   15   13   11

根据书上的说明，确定路径的方法是

1. 从数组槽 [0][0] 开始，在本例中值为 14
   • 检查插槽 [0][1]。当我们向左移动到插槽时，插入一个间隙，从而将值加 2，得到 14
   • 检查插槽 [1][0]，并插入另一个间隙导致值为 17
   • 检查插槽 [1][1]。当我们沿对角线移动时，惩罚值会添加到插槽值中，结果为 14

既然我在[0][1]和[1][1]中有两种可能的匹配，那么下一步要使用哪一种呢？

Answer 1

参见 this实现 Smith-Waterman 的概述，包括追溯。在矩阵中的每个位置，您应该检查 4 件事:

• 如果位置值等于空位惩罚加上上面的位置，则向上是有效的移动。
• 如果位置值等于空位惩罚加上位置左侧，则左侧是有效移动。
• 如果位置值等于匹配值加上位置的左上角，则对角线是有效着法。
• 如果位置值为 0，则完成。

第一个和第二个选项与在其中一个字符串中插入一个间隙相关，第三个与对齐两个字符相关。如果多条路径都有效，那么您就有多种可能的对齐方式。正如文章所述，此时的决定在很大程度上取决于上下文(您有多种选择)。