# DeepGraph 免费层交付 · 2-piece affine gap 的 progressive 多序列比对

**提交方向**: 用 C/C++ 写一份 2-piece affine gap cost 得分策略的 progressive 模式多序列比对程序
**目标档位**: 把实验跑完,给数据和结果 · **投稿目标**: 未填写(按"中文核心 / SCI 三四区 / 普通国际会议"校准)
**交付时间**: 2026-07-31

---

## 0. 先说一个判断:算力完全够,卡你的是"这算不算贡献"

这个方向纯 CPU、不需要 GPU:8 条 ~800 bp 序列的 progressive 比对,一次跑在毫秒量级,4 核机器上做上千次参数扫描也就几分钟。硬件不是问题。

真正的问题是定位。2-piece affine(`g(l) = min{O₁+l·E₁, O₂+l·E₂}`)不是新东西:Gotoh 1990 年就给了 L 段分段 gap 的 O((L+C)MN) 算法;minimap2 从 2018 年起在生产环境里用它;WFA2-lib 有现成的 `gap_affine_2p` C/C++ 实现。所以"我用 C++ 写了一个 2-piece affine 的 progressive MSA"作为方法学创新,审稿人一句"已有工作"就能毙掉。

**能站住的定位只有一个:把它当成一个受控的量化问题——在 progressive MSA 这个具体设定下,indel 长度分布要偏到什么程度,2-piece 才真的比 1-piece 强,代价是多少。** 这个问题公开文献里没有干净的答案(2-piece 的实证证据几乎都来自 pairwise 的长读段比对,不是多序列的 progressive 流程)。按这个定位做扎实,发中文核心 / SCI 四区 / 普通国际会议是合理的;当成方法创新投顶刊顶会不行。

## 1. 领域现状:算法层是成熟工程,拥挤程度中等偏高,但"分段 gap × progressive MSA"这一格是空的

- **分段 gap 本身早已定型。** Gotoh(1990)给了通用的 L 段线性 gap 最优比对算法,L=2 就是你要写的东西。工程侧现成实现遍地:minimap2 用 2-piece(论文里叫 concave gap cost)来救长 INDEL;WFA2-lib 直接暴露 `affine2p_penalties`(O1/E1/O2/E2),公式就是 `min{O₁+N·E₁, O₂+N·E₂}`。**你写的 DP 核心,别人已经写过且优化过——这部分不要当卖点。**
- **MSA 侧用分段 gap 的先例存在但很少。** Yamada / Gotoh / Yamana(2006, BMC Bioinformatics)的 PRIME 就是"group-to-group 比对 + 分段线性 gap cost",结论是在 BAliBASE 3.0 / PREFAB 4.0 上能达到当时最好一档的精度。这是你最直接的前人工作,**审稿人一定会问你和它什么关系,必须在引言里正面回答。**
- **progressive MSA 这条线本身还很活跃,而且卷的是"规模和速度",不是 gap 模型。** FAMSA2(Gudyś 等,Nature Biotechnology 2026)是 C++ 的 progressive 比对器,报告 8 小时跑完整个 Pfam-A v37(6200 万条序列/2.2 万个家族),平均比现有工具快约 400 倍;MuSAlS(arXiv, 2026-01,ISMB 2026)走层次聚类 guide tree;ReAlign-P(Bioinformatics 2025, C++17)做的是比对后精修。**结论:你不可能在速度/规模上赢这些人,别往那个方向打。**
- **审稿人默认你要比的对象:** 同一份代码里的 1-piece affine(自身对照,必须有),以及 ClustalW/MUSCLE/MAFFT 里至少一个外部 progressive 基线;评测集默认是 BAliBASE 3.0(386 个家族)、OXBench、PREFAB4 之一。

## 2. 还开着的缺口(按可行性排序)

**缺口 A(推荐,本轮做):2-piece 在 progressive MSA 里的收益边界没人量化过。**
已有证据都是 pairwise 的:两条序列上 2-piece 能救长 INDEL。但 progressive 是贪心的——早期一次错误的 gap 放置会一路传播到最后。**"pairwise 上的收益能不能穿过 progressive 的贪心传播存活下来",是一个没被单独测过的问题。** 做法是控制模拟数据的 indel 长度分布(长 indel 占比 π),扫出收益随 π 的曲线和转折点。工作量小、结论硬、负结果也有价值。够中文核心 / SCI 四区。

**缺口 B(可做,工作量翻倍):profile 上的 gap 参数该不该随 profile 大小变。**
现有实现基本把 O/E 当常数。但 profile-profile 比对里,一列 30 条序列的 profile 和一条裸序列,gap 的"证据强度"完全不同。让 (O₂,E₂) 随 profile 内已有 gap 比例自适应,是一个具体、可实现、且没被 2-piece 语境下测过的改动。做成了能撑起一篇完整期刊文章。

**缺口 C(风险高,不建议现在碰):参数自动估计。**
从数据本身估 (O₁,E₁,O₂,E₂) 而不是网格搜。学术上最值钱,但要建 indel 长度的统计模型,还要防过拟合,工作量和审稿难度都是前两个的数倍。

## 3. 评审会打你的三个点(提前堵)

1. **"2-piece affine 是 Gotoh 1990 的东西,minimap2/WFA2-lib 早就实现了,你的贡献是什么?"**
 —— 最致命的一条。堵法:引言第一段就承认算法归属,把贡献明确写成"progressive MSA 设定下的受控量化 + 开源可复现实现",并给出一个数值化的结论(例如"长 indel 占比低于 X% 时 2-piece 不值得")。**别写"我们提出了一种新的 gap 罚分策略"——这句话就是自曝。**
2. **"2-piece 比 1-piece 多两个自由参数,你的提升就是多调参调出来的。"**
 —— 中等严重,但很容易被抓。堵法三件套:(a) 明说 1-piece 是 2-piece 的特例(令 O₂=O₁, E₂=E₁),所以在调参集上 2-piece 不可能更差,真正的信息在测试集;(b) 两臂给**完全相同的网格搜索次数**;(c) 调参集和测试集用不同随机种子生成,严格分离。
3. **"只有模拟数据 / 没跟 MAFFT、MUSCLE 比。"**
 —— 对普通期刊来说这是"必须补",不是"可以不补"。本轮明确不做,但你投稿前必须补上 BAliBASE 3.0 的 RV11/RV12 加 BAliScore 评分。模拟数据的价值是**能控制 indel 长度分布**(真实 benchmark 做不到),两者互补,论文里要这么写。
4. (附带)**性能回归也会被问。** 2-piece 的 DP 要 5 层(M / I₁ / D₁ / I₂ / D₂)而不是 3 层,时间和内存都会涨。**如果你只报精度不报耗时,审稿人会当你在藏。** 本轮会一起测。

## 4. 我们这一轮真去跑的实验

**选缺口 A。** 理由:它是唯一一个能在 60 分钟 CPU 预算内跑出可站住结论的,而且它的结论直接决定缺口 B/C 值不值得做——如果 2-piece 的收益在 progressive 里根本穿不过来,后面两个缺口都白搭。

**可被推翻的预测:**
> 2-piece 相对 1-piece 的精度增益强依赖于长 indel 占比 π。具体预测:**π=0 时 SP 增益 ≤ 0.5 个百分点且 3 个种子不同号(即不显著);π=0.20 时 SP 增益 ≥ 2 个百分点且 3 个种子全部同号。**
> **推翻条件(任一即算预测被推翻):** ① π=0.20 时增益 < 1 个百分点,或 3 个种子符号不一致 —— 说明 pairwise 上的收益被 progressive 的贪心传播吃掉了,这本身就是有价值的负结果;② π=0 时 2-piece 反而显著更好(> 1 个百分点)—— 说明增益来自调参而非 gap 模型,第 3 节第 2 条的质疑成立。

**主指标表**

| 指标 | 口径 | 为什么 |
|---|---|---|
| `sp_score` | 与真实比对相比,正确配对的残基对占参考对总数的比例 | MSA 领域标准主指标,审稿人认这个 |
| `tc_score` | 完全正确的列数 / 参考列数 | 比 SP 严格,能暴露"大体对但边界错" |
| `sp_near_long_indel` | 只统计长 indel(≥10)边界前后 5 列的 SP | **机制指标**:2-piece 若真起作用,收益必须集中在这里。若总 SP 涨了但这里没涨,说明是别的原因 |
| `runtime_ms` | 单次完整 MSA 墙钟(不含 IO) | 5 层 DP 的代价必须报 |
| `peak_dp_bytes` | DP 矩阵峰值分配字节 | 同上 |

**要扫的自变量:** 长 indel 占比 `pi_long ∈ {0.00, 0.05, 0.20}`(indel 长度 = 混合分布:短 = 几何分布均值 2;长 = 几何分布均值 30)。

**baseline 是什么、为什么公平:** baseline 是**同一份 C++ 代码、同一棵 guide tree、同一个 profile 打分函数**,只把 gap 函数换成 1-piece affine `g(l)=O+l·E`。用同一份代码而不是外部工具,是为了让唯一变量就是 gap 模型——外部工具(MAFFT/MUSCLE)差异来自 guide tree、打分矩阵、迭代精修等一堆混杂因素,不能用来回答这个问题(它们是投稿时必须补的**外部**基线,不是本实验的**受控**对照)。两臂各给 20 次网格搜索评估,在 dev 集(种子 100/101/102 生成的数据)上选参数,在 test 集(种子 0/1/2)上报结果。

**统计口径:** 3 个随机种子 × 每种子 10 个模拟家族(8 条序列 / 根长 800 bp / 随机拓扑),报每种子均值 + 跨种子均值与标准差 + 3 个种子的逐一数值(不只报均值)。两臂在同一批数据、同一棵 guide tree 上跑,调参预算对齐。**负结果照报**:如果 π=0.20 上也没有增益,报告原样写"2-piece 在 progressive MSA 中未观察到可复现增益",并给出 `sp_near_long_indel` 的分解来说明是 pairwise 阶段就没赢,还是赢了但被传播误差抹掉。

**这一轮做不到的部分(明确列出):**
- 不跑真实 benchmark(BAliBASE / OXBench / PREFAB4)。BAliBASE 的官方分发走老 FTP,可用性不稳定,不放进 60 分钟预算里赌;这是投稿前必须补的第一件事。
- 不与 MAFFT / MUSCLE / FAMSA2 横向比较。
- 只做核酸(4 字母、match/mismatch 打分),不做蛋白 BLOSUM62 / profile PSSM 打分。选核酸是因为 2-piece affine 的真实战场就是长 indel 多的核酸比对(minimap2 的场景),蛋白上长 indel 稀少,信号更弱。
- 不做 iterative refinement(MAFFT/MUSCLE 式的迭代精修),只做纯 progressive——加了精修就分不清增益来自 gap 模型还是精修。
- 不做 SIMD / 多线程优化,不测 >50 条序列的规模。
- 不做参数自动估计(缺口 C)。

## 5. 参考来源

- [Gotoh O. (1990) Optimal sequence alignment allowing for long gaps. *Bull. Math. Biol.* 52:359–373](https://link.springer.com/article/10.1007/BF02458577) —— L 段分段 gap 的最优比对算法,L=2 即本方向
- [Altschul S.F., Erickson B.W. (1986) Optimal sequence alignment using affine gap costs. *Bull. Math. Biol.*](https://link.springer.com/article/10.1007/BF02462326) —— 1-piece affine 基线的出处
- [Li H. (2018) Minimap2: pairwise alignment for nucleotide sequences (arXiv:1708.01492)](https://arxiv.org/abs/1708.01492) —— 生产系统里用 2-piece(论文称 concave gap cost)救长 INDEL
- [WFA2-lib (smarco/WFA2-lib, GitHub)](https://github.com/smarco/WFA2-lib) —— C/C++ 的 `gap-affine-2p` 现成实现,公式 g(N)=min{O₁+N·E₁, O₂+N·E₂},参数名 `affine2p_penalties.*`
- [Yamada S., Gotoh O., Yamana H. (2006) Improvement in accuracy of multiple sequence alignment using novel group-to-group sequence alignment algorithm with piecewise linear gap cost. *BMC Bioinformatics*](https://pmc.ncbi.nlm.nih.gov/articles/PMC1769516/) —— 分段 gap 用于 MSA 的最直接前人工作(PRIME)
- [Gudyś A. 等 (2026) Fast and accurate multiple-protein-sequence alignment at scale with FAMSA2. *Nature Biotechnology*](https://www.nature.com/articles/s41587-026-03095-3) · [FAMSA 代码库](https://github.com/refresh-bio/FAMSA) —— 当前 progressive MSA 的速度/规模标杆(C++)
- [Zhai Y. 等 (2025) ReAlign-P: a vertical iterative realignment method for protein multiple sequence alignment. *Bioinformatics* 41(8):btaf421](https://academic.oup.com/bioinformatics/article/41/8/btaf421/8213638) —— 近一年该领域的评测惯例(BAliBASE v3 386 例 / OXBench / PREFAB4 / SABRE)
- [Light E.G. 等 (2026) MuSAlS: A Fast Multiple Sequence Alignment Approach Using Hierarchical Clustering (arXiv:2601.15458)](https://arxiv.org/abs/2601.15458) —— 2026 年 progressive/guide-tree 方向的新工作
- [Thompson J.D. 等 (2005) BAliBASE 3.0: latest developments of the multiple sequence alignment benchmark. *Proteins* (PubMed 16044462)](https://pubmed.ncbi.nlm.nih.gov/16044462/) —— 投稿前必须补的标准评测集

---

*本文档由 JouleBeat · DeepGraph 出具。文献结论来自公开检索,已标注出处;判断部分是我们的观点,可以被反驳。*

```json
{
  "task_slug": "msa-2piece-affine-gap",
  "question": "在 progressive 多序列比对中,2-piece affine gap cost 相对 1-piece affine 的精度增益,如何随序列演化中长 indel 的占比变化?增益能否穿过 progressive 贪心传播存活下来,代价是多少?",
  "falsifiable_prediction": "预测增益强依赖长 indel 占比 pi_long:pi_long=0 时 2-piece 的 SP 增益 <= 0.5 个百分点且 3 个种子不同号;pi_long=0.20 时 SP 增益 >= 2 个百分点且 3 个种子全部同号。推翻条件:(1) pi_long=0.20 时增益 < 1 个百分点或 3 个种子符号不一致;(2) pi_long=0 时 2-piece 显著更好(>1 个百分点),说明增益来自额外调参自由度而非 gap 模型。",
  "dataset": "程序生成(自带 C++ 模拟器 simulate.cpp,无外部依赖):沿随机二叉树演化 8 条核酸序列,根序列长 800 bp,分支上施加替换(K2P,transition/transversion=2)与 indel 事件;indel 长度为混合分布——以概率 (1-pi_long) 取几何分布(均值 2),以概率 pi_long 取几何分布(均值 30)。输出两份 FASTA:未比对序列(输入)+ 真实比对(ground truth)。dev 集用种子 100/101/102,test 集用种子 0/1/2,每种子 10 个家族。",
  "arms": [
    {
      "name": "baseline-affine-1p",
      "is_baseline": true,
      "what": "同一份 C++ progressive MSA 程序:k-mer 距离 + UPGMA guide tree,profile-profile Gotoh 仿射 DP(3 层 M/I/D),gap 代价 g(l)=O+l*E。在 dev 集上做 20 次网格搜索(O in {4,6,8,10,12} x E in {0.5,1,2,3})选最优 (O,E),固定后在 test 集评测。"
    },
    {
      "name": "proposed-affine-2p",
      "is_baseline": false,
      "what": "同一程序、同一 guide tree、同一 profile 打分函数,仅把 gap 代价换成 g(l)=min{O1+l*E1, O2+l*E2},DP 扩到 5 层(M/I1/D1/I2/D2,Gotoh 1990 的 L=2 情形)。(O1,E1) 固定为 baseline 在 dev 集选出的最优值,在 dev 集上对 (O2,E2) 做 20 次网格搜索(O2 in {12,16,20,24,28} x E2 in {0.05,0.1,0.2,0.4}),两臂调参评估次数严格相同。注意 O2=O1,E2=E1 时退化为 baseline,即 baseline 是本臂的特例。"
    }
  ],
  "metrics": [
    {"name": "sp_score", "higher_is_better": true, "what": "与模拟真实比对相比,正确配对的残基对数 / 真实比对中的残基对总数"},
    {"name": "tc_score", "higher_is_better": true, "what": "与真实比对完全一致的列数 / 真实比对的列数"},
    {"name": "sp_near_long_indel", "higher_is_better": true, "what": "机制指标:仅统计真实比对中长度 >= 10 的 gap 段边界前后各 5 列范围内的 SP 分数"},
    {"name": "runtime_ms", "higher_is_better": false, "what": "单个家族完整 MSA 的墙钟毫秒数,不含文件 IO"},
    {"name": "peak_dp_bytes", "higher_is_better": false, "what": "DP 矩阵峰值分配字节数(程序内部计数,非 RSS)"}
  ],
  "sweep": {"pi_long": ["0.00", "0.05", "0.20"]},
  "seeds": [0, 1, 2],
  "budget_minutes": 45,
  "cpu_feasible": true,
  "out_of_scope": [
    "不下载/评测真实 benchmark(BAliBASE / OXBench / PREFAB4 / SABRE)——官方分发走老 FTP,可用性不稳定,不进本轮时间预算",
    "不与 MAFFT / MUSCLE / ClustalW / FAMSA2 等外部工具横向比较(本轮只做同代码受控对照)",
    "不做蛋白序列与 BLOSUM62 / profile PSSM 打分,只做核酸 match/mismatch",
    "不做 iterative refinement,只做纯 progressive(否则无法区分增益来源)",
    "不做 SIMD / 多线程优化,不测超过 50 条序列或超过 5 kb 的规模",
    "不做 gap 参数的自动估计或学习(缺口 C)",
    "不做 profile 大小自适应的 gap 参数(缺口 B)"
  ]
}
```