Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.entcs.2003.12.009
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
Source: 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. https://doi.org/10.1016/j.entcs.2003.12.009
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
URI: http://scholarbank.nus.edu.sg/handle/10635/40073
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.

SCOPUSTM   
Citations

5
checked on Dec 13, 2017

Page view(s)

63
checked on Dec 16, 2017

Google ScholarTM

Check

Altmetric


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