摘要
系统发育网络能够建模网状进化，捕捉如杂交和水平基因转移等事件。在此背景下，一个基本的计算问题是树包含问题，即判断一个给定的系统发育网络是否与一个给定的系统发育树兼容。然而，该问题的经典表述对生物数据中支持不足的分支并不稳健，可能导致假阴性。为了解决这个问题，Bentert、Malík 和 Weller 提出了一个考虑不确定性的放宽版本，称为软树包含。
我们提出了一种算法，可以在时间复杂度为 $2^{O(\Delta_T \cdot k \cdot \log(k))} \cdot n^{O(1)}$ 下解决软树包含问题，其中 $k = \operatorname{sw}(\Gamma) + \Delta_N$，$\Delta_T$ 和 $\Delta_N$ 分别表示树和网络中的最大出度，而 $\operatorname{sw}(\Gamma)$ 表示给定网络树扩展的“扫描宽度”。$n$ 是输入大小。我们的研究利用了在实践中遇到的系统发育网络通常具有低扫描宽度的事实，从而使问题更加可处理。
博主点评： 本文提出的算法在处理不确定性时，展现出对低扫描宽度的有效利用，极大提高了软树包含问题的解决效率，具有重要的理论和应用价值。它为生物信息学中的系统发育分析提供了新的思路，特别是在数据质量不高的情况下。