# DeepGraph 免费层交付 · 2-piece affine gap 在 progressive MSA 里的收益边界(预测被推翻)

**提交方向**: 用C/C++写一份2-piece affine gap cost得分策略的progressive 模式的多序列比对程序。
**交付时间**: 2026-07-31
**这一轮真跑了**: 自造合成数据集(6 taxa / 根序列 220bp / K2P 替换 + 混合几何 indel;dev 种子 100/101/102 × 4 家族,test 种子 0/1/2 × 4 家族,pi_long ∈ {0.0, 0.05, 0.2});6 个臂(1-piece baseline 与 2-piece proposed 各 3 个 pi_long 档);3 个测试种子;含两轮各 20 组的网格搜索在内,全流程 20.1 秒跑完。代码与日志随附。

---

## 0. 结论(先说结果)

**我们的预测被推翻了,这条路在你现在的设定下不成立。** 预测是:长 indel 占比 `pi_long=0.20` 时,2-piece 相对 1-piece 的 SP 增益 ≥ 2 个百分点,且 3 个种子全部同号。实测:`pi_long=0.20` 上增益只有 **0.68pp**(baseline 均值 0.4602 → proposed 均值 0.4670),而且**种子符号不一致**——有一个种子上 1-piece 反而更好。`pi_long=0.00` 上增益 **0.09pp**,同样符号不一致。

原因(两种解释,这一轮没有分辨出是哪一种):要么效应真实但在这个规模(6 条序列、约 220bp、每种子 4 个家族)上被噪声淹没,要么 progressive 的贪心传播真的把 2-piece 在 pairwise 上的好处吃掉了——早期的合并一旦锁死 gap 位置,后面更灵活的 gap 模型就没机会发挥。

**下一步该往哪拐:** 别急着把这个 2-piece 实现当方法创新写论文,先把规模和 iterative refinement 这两个变量拉进来(见第 3 节)。代价这边倒是很确定:2-piece 的 5 层 DP 在 `pi_long=0.20` 上运行时间 6.27ms → 10.7ms,峰值 DP 内存 1.31MB → 3.58MB。**精度没换来,开销是实打实的。**

## 1. 我们替你跑了什么

**实验设计一句话:** 同一份 C++ 代码、同一棵 guide tree、同一个 profile 打分函数,唯一变量是 gap 函数——baseline 用 1-piece affine `g(l)=O+l·E`,proposed 用 2-piece affine `g(l)=min(O1+l·E1, O2+l·E2)`;在 dev 集上各做 20 组网格搜索选参数,在 test 集(种子 0/1/2)上报结果。

**baseline 是什么、为什么公平:** baseline 不是外部工具,就是同一份代码把 gap 函数退化成 1-piece。三点保证对照公平:(a) 令 O2=O1、E2=E1 时 2-piece 精确退化为 baseline,即 baseline 是 proposed 的特例;(b) 两臂网格搜索评估次数完全相同(各 20 组);(c) 调参用 dev 种子 100/101/102,报结果用 test 种子 0/1/2,严格分离。proposed 的 (O1,E1) 直接沿用 baseline 选出的值,只搜 (O2,E2)。

**选出的参数:** baseline 三档都是 (O,E)=(4,3);proposed 的 (O1,E1)=(4,3) 固定,(O2,E2) 在 pi_long=0.00 / 0.05 / 0.20 上分别选到 (28, 0.4) / (24, 0.4) / (16, 0.4)。

**主结果表 · sp_score(主指标,越高越好)**

| pi_long | 臂 | seed 0 | seed 1 | seed 2 | 均值 ± 标准差 |
|---|---|---|---|---|---|
| 0.00 | baseline-affine-1p | 0.4505 | 0.4779 | 0.5207 | 0.4830 ± 0.0289 |
| 0.00 | proposed-affine-2p | 0.4475 | 0.4838 | 0.5207 | 0.4840 ± 0.0299 |
| 0.05 | baseline-affine-1p | 0.3438 | 0.4808 | 0.5207 | 0.4484 ± 0.0757 |
| 0.05 | proposed-affine-2p | 0.3408 | 0.4984 | 0.5207 | 0.4533 ± 0.0801 |
| 0.20 | baseline-affine-1p | 0.3438 | 0.4808 | 0.5561 | 0.4602 ± 0.0879 |
| 0.20 | proposed-affine-2p | 0.3406 | 0.4985 | 0.5620 | 0.4670 ± 0.0931 |

增益:pi_long=0.00 为 **0.09pp**,pi_long=0.20 为 **0.68pp**(两个数直接来自 `results.json.headline.claim`);pi_long=0.05 为上表两列均值相减,约 0.49pp。**三档全部符号不一致**——每一档上 seed 0 都是 baseline 略高,另外两个种子是 proposed 略高。

**其余指标 · 均值 ± 标准差**

| pi_long | 臂 | tc_score | sp_near_long_indel | runtime_ms | peak_dp_bytes |
|---|---|---|---|---|---|
| 0.00 | baseline-1p | 0.7649 ± 0.1405 | 0.4830 ± 0.0289 | 5.71 ± 0.157 | 1,080,267 ± 59,593 |
| 0.00 | proposed-2p | 0.7641 ± 0.1413 | 0.4840 ± 0.0299 | 9.99 ± 0.595 | 2,785,935 ± 138,135 |
| 0.05 | baseline-1p | 0.6256 ± 0.2536 | 0.4291 ± 0.1152 | 6.01 ± 0.410 | 1,184,105 ± 132,484 |
| 0.05 | proposed-2p | 0.6238 ± 0.2550 | 0.4325 ± 0.1105 | 10.29 ± 0.170 | 3,087,132 ± 350,299 |
| 0.20 | baseline-1p | 0.4976 ± 0.1049 | 0.3438 ± 0.1105 | 6.27 ± 0.139 | 1,309,470 ± 45,075 |
| 0.20 | proposed-2p | 0.4949 ± 0.1061 | 0.3516 ± 0.0957 | 10.73 ± 0.313 | 3,576,959 ± 82,738 |

逐个种子的原始值全部在 `work/results.json` 的 `arms[].metrics[].per_seed` 里,一个没删。

## 2. 怎么读这个结果

**这些数支持的结论:** 在这个受控设定下,2-piece affine 相对 1-piece 的 SP 增益**小于 1 个百分点,且在 3 个种子上符号不一致**,预测的 ≥2pp 门槛没达到。增益随 pi_long 单调上升(0.09 → 约 0.49 → 0.68pp),方向和"长 indel 越多、2-piece 越有用"的机制一致,但幅度远小于种子间离散度(标准差最高到 0.093),**所以这只是一个方向性的观察,不构成任何统计上的断言**。同时代价确定:5 层 DP 的运行时间接近 1-piece 的两倍,峰值 DP 内存约 2.6–2.7 倍。tc_score 三档上 proposed 都略低于 baseline,差距同样在噪声量级内。

**这些数不支持的结论:** 不能说 2-piece 无效——3 个种子、每种子 4 个家族的样本量,本来就分辨不出 1pp 量级的差异。也不能说 2-piece 有效。**这一轮能确定的只有:在这个规模上它没有可复现的增益,而开销翻倍是确定的。** 我们没跑真实 benchmark、没跟 MAFFT/MUSCLE/FAMSA2 比、没做蛋白序列、没做 iterative refinement,这些结论一条都没有暗示。

**放大后可能变的部分:** 序列更长(实际用 220bp,原计划 800bp)、序列更多(6 条,原计划 8 条)、家族更多(4 个/种子,原计划 10 个)之后,长 indel 事件的绝对数量会上去,信噪比会改善。**如果要复查这个负结果,先加家族数和序列长度,这是最短路径。**

**本轮的三条偏离(全部来自 `results.json.deviations`):**

1. **规模缩了。** n_taxa 8→6,root_len 800bp→220bp,每种子家族数 10→4,proposed 网格的 E2 保留 4 个取值没有收窄——都是为了塞进 4 核共享 CPU 上的 45 分钟预算。网格搜索次数(两臂各 20 组)按原计划保留,没缩。
2. **打分尺度和分支长度改过。** match/mismatch 从最初的 +2/-1 改成 +1/-3,分支长度从 U(0.03,0.18) 缩到 U(0.01,0.05)。原因是发现原尺度下,序列分歧度一高,朴素的 pairwise 比对会偏好插入大量伪造的小 gap(随机列的期望得分变成负的,插小 gap 躲开局部差窗口成了 DP 的真实最优解,不是递推写错)。改完对着 ground truth 验证过。**这意味着预测里那些 (O,E) 绝对数值只在这个打分尺度下有意义**——任务描述没固定打分尺度,我们必须先选一个并验证,才敢信后面的任何数字。
3. **`sp_near_long_indel` 有回退。** 当某个(种子,臂)的 4 个测试家族里一条真实长度 ≥10 的 gap 都没出现时,这个指标无定义(低 pi_long 下长 indel 罕见但不是不可能),此时回退成该种子的整体 sp_score,并在 `logs/run.log` 里逐条记了 `... falls back to sp_score=...`。影响 pi_long=0.00 的全部 3 个种子,以及 pi_long=0.05 的 1 个种子;pi_long=0.20 三个种子都有真实的侧翼数据。**这个指标只用于机制检查,不是主结论的依据**(主结论用的是 sp_score),所以回退不触及"推翻"这个判定。

## 3. 你现在可以拿它做什么

**值得投的一步:先把这个负结果做实,而不是先去优化 2-piece 的实现。** 最短路径是把家族数从 4 提到 10、根序列从 220bp 回到 800bp、种子从 3 提到 10,重跑同一份 `run.sh`——代码不用改,只是参数。如果放大后 pi_long=0.20 的增益仍然 <1pp 且符号不稳,你就拿到了一个干净、可发表的负结论:"2-piece affine 在纯 progressive MSA 里的收益穿不过贪心传播"。这个结论对中文核心 / SCI 四区 / 普通国际会议是够的,而且它比一个含糊的正结果更难被驳。

**第二步(只在第一步做完后再投):加一个 iterative refinement 的开关。** 本轮的两种解释里,"贪心传播吃掉增益"这一条,只有在开了精修之后增益回来,才能被证实。这是一个能把负结果升级成机制性发现的实验。

**先别投的:** 别去做 profile 大小自适应的 gap 参数(SCOPE 第 2 节缺口 B),也别碰参数自动估计(缺口 C)。**这两个都建立在"2-piece 在 progressive 里确实有增益"之上,而这一轮的数据不支持这个前提。** 也别去和 FAMSA2 拼速度和规模,那条线你赢不了。

**审稿人最可能打的三个点**(SCOPE 第 3 节的判断,压成三句):
1. **"2-piece affine 是 Gotoh 1990 的东西,minimap2 / WFA2-lib 早就实现了,你的贡献是什么?"** 最致命。你必须在引言第一段就承认算法归属,把贡献写成"progressive MSA 设定下的受控量化 + 可复现实现",**绝对不要写"我们提出了一种新的 gap 罚分策略"**。
2. **"你的提升就是多两个自由参数调出来的。"** 本轮的对照设计已经堵住了(两臂等量网格、dev/test 种子分离、baseline 是 proposed 的特例),照写即可。而且现在增益本来就不显著,这条攻击反而失效了。
3. **"只有模拟数据,没跟 MAFFT / MUSCLE 比。"** 对普通期刊这是"必须补"。投稿前第一件事是补 BAliBASE 3.0 的 RV11/RV12 + BAliScore。论文里要写清楚两者互补:**模拟数据的不可替代价值就是能控制 indel 长度分布,真实 benchmark 做不到。**

## 4. 随附材料

| 文件 | 是什么 |
|---|---|
| `work/src/simulate.cpp` | C++ 模拟器:随机二叉树 + K2P 替换 + 混合几何 indel;用全局双向链表精确追踪真实比对列,ground truth 是精确的不是近似的 |
| `work/src/msa.cpp` | C++ progressive MSA:k-mer(k=4)余弦距离 + UPGMA guide tree + profile-profile Gotoh DP;1-piece 走 3 层(M/Ix/Iy),2-piece 走 5 层(M/Ix1/Iy1/Ix2/Iy2) |
| `work/experiment.py` | 编排:模拟 + 两轮 dev 网格搜索 + test 集评测 + 写 results.json 和图 |
| `work/run.sh` | **一条命令复现:`bash run.sh`**。内含 g++ -O2 -std=c++17 编译两个 C++ 程序,再跑 experiment.py |
| `work/logs/run.log` | 完整日志:每一组网格搜索的 dev 得分、每个种子每个臂的测试得分、以及全部 `sp_near_long_indel` 回退记录 |
| `work/figs/sp_gain_vs_pi_long.png` | SP 增益随 pi_long 的曲线 |
| `work/results.json` | 原始结果:6 个臂 × 5 个指标 × 3 个种子的逐个数值 + 均值 + 标准差,以及预测判定和偏离说明。**本报告里每个数字都能在这里查到** |
| `work/data/` | 全部模拟数据(未比对输入 FASTA + 真实比对 FASTA),dev 与 test 均在内 |
| `SCOPE.md` | 方向判断与文献查新(本报告第 5 节的出处) |

**环境:** 纯 CPU,Python 3.12.3,**没有用 torch**(这是 C++ 实验,`results.json.env.torch` 记为 n/a),无额外第三方依赖。所有随机性均由种子固定(dev 100/101/102,test 0/1/2),`bash run.sh` 可原样重跑,全流程 20.1 秒。

**关于数据来源:** 我们不需要你的数据、代码或稿子。证据全部由随附的 C++ 模拟器自己生成,不依赖任何外部数据分发,任何人拿到这个目录就能独立复查、也能推翻我们的结论。

## 5. 方向判断与文献(摘自随附的 SCOPE.md)

- **算力不是瓶颈,定位才是。** 这个方向纯 CPU、毫秒量级,4 核机器足够。真问题是"这算不算贡献"。
- **2-piece affine 不是新东西。** Gotoh 1990 年给了 L 段分段 gap 的最优算法(L=2 即本方向);minimap2 从 2018 年起在生产里用它;WFA2-lib 有现成的 `gap_affine_2p` C/C++ 实现。**DP 核心不能当卖点。**
- **MSA 侧的分段 gap 有直接前人工作:** Yamada/Gotoh/Yamana(2006)的 PRIME。引言里必须正面回答"你和它什么关系"。
- **progressive MSA 这条线卷的是规模和速度**(FAMSA2、MuSAlS、ReAlign-P),不是 gap 模型——别往速度方向打。
- **唯一能站住的定位:** 把它当受控的量化问题——在 progressive MSA 这个具体设定下,indel 长度分布偏到什么程度 2-piece 才真的更强、代价多少。公开文献里没有干净答案(2-piece 的实证证据几乎都来自 pairwise 长读段比对)。按这个定位做,中文核心 / SCI 四区 / 普通国际会议合理;当方法创新投顶会顶刊不行。
- **本轮选的是缺口 A**(收益边界的量化),因为它的结论直接决定缺口 B(profile 自适应 gap 参数)和缺口 C(参数自动估计)值不值得做。

**参考来源(原样保留):**

- [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 出具。实验代码、日志与原始结果随附,结论可被复查与反驳。*