ConcordTree v0.1.2

ConcordTree

准确性测试

1.1

物种树

SimPhy 1.0.2 与 AliSim 模拟的 100 基因座数据；Small 为 32–256 个物种，Large 为 512–4096 个物种。

Two-panel comparison of mean normalized RF distance on SimPhy Small and Large species-tree datasets — **图 1.** SimPhy Small 与 Large 上的平均 nRF（95% bootstrap 置信区间）。

1.2

基因树

AliSim 模拟的 200 条 DNA 比对，覆盖 256–4096 个物种。

Comparison of mean normalized RF distance on the AliSim single-history gene-tree panel — **图 2.** AliSim 基因树数据上的平均 nRF（95% bootstrap 置信区间）。

1.3

真实数据与 DIPPER 数据

已发表真实数据

数据来源	ConcordTree 注意力	ConcordTree 轻量	DIPPER GPU	FastTree	CASTER
Wang 2020 · Wolbachia	0.1000	0.0667	1.0000	0.0000	0.1667
Pflug 2024 · Bembidion	0.2093	0.1860	0.6512	0.1163	0.1163
Wang 2022 · Oakleaf	0.0286	0.0286	0.6286	—	0.0286
Chakrabarty 2017 · Ostariophysan	0.0625	0.0625	0.5312	0.0625	0.1562
Parada 2021 · Sigmodontinae	0.1579	0.1404	0.9298	0.0175	0.1404
Liu 2017 · Placental	0.1646	0.1519	1.0000	0.1519	0.1392
Foley 2023 · Mammals241	0.0084	0.0126	0.0462	0.0000	0.0126
Choi 2022 · Papilionoid	0.0373	0.0581	0.2614	0.0207	0.0705
Chen 2019 · Ruminant	0.0408	0.0408	0.3469	0.0000	0.0408
Leebens-Mack 2019 · 1KP	0.1200	0.1183	0.9591	0.0979	0.2613
平均	0.0929	0.0866	0.6355	0.0519*	0.1133

DIPPER 论文模拟数据

DIPPER 论文公开的 AliSim 10K–50K 与 RNASim 10K–500K 数据（Walia et al., 2026）。

数据	物种数	ConcordTree 轻量	DIPPER GPU
A10	10,000	0.27928	0.25589
R10	10,000	0.12474	0.16405
A20	20,000	0.26184	0.25974
R20	20,000	0.11062	0.15712
A50	50,000	0.20801	0.26010
R50	50,000	0.09561	0.18214
R100	100,000	0.08831	0.16072
R200	200,000	0.08966	0.13990
R500	500,000	0.08882	0.11711
平均	—	0.14965	0.18853

性能测试

NVIDIA L40S 上的实测时间；每个物种规模包含 10 条 AliSim 数据。

Median runtime with interquartile range across taxon scales on a logarithmic axis — **图 3.** 每条 MSA 的中位运行时间；阴影为四分位区间。

物种数	ConcordTree 轻量	ConcordTree 注意力	DIPPER GPU	VeryFastTree	RapidNJ	FastME
256	0.72 s	0.74 s	3.69 s	10.13 s	0.96 s	6.11 s
512	1.69 s	1.99 s	3.77 s	33.96 s	65.53 s	40.01 s
1,024	4.60 s	5.76 s	3.85 s	42.58 s	92.65 s	88.71 s
2,048	8.93 s	10.36 s	4.00 s	132.69 s	562.91 s	683.45 s
4,096	8.11 s	10.79 s	4.42 s	158.58 s	827.72 s	1,623.33 s

RNASim 大规模运行时间

同一批 DIPPER 论文 RNASim 数据，在单张 NVIDIA L40S 上运行。

物种数	ConcordTree 轻量	DIPPER GPU	耗时倍数
10K	33.07 s	8.94 s	3.70×
20K	1:14.62	39.93 s	1.87×
50K	4:20.54	39.19 s	6.65×
100K	12:02.01	2:21.77	5.09×
200K	40:17.53	10:27.40	3.85×
500K	3:08:36.52	1:05:01.28	2.90×
合计	4:07:04.28	1:19:18.51	3.12×

两种方法均按下述测试配置运行；表中报告单张 NVIDIA L40S 上的完整算法时间。

附录：数据与测试配置

A.1 物种树模拟

SimPhy 1.0.2 为每条记录生成一棵物种树和 100 棵基因树。ILS 组的基因树差异来自不完全谱系排序；complex 组在此基础上加入基因复制、基因丢失和水平转移。随后使用 AliSim 沿每棵基因树模拟 DNA 序列。每个基因座为每个物种保留一条代表序列，缺失的基因座以缺口表示，再将 100 个基因座连接为一个超矩阵。评测时以生成的物种树为参考。

Small 数据包含 32、64、128、192 和 256 个物种，每个规模各有 50 条 ILS 和 50 条 complex 比对，共 500 条。Large 准确性图使用 512 和 1,024 个物种的共同数据，每个规模同样包含两种条件各 50 条，共 200 条。

参数	ILS	complex
物种数	Small: 32, 64, 128, 192, 256 Large: 512, 1,024, 2,048, 3,072, 4,096
物种形成率	Lognormal(−14, 1)
物种树高度	Uniform(100,000, 10,000,000)
每物种个体数	Discrete uniform {1, …, 6}
有效群体大小	Lognormal(12, 0.5)
世代时间	1
全树替换率	Exponential(10,000,000)
分支替换率异质性	species: Lognormal(1.5, 1); locus: Lognormal(1.2, 1); gene × lineage: Lognormal(1.4, 1)
基因复制与丢失	不模拟	GB ~ Uniform(−25, −15); LD ~ Lognormal(GB, 0.4); LB = LD
水平转移	不模拟	GT = GB; LT ~ Lognormal(GT, 0.4); 受供体—受体进化距离约束
序列演化模型	GTR+F+G4, 可选 +I；参数由经验拟合库逐基因座抽取
单基因座序列长度	104–8,000 nt

AliSim 使用的逐基因座序列长度、缺口比例、碱基频率、替换率、Γ 形状参数和不变位点比例来自 RAxML Grove 经验参数库。该开放数据库汇集了 RAxML 与 RAxML-NG Web 服务器上真实分析任务的匿名化模型估计（Höhler et al., 2022）。

Lognormal 后两个数字分别为对数尺度的位置与尺度参数；GB、GT、LD、LB 和 LT 为 SimPhy 对基因复制、转移、丢失及其逐基因座速率的参数记号。

A.2 基因树模拟

AliSim 2.4.0 直接在一棵随机树上模拟一条 DNA 比对，因此每条比对中的全部位点共享同一进化历史。生成树同时作为该条记录的参考树。

数据覆盖 256、512、1,024、2,048 和 4,096 个物种，每个规模 40 条，共 200 条。树形包括 Yule-Harding、均匀随机、平衡树和阶梯树；序列使用多组 GTR 核苷酸替换参数、碱基频率和位点速率异质性，根序列长度为 2,048–16,384 个位点，并在部分记录中模拟插入和缺失。

A.3 DIPPER 论文数据

该组数据直接采用 DIPPER 论文公开的比对和生成树。A10、A20 和 A50 是 AliSim 生成的 DNA 数据；R10、R20、R50、R100、R200 和 R500 是 RNASim 生成的 RNA 数据，覆盖 10K–500K 个物种。

A.4 测试配置

ConcordTree 使用 4 个视图。表格中的“轻量”和“注意力”仅表示四元组评分器的两种可选实现，其余推断流程一致。局部优化以交换比例 0.005 为停止阈值；若拓扑进入重复循环，则保留循环中评分最优的树并停止。

DIPPER 论文数据使用适合其稀疏且相干覆盖结构的缺失感知距离，其余面板使用标准距离。DIPPER GPU 按论文配置运行。

附录：方法

B.1 方法概览

Overview of the ConcordTree inference algorithm

Part 1

推断参数

令 X∈Σ^N×L 表示包含 N 个物种和 L 个对齐位点的 MSA。ConcordTree 的输出是与输入具有相同叶集的一棵无根二叉树 T。一次推断由下列参数组确定：

Θ=(t, g, m, K; ε_V, R_V, ε_C, R_C, ε_S, R_S).

t · 任务类型: 可选基因树或物种树，默认为物种树。
g · AP-NJ 距离: 可选标准距离或缺失感知距离，默认为标准距离。
m · 四元组评分器: 对从一条内部边的四个相邻分支各选一个物种形成的四元组，评分器分别为 AB|CD、AC|BD 和 AD|BC 给出支持分数。分数越高，表示该拓扑与 MSA 中的序列模式越相容；NNI 使用候选拓扑相对当前拓扑的分数增益。可选轻量 MLP 或 Transformer，默认为 MLP。View NNI 始终使用与任务类型匹配的 MLP。
K · View 数量: 可设为 2–8，默认为 4。每个 View 选择一个互补位点子集，并最终产生一棵包含全部 N 个物种的树。
ε_z, R_z · 精修控制: 对阶段 z∈{View, Coordinate, Saturation}，ε_z 是交换比例阈值，R_z 是最大轮数。三个阶段的默认值依次为 (0.01,24)、(0.005,4) 和 (0.005,5)。

Part 2

AP-NJ：无矩阵聚合轮廓邻接法

第 k 个 View 选择位点集合 J_k⊆{1,…,L}，但始终保留全部 N 个物种。AP-NJ 在该子矩阵上构造一棵完整骨架树。每个物种或已合并簇在位点 s 上由四维状态轮廓表示；观测碱基对应 one-hot 向量，缺失状态由距离模型 g 处理。

在标准模型中，缺失状态使用该位点的经验碱基频率 q_s 表示。若 r_is 和 r_js 是两个簇的状态轮廓，则位点不匹配距离为

d_s^std(i,j)=1−r_is^Tr_js.

内积表示两个轮廓在该位点取相同碱基的概率，因此一减去该值就是期望不匹配概率。

在缺失感知模型中，p_is 只记录实际观测质量，m_is=1^Tp_is 是观测质量，π_s=1−‖q_s‖₂² 是背景不匹配概率，w_s=c_s² 表示随机两个物种同时观测到该位点的概率。令

h_is=p_is^T[(1−q_s)−π_s1],

则缺失感知的位点距离为

d_s^cov(i,j)=π_s+(1−π_s)m_ism_js−p_is^Tp_js+w_s[h_is(1−m_js)+h_js(1−m_is)].

当两端均被观测时，该式退化为普通不匹配；当两端均缺失时，距离回到位点先验；只有一端被观测时，它在边际化和经验填补之间连续插值。

相干稀疏指数

CSI 同时描述物种对的共同观测稀疏度，以及不同物种是否在相同区域缺失。令 S_i为物种 i 具有实际观测的位点集合。对每一对物种，定义共同观测比例 O_ij 和观测掩码的 Jaccard 相似度 J_ij：

O_ij=|S_i∩S_j|/L, J_ij=|S_i∩S_j|/|S_i∪S_j|.

相干稀疏指数（coherent sparsity index, CSI）定义为

CSI=[1−median_i<j(O_ij)] median_i<j(J_ij).

第一项在物种对能够共同观测的位点较少时增大，表示“稀疏性”；第二项在不同物种的观测区域高度重合时增大，表示“相干性”。只有两者同时出现，CSI 才高。因此，CSI 区分了普通的分散缺失与成块、相关的缺失，后者正是缺失感知距离所建模的情形。

CSI≤0.25：选择标准距离。CSI≥0.35：选择缺失感知距离。0.25<CSI<0.35：比较两种距离。

两种距离对簇轮廓都是仿射双线性的。令当前活动簇集合为 A、簇数为 n_A，聚合轮廓为 P_s=∑_j∈Ap_js。算法可以直接由 P_s 得到标准 NJ 行和 R_i=∑_j∈Ad_g(i,j)，无需建立稠密的 N×N 距离矩阵。对于稀疏候选对，仍使用标准 NJ 准则

Q(i,j)=(n_A−2)d_g(i,j)−R_i−R_j.

其中 d₍g₎(i,j) 是参数 g 选择的簇间距离，Rᵢ 和 Rⱼ 是对应的距离行和。AP-NJ 只稀疏化候选对的搜索；候选对的距离、行和与 Q 值均按选定公式计算。

算法 1 · AP-NJ

输入：View 子矩阵 X_J，距离模型 g。输出：包含全部物种的二叉树。

为每个物种初始化状态轮廓，并令活动簇集合 A 为全部叶节点。
当 |A|>3 时，利用轮廓投影为每个簇提出少量近邻候选。
由聚合轮廓计算所有活动簇的精确 NJ 行和 R_i。
对候选对计算 Q(i,j)，选择互为最佳且彼此不重叠的簇对。
并行合并选中的簇对；更新平均轮廓和距离偏移，使后续距离满足标准 NJ 递推式。
连接最后三个活动簇并返回树。

Part 3

相容分支合并

每棵 View 树 T_k 被写成非平凡二分分支集合 S(T_k)。算法首先建立分支库 𝒮=⋃_k=1^KS(T_k)。对分支 s，其 View 支持数为

c(s)=∑_k=1^K1[s∈S(T_k)].

c(s)=K 表示所有 View 一致支持该分支。其余分支按局部神经收益是否在所有可用 View 中为非负、支持数、收益中位数和均值依次排序。

两个分支 A|A^c 和 B|B^c 相容，当且仅当下面四个交集至少有一个为空：

A∩B, A∩B^c, A^c∩B, A^c∩B^c.

这个条件保证两个二分分支能够同时出现在同一棵无根树中。算法按证据顺序依次接收相容分支，因此得到的是该顺序下的极大相容集合，而不是声称求解全局加权最优树。

为了给尚未解析的区域提供一致锚点，定义中心 View 为

k^*=arg min_k ∑_ℓ=1^K|S(T_k) △ S(T_ℓ)|.

其中 △ 表示对称差，其大小就是两棵树不同的分支数。中心 View 因此是与其余 View 总分支差最小的那棵树；它只补足锚点，不覆盖已接受的相容分支。

算法 2 · 相容分支合并

输入：View 树 T₁,…,T_K 及其分支证据。输出：共识树 T₀。

提取全部 View 树的规范化二分分支并建立分支库。
将所有 c(s)=K 的一致分支加入集合 𝒞。
按稳定性、View 支持数和神经证据对其余分支排序。
依次扫描分支；若候选分支与 𝒞 中全部分支相容，则将其加入 𝒞。
继续加入中心 View 中与 𝒞 相容的锚点分支。
确定性补全 𝒞，直到包含 N−3 个内部边，并将其实体化为 T₀。

Part 4

三种 NNI 精修

对于内部边 e，其四个相邻分支记为 A、B、C 和 D。保持当前拓扑与两种 NNI 交换构成三个候选状态：AB|CD、AC|BD 和 AD|BC。四元组评分器给出势函数

L_m(AB|CD), L_m(AC|BD), L_m(AD|BC),

其中 m 是所选评分器。若当前状态为 τ₀，最佳替代状态为 τ^*，则交换收益为 Δ(e)=L_m(τ^*)−L_m(τ₀)。每轮只执行收益满足该阶段准则且互不共享内部节点的 NNI，以避免同时修改相邻边。

View NNI

在每棵 AP-NJ 树上检查全部内部边。树的初始拓扑来自该 View 的位点子集，但 NNI 评分读取完整 MSA。它从四个相邻分支各取少量邻近代表，用轻量评分器消除明显局部错误。

Coordinate NNI

从 T₀ 开始，只检查没有得到全部 View 一致支持的边。一个上下文面板可以服务多条邻近边，每条边由两个覆盖视角共同确认，从而批量修复共识树。

Saturation NNI

在 Coordinate 输出树上重新识别不确定边，并为每条边建立专属且四向均衡的上下文。它要求整体收益和代表四元组的中位收益均为正，用于集中复查剩余边。

设第 r 轮接受的交换集合为 M_r。一棵含 N 个叶的无根二叉树具有 N−3 条内部边，因此定义归一化交换比例

ρ_r=|M_r|/(N−3).

阶段 z 在没有可接受交换、ρ_r≤ε_z 或 r≥R_z 时停止。ε_z 控制收敛程度，R_z 控制最坏运行预算。

算法 3 · NNI 精修的通用流程

输入：树 T、阶段 z、评分器 m、停止参数 (ε_z,R_z)。输出：精修后的树。

若 z=View，令目标集合为 T 的全部内部边；否则令目标集合为当前树中未获全部 View 一致支持的边。
按照阶段 z 的规则构造代表物种上下文，并计算每条目标边三种局部拓扑的势函数。
从正收益候选中按收益排序，选择一组互不冲突的 NNI。
同时应用选中的 NNI，得到下一轮树并计算交换比例 ρᵣ。
若没有交换、ρᵣ≤ε_z 或达到 R_z，则返回当前树；否则重新构造上下文并继续下一轮。

执行顺序：每棵 AP-NJ 树先运行 View NNI，得到 T₁,…,Tₖ；合并得到 T₀ 后，依次运行 Coordinate NNI 和 Saturation NNI，输出最终树 T*。

Part 5

计算复杂度

设 N 为物种数，L 为比对长度，K 为 View 数量，S 为每个 View 使用的最大位点数，R 为三个 NNI 阶段的总轮数。读取 MSA 需要 O(NL) 时间；AP-NJ 的期望时间为 O(KNS log N)，无需建立传统 NJ 的稠密 N×N 距离矩阵；NNI 精修检查 O(RN) 条内部边，且每条边使用固定大小的四元组上下文。因此，在 K、S 和 R 固定时，通常的时间增长为 O(NL+N log N)。分支合并对平衡树为 O(KN log N)，在完全阶梯化树上的最坏情况为 O(KN²)。主要内存为输入 MSA 的 O(NL) 与 View 轮廓的 O(NS)；稠密距离矩阵不占用内存。