Algorithms for combining rooted triplets into a galled phylogenetic network
Algorithms for combining rooted triplets into a galled phylogenetic network
复制标题
DOI：
10.1137/s0097539704446529
复制
发表时间：
2006-01-01
影响因子：
1.6
通讯作者：
Sung, WK
中科院分区：
文献类型：
--
作者：
Jansson, J;Nguyen, NB;Sung, WK
本文考虑的问题是确定给定的有根三元组 T 是否可以无冲突地合并到一个有问题的系统发育网络中，如果可以，则构建这样一个网络。当输入 T 很稠密时，我们在 O(vertical bar Tvertical bar) 时间内解决问题，这是最优的，因为输入的大小是 Theta(vertical bar Tvertical bar)。相比之下，以前解决此问题的最快算法的运行时间为 O(竖条 T 竖条(2))。我们还开发了一种最优的 O（竖条 T 竖条）时间算法，用于枚举由 L 标记的所有与 T 一致的简单系统发育网络，其中 L 是 T 中的叶子标签集，这是我们的主要算法所使用的。接下来，我们证明，如果扩展到非密集输入，即使对于简单系统发育网络的特殊情况，问题也会变得 NP 困难。我们还表明，对于每个正整数 n，在 n 个叶子上都存在一些有根三元组集合 T，使得任何粗糙网络都可以与 T 中的有根三元组的至多 0.4883 中心点垂直条 T 垂直条一致。另一方面，我们提供了一种多项式时间近似算法，该算法始终输出与 T 中有根三元组的至少 5/12 (>0.4166) 因子一致的粗糙网络。
This paper considers the problem of determining whether a given set T of rooted triplets can be merged without conflicts into a galled phylogenetic network and, if so, constructing such a network. When the input T is dense, we solve the problem in O(vertical bar T vertical bar) time, which is optimal since the size of the input is Theta(vertical bar T vertical bar). In comparison, the previously fastest algorithm for this problem runs in O(vertical bar T vertical bar(2)) time. We also develop an optimal O(vertical bar T vertical bar)-time algorithm for enumerating all simple phylogenetic networks leaf-labeled by L that are consistent with T, where L is the set of leaf labels in T, which is used by our main algorithm. Next, we prove that the problem becomes NP-hard if extended to nondense inputs, even for the special case of simple phylogenetic networks. We also show that for every positive integer n, there exists some set T of rooted triplets on n leaves such that any galled network can be consistent with at most 0.4883 center dot vertical bar T vertical bar of the rooted triplets in T. On the other hand, we provide a polynomial-time approximation algorithm that always outputs a galled network consistent with at least a factor of 5/12 (>0.4166) of the rooted triplets in T.