🧬 序列比对：算法实现与详解

1. Needleman-Wunsch（全局比对 · 线性 gap）

构建 (m+1)×(n+1) 矩阵 H，H[i,j] 表示 A 前 i 个字符与 B 前 j 个字符的最优得分。边界行/列累加 gap 罚分，然后从 H[m,n] 回溯。

// needlemanWunschLinear — 摘自 sequence-alignment-core.js
for (let i = 1; i <= m; i++) {
  for (let j = 1; j <= n; j++) {
    const diag = H[i-1][j-1] + scorer.score(a[i-1], b[j-1]);
    const up   = H[i-1][j] + gap;
    const left = H[i][j-1] + gap;
    H[i][j] = Math.max(diag, up, left);
    trace[i][j] = [diag, up, left].indexOf(H[i][j]); // 0=对角 1=上 2=左
  }
}

回溯：从 (m,n) 沿 trace 走向 (0,0)。trace=0 对齐两字符；1 在 B 上插 gap；2 在 A 上插 gap。

2. Smith-Waterman（局部比对）

与 NW 相同的三种来源，但每项再与 0 取 max，使低分区域「截断」。矩阵全局最大值处开始回溯，直到遇到 0 停止。

const val = Math.max(0, diag, up, left);
H[i][j] = val;
if (val > maxScore) { maxScore = val; maxI = i; maxJ = j; }
// 回溯起点：(maxI, maxJ)，遇 H[i][j]===0 停止

典型场景：在长基因组/蛋白质中搜索短 motif；全局 NW 会被迫对齐无关前缀，得分被拉低。

3. Gotoh 仿射 gap（三矩阵 M / Ix / Iy）

• M[i,j]：A[i] 与 B[j] 对齐（match/mismatch）
• Ix[i,j]：A[i] 对 gap（A 上 opening/extend indel）
• Iy[i,j]：B[j] 对 gap

长 indel 只付一次 open + (k−1)×extend，比线性 gap 的 k×gap 更符合生物学。SW 版本在每个矩阵单元同样 max(0,·)。

4. 打分函数 createScorer

DNA 默认 match=+2、mismatch=−1；蛋白质可选 BLOSUM62 或按疏水/带电等分组的简化分。比对展示时 | 表示相同，: 表示 BLOSUM 保守替换。