Computing the maximum agreement of phylogenetic networks
Computing the maximum agreement of phylogenetic networks
复制标题
DOI：
10.1016/j.tcs.2004.12.012
复制
发表时间：
2005-05-20
影响因子：
1.1
通讯作者：
Sung, WK
中科院分区：
文献类型：
--
作者：
Choy, C;Jansson, J;Sung, WK
我们引入了最大一致性系统发生子网络问题（MASN）来寻找一组系统发生网络所共有的分支结构。我们证明了该问题是NP难的，即使限制到三个系统发育网络，并给出了一个O（n（2））时间算法的特殊情况下，两个水平1的系统发育网络，其中n是在输入网络中的叶子的数量，其中N被称为水平f系统发育网络，如果每个双连通组件在底层无向图诱导N的子图包含最多f个节点的深度为2。我们还展示了如何扩展我们的技术，以产生一个多项式时间算法的任何两个水平f系统发育网络N-1，N-2满足f = O（log n）;更准确地说，它的运行时间是O（垂直酒吧V（N-1）垂直酒吧（.）垂直条V（N-2）垂直条（.）2（f1+f2）），其中V（N-i）和f（i）分别表示Ni中的节点集合和N-i的水平，其中i是{1，2}的元素。(c)2005 Elsevier B. V.保留所有权利。
We introduce the maximum agreement phylogenetic subnetwork problem (MASN) for finding 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(n(2))-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 induces a subgraph of N containing at most f nodes with indegree 2. We also show how to extend our technique to yield a polynomial-time algorithm for any two level-f phylogenetic networks N-1, N-2 satisfying f = O(log n); more precisely, its running time is O(vertical bar V(N-1)vertical bar (.) vertical bar V(N-2)vertical bar (.) 2(f1+f2)), where V(N-i) and f(i) denote the set of nodes in Ni and the level of N-i, respectively, for i is an element of {1, 2}. (c) 2005 Elsevier B.V. All rights reserved.