Please use this identifier to cite or link to this item:
|Title:||Computing the maximum agreement of phylogenetic networks||Authors:||Choy, C.
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. 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.
checked on Apr 21, 2019
checked on Apr 20, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.