半定向系统发育网络的数学表征及其在多根变体中的应用研究

《Theory in Biosciences》：Characterizing semi-directed phylogenetic networks and their multi-rootable variants

本研究针对半定向系统发育网络定义不明确的问题，通过建立混合图的组合特征条件（如无半定向环和非平凡边路径），首次提出了半定向网络与多半定向网络的显式数学表征。研究人员创新性地将树状子序列、全向点和路径划分等根网络分析工具扩展至半定向场景，系统阐述了网络在树子型（tree-child）、果园型（orchard）和基于树型（tree-based）等约束类别下的可根化条件。该成果发表于《Theory in Biosciences》，为基于网络的进化模型开发奠定了坚实的理论基础。

　　

在进化生物学研究中，系统发育网络为描述物种间复杂的进化关系（如杂交、基因转移等网状进化事件）提供了比系统发育树更灵活的框架。近年来，一种称为半定向网络（semi-directed network）的特殊网络类型受到广泛关注。这类网络可通过将根系统发育网络（即有向无环图）中的部分弧去方向化得到，但该定义具有隐含性——我们无法直接判断一个混合图是否满足这种性质。更复杂的是，在实际生物学数据中确定网络根的位置常面临挑战，而无根或部分去方向化的网络模型可规避这一问题，并展现出更好的可识别性优势。

为此，Niels Holtgrefe等研究人员在《Theory in Biosciences》上发表了题为“Characterizing semi-directed phylogenetic networks and their multi-rootable variants”的研究论文，旨在建立半定向网络与多半定向网络（multi-semi-directed network）的显式数学表征，并进一步探索其在经典根网络类别下的结构性质。

本研究主要采用组合图论与网络拓扑分析的方法，通过定义半定向环（semi-directed cycle）、

Λ路径（∧-path）和边路径（edge-path）等图结构，建立了半定向网络的判定条件；利用樱桃采摘序列（cherry picking sequence）和全向点（omnian）等工具分析网络的可约简性；通过路径划分（path partition）技术刻画网络基于树或森林的性质。关键算法实现了在O(|V|+|E|+|A|)时间内判定混合图是否为（多半）半定向网络。

半定向网络的组合特征

研究团队首先提出了多半定向网络的充要条件：顶点度数满足d(v)≠2且d^–(v)∈{0, d(v)–1}；不存在半定向环；任意两个 reticulation 间无非平凡边路径。进一步地，通过引入Λ路径存在性条件，严格区分了单根半定向网络与多根变体。图3中的网络N₁即为典型半定向网络，而N₂因需双根支持被判定为多半定向网络。

可根化配置的完整表征

基于网络源组分（source component）与汇组分（sink component）的分布特性，研究给出了根配置（root configuration）的完整刻画：每个源组分中必须恰好存在一个根位置（可为顶点、边或弧），且根位置必须位于源组分内。这一结果显著推广了Maxfield等人前期工作中对顶点根选择的限制。

全向点与网络子类关联

通过分析全向点（即出度≥1且边度≤1的顶点）的分布规律，团队建立了半定向网络与树子型（tree-child）网络的关联：强树子型网络当且仅当不存在全向点；弱树子型网络要求全向点数目不超过根数，且全向点与 reticulation 间无非平凡边路径。图7通过三个典型案例直观展示了这一分类。

樱桃采摘序列与果园网络

研究将果园网络（orchard network）的HGT一致性标记（HGT-consistent labelling）推广至多半定向场景，证明弱果园网络等价于存在樱桃/网状樱桃（reticulated cherry）约化序列将网络化为边-顶点森林。强果园网络则要求所有强樱桃采摘序列（strong cherry picking sequence）中的每个源组分网状樱桃（scr-cherry）约化步骤必须存在替代选择。图9-12通过系列网络约化过程演示了这一性质。

路径划分与基于树/森林网络

通过构建满足顶点覆盖性（P1）、叶集匹配性（P2）和交叉组分唯一性（P3）的半定向路径集合，研究实现了弱基于森林网络（weakly forest-based network）的判定。特别地，对单根半定向网络，该路径系统的存在直接等价于弱基于树性（weakly tree-based），为树基性检验提供了新工具。

本研究通过建立半定向系统发育网络的显式组合表征，系统解决了该类网络的结构可判定性问题。所提出的根化条件、子类约束准则与高效判定算法，不仅深化了对网络拓扑结构的理解，更为基于半定向网络的进化模型构建、网络比较与重构算法开发奠定了理论基础。未来研究方向包括将强果园网络表征推广至多根场景、探索强基于森林网络的新判据，以及开发更高效的子类识别算法。这些成果将推动系统发育网络在基因组进化、病毒传播等领域的应用。