2.1.3 Affine gap penalty

在 Banded Smith-Waterman（BSW）中，你给出的两个公式：

E(i+1,j) = \max\{H(i,j) - g_o,\ E(i,j) - g_e,\ 0\}

F(i,j+1) = \max\{H(i,j) - g_o,\ F(i,j) - g_e,\ 0\}

是用于处理 affine gap penalty（仿射间隙罚分） 的辅助递推。它们分别跟踪两种不同类型的 gap：一种是在序列 $Y$ 中插入 gap（即 $X$ 比 $Y$ 多出一个字符），另一种是在序列 $X$ 中插入 gap（即 $Y$ 比 $X$ 多出一个字符）。下面逐层解释。

1. 为什么需要 E 和 F？

Smith-Waterman 的基本得分矩阵 $H(i,j)$ 只记录以 $X(i)$ 和 $Y(j)$ 结尾的最优局部比对得分。但当比对中出现插入或缺失时，罚分不是简单的线性罚分，而是 仿射罚分：

通常 $g_o > g_e$ ，即打开 gap 的代价比延长 gap 更高。为了区分“打开”和“延长”，需要额外的矩阵来记录当前是否已经处于 gap 状态。

于是引入：

$E(i,j)$ ：表示在 $X$ 方向上前进（即 $i$ 增加），而 $Y$ 不动，也就是在 $Y$ 中插入一个 gap（deletion）。它跟踪的是“已经打开了一个 deletion gap”的得分。
$F(i,j)$ ：表示在 $Y$ 方向上前进（即 $j$ 增加），而 $X$ 不动，也就是在 $X$ 中插入一个 gap（insertion）。它跟踪的是“已经打开了一个 insertion gap”的得分。

E(i+1,j) = \max\{H(i,j) - g_o,\ E(i,j) - g_e,\ 0\}

这里 $E(i+1,j)$ 表示在 $X$ 的第 $i+1$ 个位置、 $Y$ 的第 $j$ 个位置处，以 deletion gap 结尾的得分。它有三种可能来源：

从 $H(i,j)$ 打开一个新的 gap
$H(i,j) - g_o$ ：在 $(i,j)$ 处结束一个正常比对，然后向下走一步（ $i$ 增加， $j$ 不变），打开一个新的 deletion gap。代价是减去 gap opening penalty $g_o$ 。
从 $E(i,j)$ 延续已有的 gap
$E(i,j) - g_e$ ：之前已经处于 deletion gap 状态，现在继续向下走一步，延长这个 gap。代价是减去 gap extension penalty $g_e$ 。
取 0
Smith-Waterman 是局部比对，得分不能为负。如果以上两种选择都导致负分，就取 0，表示从当前位置重新开始一个新的局部比对。

所以 $E(i+1,j)$ 记录的是：在 $(i+1,j)$ 处，以 deletion gap 结尾的最优得分。

F(i,j+1) = \max\{H(i,j) - g_o,\ F(i,j) - g_e,\ 0\}

类似地， $F(i,j+1)$ 表示在 $X$ 的第 $i$ 个位置、 $Y$ 的第 $j+1$ 个位置处，以 insertion gap 结尾的得分。它的来源：

从 $H(i,j)$ 打开一个新的 gap
$H(i,j) - g_o$ ：在 $(i,j)$ 处结束正常比对，然后向右走一步（ $j$ 增加， $i$ 不变），打开一个新的 insertion gap。
从 $F(i,j)$ 延续已有的 gap
$F(i,j) - g_e$ ：之前已经处于 insertion gap 状态，继续向右走一步，延长这个 gap。
取 0
同样，局部比对不允许负分。

最终 $H(i,j)$ 的更新通常为：

H(i,j) = \max\{0,\ H(i-1,j-1) + S(X(i),Y(j)),\ E(i,j),\ F(i,j)\}

其中：

所以 $E$ 和 $F$ 是 $H$ 的候选来源，它们共同实现了仿射 gap 罚分。

假设：

那么：

E(i+1,j) = \max\{5 - 2,\ 4 - 1,\ 0\} = \max\{3,\ 3,\ 0\} = 3

这表示：从 $(i,j)$ 向下走一步，无论是打开新 gap 还是延续旧 gap，得分都是 3。如果 $H(i,j)$ 很小，比如 $H(i,j) = 1$ ，那么：

E(i+1,j) = \max\{1 - 2,\ 4 - 1,\ 0\} = \max\{-1,\ 3,\ 0\} = 3

此时延续旧 gap 更好。如果两者都很负，就取 0，重新开始。

在 DP 表中：

        j      j+1
i       H(i,j)  → F(i,j+1)   （向右：在 X 中插入 gap）
i+1     ↓
        E(i+1,j)              （向下：在 Y 中插入 gap）

$E$ 和 $F$ 是 Smith-Waterman 中用于实现仿射 gap 罚分的辅助矩阵：