Computing the Maximum Agreement of Phylogenetic Networks
Computing the Maximum Agreement of Phylogenetic Networks
复制标题
DOI：
10.1016/j.entcs.2003.12.009
复制
发表时间：
2004-02
期刊：
影响因子：
--
通讯作者：
C. Choy;J. Jansson;K. Sadakane;W. Sung
中科院分区：
文献类型：
--
作者：
C. Choy;J. Jansson;K. Sadakane;W. Sung
我们引入了最大一致性系统发生子网络问题（MASN），即寻找一组系统发生网络共享的分支结构。我们证明，即使仅限于三个系统发生网络，该问题也是 NP 困难的，并针对两个 1 级系统发生网络的特殊情况给出 O(n2) 时间算法，其中 n 是输入网络中的叶数，如果底层无向图中的每个双连通分量最多包含 n 个入度为 2 的节点，则 N 称为 f 级系统发生网络。 算法可以扩展为两个 f 级系统发育网络 N1,N2 生成多项式时间算法，对于任何上限为常数的 f；更准确地说，它的运行时间是 O(|V(N1)|·|V(N2)|·4f)，其中 V(Ni) 表示 Ni 的节点集。
We introduce the maximum agreement phylogenetic subnetwork problem (MASN) of finding a branching structure shared by a set of phylogenetic networks. We prove that the problem is NP-hard even if restricted to three phylogenetic networks and give an O(n2)-time algorithm for the special case of two level-1 phylogenetic networks, where n is the number of leaves in the input networks and where N is called a level-f phylogenetic network if every biconnected component in the underlying undirected graph contains at most f nodes having indegree 2 in N. Our algorithm can be extended to yield a polynomial-time algorithm for two level-f phylogenetic networks N1,N2for any f which is upper-bounded by a constant; more precisely, its running time is O(|V(N1)|·|V(N2)|·4f), where V(Ni) denotes the set of nodes of Ni.