Computing the maximum agreement of phylogenetic networks

摘要

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.