Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.tcs.2004.12.012
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: 2005
Source: Choy, C., Jansson, J., Sadakane, K., Sung, W.-K. (2005). Computing the maximum agreement of phylogenetic networks. Theoretical Computer Science 335 (1) : 93-107. ScholarBank@NUS Repository. https://doi.org/10.1016/j.tcs.2004.12.012
Abstract: 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(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 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 N1,N2 satisfying f=O(logn); more precisely, its running time is O(|V(N1)|·|V(N2)|·2f1+f2), where V(Ni) and fi denote the set of nodes in Ni and the level of Ni, respectively, for i∈{1,2}. © 2005 Elsevier B.V. All rights reserved.
Source Title: Theoretical Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/39452
ISSN: 03043975
DOI: 10.1016/j.tcs.2004.12.012
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

38
checked on Dec 11, 2017

WEB OF SCIENCETM
Citations

34
checked on Dec 11, 2017

Page view(s)

65
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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