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.


checked on Sep 29, 2022

Page view(s)

checked on Sep 22, 2022

Google ScholarTM



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