Please use this identifier to cite or link to this item:
https://doi.org/10.1016/j.entcs.2003.12.009
DC Field | Value | |
---|---|---|
dc.title | Computing the maximum agreement of phylogenetic networks | |
dc.contributor.author | Choy, C. | |
dc.contributor.author | Jansson, J. | |
dc.contributor.author | Sadakane, K. | |
dc.contributor.author | Sung, W.-K. | |
dc.date.accessioned | 2013-07-04T07:56:03Z | |
dc.date.available | 2013-07-04T07:56:03Z | |
dc.date.issued | 2004 | |
dc.identifier.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. <a href="https://doi.org/10.1016/j.entcs.2003.12.009" target="_blank">https://doi.org/10.1016/j.entcs.2003.12.009</a> | |
dc.identifier.issn | 15710661 | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/40073 | |
dc.description.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. | |
dc.description.uri | http://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1016/j.entcs.2003.12.009 | |
dc.source | Scopus | |
dc.subject | Algorithm | |
dc.subject | Computational complexity | |
dc.subject | Maximum agreement subnetwork | |
dc.subject | Phylogenetic network comparison | |
dc.type | Conference Paper | |
dc.contributor.department | COMPUTER SCIENCE | |
dc.description.doi | 10.1016/j.entcs.2003.12.009 | |
dc.description.sourcetitle | Electronic Notes in Theoretical Computer Science | |
dc.description.volume | 91 | |
dc.description.page | 134-147 | |
dc.identifier.isiut | NOT_IN_WOS | |
Appears in Collections: | Staff Publications |
Show simple item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.