2.1.2 BSW Similarity Score

在 BSW 里，$X(i)$、$Y(j)$ 和 $X(0,i)$、$Y(0,j)$ 是两种不同粒度的东西：

• $X(i)$、$Y(j)$ 是“单个碱基”；
• $X(0,i)$、$Y(0,j)$ 是“前缀子串”。

论文里的 $X(\theta,i)$ 很可能是 OCR 把 $X(0,i)$ 识别成了 $\theta$，所以可以按 $X(0,i)$ 来理解。

---

1. 序列的定义

论文中定义了两条序列：

$$X_m = \{x_0, x_1, \ldots, x_{m-1}\}$$ $$Y_n = \{y_0, y_1, \ldots, y_{n-1}\}$$

这里 $x_i$ 表示序列 $X$ 中第 $i$ 个碱基，$y_j$ 表示序列 $Y$ 中第 $j$ 个碱基。

所以：

• $X(i) = x_i$：序列 $X$ 的第 $i$ 个碱基，例如 A、C、G、T；
• $Y(j) = y_j$：序列 $Y$ 的第 $j$ 个碱基。

它们是单个字符，用于计算匹配或错配的得分。

---

2. $X(0,i)$ 和 $Y(0,j)$ 是什么？

$X(0,i)$ 表示从第 0 个碱基到第 $i$ 个碱基组成的前缀子串：

$$X(0,i) = x_0 x_1 \ldots x_i$$

同理：

$$Y(0,j) = y_0 y_1 \ldots y_j$$

它们是一段序列，而不是单个碱基。

例如，如果：

X = A C G T

那么：

• $X(0) = A$，$X(1) = C$，$X(2) = G$，$X(3) = T$；
• $X(0,2) = A C G$；
• $X(0,3) = A C G T$。

---

3. 在 BSW 中分别起什么作用？

论文说：

S is a similarity score between the base $X(i)$ and $Y(j)$.

也就是说，$S(X(i), Y(j))$ 是两个单个碱基之间的相似性得分。例如：

• 如果 $X(i) = Y(j)$，得分较高；
• 如果不同，得分较低或为负。

论文又说：

$H(i,j)$ refers to the similarity score for the substring $X(0,i)$ and $Y(0,j)$.

也就是说，$H(i,j)$ 是两个前缀子串之间的相似性得分。它是在比较 $X$ 的前 $i+1$ 个碱基和 $Y$ 的前 $j+1$ 个碱基时，得到的最优局部比对得分。

所以关系是：

• 单个碱基的匹配得分 $S(X(i), Y(j))$ 是构建 $H(i,j)$ 的基本单元；
• $H(i,j)$ 通过递推，把之前子串的得分 $H(i-1,j-1)$ 和当前碱基得分 $S(X(i), Y(j))$ 结合起来。

一个典型的 BSW 递推式是：

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

这里：

• $H(i-1,j-1)$：更短前缀子串 $X(0,i-1)$ 和 $Y(0,j-1)$ 的得分；
• $S(X(i), Y(j))$：当前两个碱基的匹配得分；
• 两者相加，就得到扩展到当前碱基后的子串得分。

---

4. 一句话区分

符号	含义	粒度
$X(i)$、$Y(j)$	第 $i$ 个、第 $j$ 个碱基	单个字符
$X(0,i)$、$Y(0,j)$	从 0 到 $i$、从 0 到 $j$ 的前缀子串	一段序列
$S(X(i), Y(j))$	两个碱基的匹配/错配得分	点对点
$H(i,j)$	两个前缀子串的最优局部比对得分	段对段

---

5. 直观理解

可以把 BSW 想象成：

• 每次只比较两个碱基：$X(i)$ 和 $Y(j)$，用 $S$ 打分；
• 但最终要回答的是：$X$ 的前 $i+1$ 个碱基和 $Y$ 的前 $j+1$ 个碱基有多相似，这就是 $H(i,j)$；
• 所以 $H(i,j)$ 是“累积结果”，$S(X(i),Y(j))$ 是“当前一步的增量”。

总结：

$X(i)$、$Y(j)$ 是单个碱基，用来算匹配得分；$X(0,i)$、$Y(0,j)$ 是前缀子串，用来表示当前已经比对的序列范围。$H(i,j)$ 就是这两个前缀子串之间的最优比对得分。