Skip to main content

2.1.4 BSW match, insertion, deletion

在 Banded Smith-Waterman（BSW）中，match、insertion、deletion 描述的是两条序列比对时，每个位置上的编辑操作。它们决定了 DP 表中路径的走向，也对应不同的得分和罚分。

下面用具体例子说明。

1. 先明确两条序列的角色​

通常：

  • 参考序列（Reference）：记作 XX，长度 mm；
  • 测序读段（Read）：记作 YY，长度 nn。

BSW 的目标是：在参考序列中找一个局部区域，使 read 和它的相似性得分最高。

2. 三种操作的定义​

2.1 Match（匹配/错配）​

  • 含义：参考的一个碱基 X(i)X(i) 和 read 的一个碱基 Y(j)Y(j) 对齐。
  • 结果：
    • 如果 X(i)=Y(j)X(i) = Y(j)，叫 匹配（match），通常加正分；
    • 如果 X(i)≠Y(j)X(i) \neq Y(j)，叫 错配（mismatch），通常加负分或低分。
  • DP 表走向：从左上角对角线来，即 (i−1,j−1)→(i,j)(i-1, j-1) \to (i, j)。
  • 对应公式： H(i−1,j−1)+S(X(i),Y(j))H(i-1,j-1) + S(X(i), Y(j))

2.2 Deletion（缺失）​

  • 含义：参考序列中有一个碱基 X(i)X(i)，但 read 中没有对应的碱基。
    也就是说，read 相对于参考缺失了一个碱基。
  • DP 表走向：垂直移动，即 ii 增加，jj 不变，(i−1,j)→(i,j)(i-1, j) \to (i, j)。
  • 对应公式： E(i,j)E(i,j) 其中 E(i,j)E(i,j) 记录以 deletion 结尾的得分，包含 gap 罚分。

2.3 Insertion（插入）​

  • 含义：read 中有一个碱基 Y(j)Y(j)，但参考中没有对应的碱基。
    也就是说，read 相对于参考多出了一个碱基。
  • DP 表走向：水平移动，即 jj 增加，ii 不变，(i,j−1)→(i,j)(i, j-1) \to (i, j)。
  • 对应公式： F(i,j)F(i,j) 其中 F(i,j)F(i,j) 记录以 insertion 结尾的得分，包含 gap 罚分。

3. 举例说明​

假设参考序列：

X = A C G T

例子 1：完全匹配​

Read：

Y = A C G T

比对：

X:  A  C  G  T
Y:  A  C  G  T
    |  |  |  |
    M  M  M  M
  • 每一步都是 match，走对角线。
  • 没有 insertion 或 deletion。
  • 得分最高。

例子 2：Deletion（read 缺失一个碱基）​

Read：

Y = A C T

比对：

X:  A  C  G  T
Y:  A  C  -  T
    |  |  D  |
    M  M  del M
  • 参考中的 G 在 read 中没有对应碱基。
  • 这叫做 deletion（read 缺失了 G）。
  • 在 DP 表中，从 (2,2) 到 (3,2) 是垂直移动： 
    (2,2) → (3,2)   // i 增加，j 不变
  • 对应 E(3,2)E(3,2)，得分 = H(2,2)−goH(2,2) - g_o 或 E(2,2)−geE(2,2) - g_e。

例子 3：Insertion（read 多出一个碱基）​

Read：

Y = A C G A T

比对：

X:  A  C  G  -  T
Y:  A  C  G  A  T
    |  |  |  I  |
    M  M  M  ins M
  • read 中的 A 在参考中没有对应碱基。
  • 这叫做 insertion（read 多出了 A）。
  • 在 DP 表中，从 (3,3) 到 (3,4) 是水平移动： 
    (3,3) → (3,4)   // i 不变，j 增加
  • 对应 F(3,4)F(3,4)，得分 = H(3,3)−goH(3,3) - g_o 或 F(3,3)−geF(3,3) - g_e。

例子 4：混合情况​

Read：

Y = A C T A T

比对：

X:  A  C  G  -  T
Y:  A  C  -  T  A  T
    |  |  D  I  ?  ?

这个例子较复杂，但可以拆解：

  • A-A：match
  • C-C：match
  • G-空：deletion
  • 空-T：insertion
  • T-A：mismatch
  • 末尾 T：可能继续匹配或结束

BSW 会在 DP 表中寻找最优路径，可能不会采用这种比对，而是选择得分更高的其他路径。

4. 在 DP 表中的直观表示​

假设参考 X=ACGTX = A C G T，read Y=ACTY = A C T，DP 表如下（只画部分）：

j=0j=1 (A)j=2 (C)j=3 (T)
i=00000
i=1 (A)0M
i=2 (C)0M
i=3 (G)0D
i=4 (T)0
  • 对角线：match/mismatch；
  • 垂直向下：deletion（参考有，read 无）；
  • 水平向右：insertion（read 有，参考无）。

BSW 的带状限制会只计算主对角线附近一定宽度内的单元格。

5. 与 PairHMM 的对比​

操作BSWPairHMM
Match对角线，加相似性得分M 状态，乘发射概率和转移概率
Deletion垂直，E 矩阵，gap 罚分D 状态，乘转移概率
Insertion水平，F 矩阵，gap 罚分I 状态，乘转移概率

PairHMM 用概率乘加代替了 BSW 的得分加和取最大值。

6. 一句话总结​

在 BSW 中：

  • Match：两个碱基对齐，走对角线；
  • Deletion：参考有碱基而 read 没有，垂直向下；
  • Insertion：read 有碱基而参考没有，水平向右。

三种操作通过 DP 表的三个方向（左上、上、左）实现，由 HH、EE、FF 矩阵分别处理，最终取最大值得到最优局部比对。