无向系统发生网络朝向期望网络类的可定向性：实用算法及在树-子朝向问题中的应用

《Algorithms for Molecular Biology》：Orientability of undirected phylogenetic networks to a desired class: practical algorithms and application to tree-child orientation

本文聚焦于系统发生网络方向问题的核心挑战——C-Orientation问题，即判断无向图能否被定向为特定类C的有向系统发生网络。针对现有方法计算瓶颈大、实用性不足的现状，研究团队提出：(1) 一种针对任何具有易处理成员资格测试的类C均适用的精确FPT算法，其参数为网状化数目和最小基本环的最大尺寸；(2) 一种用于树-子网络朝向问题的快速启发式算法。新方法通过大幅缩减对网状化顶点位置的搜索空间，实验证明其显著优于现有指数时间算法。虽然启发式算法随网状化数目增加会出现假阴性，但其速度优势显著，文章同时探讨了其理论改进方向及在生物学上的应用前景。

　　

引言

系统发生网络是描绘物种间复杂进化关系的强大工具，尤其适用于存在网状进化事件的情况，例如杂交、水平基因转移和重组。杂交指不同物种个体间的杂交，可能导致兼具双亲遗传物质的新杂交物种形成。水平基因转移是指将复制的遗传物质传递给另一个非其后代的生物体，此过程在细菌和古菌中尤为常见。重组是不同基因组之间遗传物质的交换，在病毒、细菌、真核生物等中普遍发生。然而，从生物数据构建有向系统发生网络仍具挑战性。邻接网络等基于距离的方法因其可扩展性和数据可视化能力而被广泛应用，但其生成的网络是无向的，这给解释进化历史带来了困难。为提供更具信息量的数据表征，开发一种将无向图转化为具有特定属性的有向系统发生网络的方法具有重要意义。

最近，Huber等人引入了两种不同的方向问题，C-Orientation问题即为其一。该问题不限制根的位置或顶点的入度，而是询问给定的二元网络能否被定向为属于期望类C的有向系统发生网络。对于包括二元树-子网络在内的许多类C，C-Orientation问题的复杂性尚未可知，且缺乏实用方法。本文旨在填补这一空白。

定义与记号

本文涉及的关键概念包括图论基础（如无向图、有向无环图DAG）和系统发生网络的定义。无向二元系统发生网络是一个简单连通无向图，其顶点集划分为度数为3的内部顶点集和度数为1的叶节点集（可与物种集合X对应）。有向二元系统发生网络则是一个简单无环有向图，其底层图连通，包含一个唯一根节点，且其余顶点被划分为树顶点、网状化顶点和叶节点。树-子网络是指每个非叶顶点至少有一个树顶点作为子节点的有向二元系统发生网络，其特点是禁止出现一个顶点有两个网状化子节点或一个网状化顶点有一个网状化子节点的子图结构。

非循环方向问题与已知结果

对于一个无向系统发生网络N，对其进行定向是指将根节点ρ插入到唯一的边e_ρ中，并将其它边定向，使得产生的有向图成为X上的一个有向系统发生网络。Huber等人研究了两类方向问题。受限方向问题要求在给定根边和所有顶点期望入度的约束下，判断是否存在可行的定向。他们证明了若存在满足约束的定向，则该定向是唯一的，并提供了一个线性时间算法。

而C-Orientation问题则不同，它不约束根的位置或顶点入度，而是询问给定的二元网络是否能被定向为属于期望类C的有向系统发生网络。对于树-子网络朝向问题，其复杂性尚未完全解决，且被推测为NP困难问题。虽然已有针对特殊情况的FPT算法，但开发实用方法仍具挑战性，这促使本研究探索启发式方法。

所提方法的理论背景

核心思想是减少对网状化顶点候选位置的搜索空间。对于一个具有r个网状化的网络，从非叶顶点中选择r个顶点作为候选组合的数量是指数级的。关键定理（定理4）指出，如果存在满足约束的定向，那么对于N的任何环基S，都存在一个从S到网状化顶点集V_R的双射φ，使得对于每个环C∈S，有φ(C)∈V(C)。这允许我们仅从每个基本环中选择一个顶点作为候选网状化，从而显著缩减搜索空间。

对于树-子朝向问题，基于其禁止子结构的特点，可以排除包含相邻网状化的候选集。此外，定理6指出，如果任意两个网状化顶点在底层图中的距离至少为3，并且存在满足约束的定向，那么该定向就是一个树-子网络。这启发我们，将网状化顶点尽可能远地放置，可能更容易找到树-子定向。

所提出的方法

本文提出了两种方法。

第一种是用于解决C-Orientation问题的精确FPT算法（算法1）。它首先计算输入网络N的一个最小环基S = {C₁, …, C_r}。然后，算法遍历从每个基本环C_i中各选一个顶点构成的所有候选网状化顶点集V_R（共有∏|V(C_i)|种组合）。对于每个候选集V_R和每条可能的根边e_ρ，算法调用一个线性时间的受限方向问题求解器（基于Huber等人的算法1），检查是否存在满足约束的定向。如果定向存在且属于目标类C，则输出该定向；否则继续搜索。该算法的运行时间是FPT的，参数为网状化数目r和所选最小环基中最大环的尺寸c。

第二种是针对树-子朝向问题的启发式算法（算法2）。它同样基于最小环基，但旨在极大化所选网状化顶点之间两两距离的总和。算法枚举所有从每个基本环中各选一个顶点构成的候选网状化顶点集s，计算其距离总和f(s)，并找出使f(s)最大的一个或多个候选集s。随后，对于每个最优候选集s和每条根边e_ρ，调用受限方向求解器。如果能找到满足约束的定向，则该定向即为一个树-子定向；否则算法返回“否”。该启发式算法速度远快于精确算法，但其准确性随r增大而降低。定理7保证了当网状化数目r≤2时，算法2是正确的。

算法2的理论局限性在于，其最优性依赖于所选的最小环基，不同的环基可能导致不同的最大距离和。更重要的是，最大化网状化顶点间的距离之和并不总是找到树-子定向的最佳策略，可能存在距离和并非最大却能成功定向的候选集，如图7所示ρ, δ_N^-) is not tree-child orientable, regardless of the choice of root edge e_ρ. However, choosing s∈S\S* as shown on the right, with f(s)=19, yields a tree-child orientable (N, e_ρ, δ_N^-)">。

实验

研究者实现了两种算法（算法1的树-子网络版本及算法2）以及Huber等人的现有指数时间算法进行对比。实验使用人工生成的网络作为测试数据。

实验一比较了三种方法在20个具有10个叶片的树-子可定向网络上的执行时间。结果表明，尽管算法1和现有方法都是指数时间，但算法1凭借更小的搜索空间，速度显著优于现有方法。而算法2的速度则比算法1更快。

实验二在289个具有10个叶片和1至5个网状化的网络上评估了算法的准确性和执行时间。算法1被证实是精确的，且速度远快于现有方法。算法2在r≤2时完全正确，且在r≤4的大多数情况下也能正确工作，对“是”和“否”实例的运行时间都远短于算法1。但当r=5时，算法2对许多“是”实例失效。

实验三在471个具有20个叶片和1至9个网状化的更大网络上评估了算法1和算法2。随着网状化数目r的增加，算法2找到树-子定向的能力单调下降。相比之下，算法1仍能为许多大r的实例找到树-子定向，尽管通常耗时较长，但有时也能在可行时间内完成。

讨论

启发式方法速度显著，但随着网状化数目增加，假阴性率上升。除了环基选择会影响目标函数最大值外，更重要的原因在于最大化网状化顶点距离之和并非总是有利于找到树-子定向。文章探讨了算法2在生物学数据上的应用潜力，通过对一个描述八种小麦近缘种进化史的部分树-子网络进行测试，算法2成功判断其可定向，并找到了一个具有不同根位置的替代性树-子定向。尽管根位置不同导致深层网状化历史有异，但两个网络在关键的近期网状化事件上保持一致，这凸显了允许根位置灵活性以发现可能被忽略的期望定向的重要性。同时，该案例也揭示了当前启发式目标函数的局限，可能错过更优解。

结论与未来工作

本文为C-Orientation问题提出了一个精确的FPT算法和一个快速的启发式算法，显著改进了现有方法。实验证明了所提算法的高效性和实用性。启发式算法在网状化数目较小时非常准确且快速，为处理大规模网络提供了可能。未来工作包括：进一步优化启发式算法的目标函数以提高其准确性；探索算法在更多生物数据集上的应用；研究其他网络类（如树基网络、网状化可见网络）的定向问题；以及开发混合策略，结合精确算法与启发式方法的优点，以平衡计算效率与求解精度。