用图神经网络快速估算进化树间的SPR距离，提升大规模数据分析效率。
Approximating SPR Distance Between Phylogenetic Trees with Graph Neural Networks
- 构建基于细菌数据的864棵进化树及388对标注距离数据集，支持模型训练。
- 训练的GNN在同类树上解释87%~90%方差，误差比基准降低四倍。
- 适用于同物种、相近规模的树比较，可推广至未见物种但难处理超大树。
比较进化树拓扑结构对理解疫情动态至关重要，但生物意义明确的子树修剪与重接（SPR）距离计算为NP难问题，在大规模数据集上难以处理。本文研究图神经网络（GNN）能否在训练后以近常数时间估算每对树的SPR距离。贡献包括：构建并公开发布一个包含864棵通过UPGMA和邻接法推断的细菌进化树的数据集，涵盖最多9,500个菌株，以及388对带标签的树对；建立可复现的预处理流程，包括中点重根，降低树深度并提供根节点信息，用于精确距离计算与模型根特征输入；验证监督目标：在小规模树上，非根化的phangorn::SPR.dist启发式方法与精确的根化rspr距离高度相关（皮尔逊相关系数0.98–0.99），是理想的单调替代指标；训练一个孪生图同构网络（GIN）回归器。在分布内（即与训练树同物种、同规模范围的保留测试集），其决定系数达到约0.87（保留分割），0.90±0.19（分层交叉验证），误差约为均值基线的四分之一，并展现出部分跨物种迁移能力（$R^2 \≈ 0.37$）。主要局限在于外推至大于训练规模的树时，准确率急剧下降。释放的数据集和已验证的启发式-精确关系为可扩展的学得型SPR近似提供了可复现基础。
原文摘要 · Abstract (English)
Comparing phylogenetic tree topologies is essential for understanding epidemic dynamics, yet biologically meaningful distances such as the Subtree Prune and Regraft (SPR) distance are NP-hard to compute and intractable on large datasets. We investigate whether a Graph Neural Network (GNN) can approximate SPR distances in near-constant time per comparison after training. Our contributions are fourfold. First, we build and publicly release a dataset of 864 phylogenetic trees inferred with UPGMA and Neighbor-Joining over four bacterial species, spanning up to 9{,}500 isolates, together with 388 labelled tree pairs. Second, we establish a reproducible pre-processing pipeline including midpoint re-rooting, which reduces tree depth and supplies the rooting required for exact distance computation and for the model's root-based features. Third, we validate the supervision target: on small trees, where exact SPR is tractable, the unrooted phangorn::SPR.dist heuristic correlates almost perfectly with the exact rooted distance computed by rspr (Pearson $0.98$--$0.99$), making it an excellent monotonic surrogate. Lastly, we train a Siamese Graph Isomorphism Network (GIN) regressor. In-distribution, i.e., held-out trees from the same species and size range as training, it explains roughly 87--90% of the variance ($R^2 \approx 0.87$ on a held-out split; $0.90 \pm 0.19$ under stratified cross-validation), with about four times lower error than a mean-predictor baseline, and shows partial transfer to unseen species ($R^2 \approx 0.37$). Its main limitation is extrapolation to trees larger than those seen in training, where accuracy collapses. The released dataset and the validated heuristic versus exact relationship provide a reproducible basis for scaling learned SPR approximation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。