Please use this identifier to cite or link to this item:
Title: Computing the maximum agreement of phylogenetic networks
Authors: Choy, C.
Jansson, J. 
Sadakane, K.
Sung, W.-K. 
Keywords: Algorithm
Computational complexity
Maximum agreement subnetwork
Phylogenetic network comparison
Issue Date: 2004
Citation: Choy, C.,Jansson, J.,Sadakane, K.,Sung, W.-K. (2004). Computing the maximum agreement of phylogenetic networks. Electronic Notes in Theoretical Computer Science 91 : 134-147. ScholarBank@NUS Repository.
Abstract: 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 N 1,N2 for any f which is upper-bounded by a constant; more precisely, its running time is O(|V(N1)|·|V(N 2)|·4f), where V(Ni) denotes the set of nodes of Ni. © 2004 Published by Elsevier B.V.
Source Title: Electronic Notes in Theoretical Computer Science
ISSN: 15710661
DOI: 10.1016/j.entcs.2003.12.009
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.