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

其余指标 · 均值 ± 标准差

逐个种子的原始值全部在 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. 随附材料

环境: 纯 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 —— L 段分段 gap 的最优比对算法,L=2 即本方向
• Altschul S.F., Erickson B.W. (1986) Optimal sequence alignment using affine gap costs. Bull. Math. Biol. —— 1-piece affine 基线的出处
• Li H. (2018) Minimap2: pairwise alignment for nucleotide sequences (arXiv:1708.01492) —— 生产系统里用 2-piece(论文称 concave gap cost)救长 INDEL
• WFA2-lib (smarco/WFA2-lib, GitHub) —— 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 —— 分段 gap 用于 MSA 的最直接前人工作(PRIME)
• Gudyś A. 等 (2026) Fast and accurate multiple-protein-sequence alignment at scale with FAMSA2. Nature Biotechnology · FAMSA 代码库 —— 当前 progressive MSA 的速度/规模标杆(C++)
• Zhai Y. 等 (2025) ReAlign-P: a vertical iterative realignment method for protein multiple sequence alignment. Bioinformatics 41(8):btaf421 —— 近一年该领域的评测惯例(BAliBASE v3 386 例 / OXBench / PREFAB4 / SABRE)
• Light E.G. 等 (2026) MuSAlS: A Fast Multiple Sequence Alignment Approach Using Hierarchical Clustering (arXiv:2601.15458) —— 2026 年 progressive/guide-tree 方向的新工作
• Thompson J.D. 等 (2005) BAliBASE 3.0: latest developments of the multiple sequence alignment benchmark. Proteins (PubMed 16044462) —— 投稿前必须补的标准评测集

本文档由 JouleBeat · DeepGraph 出具。实验代码、日志与原始结果随附,结论可被复查与反驳。