Who is Who in Phylogenetic Networks

Publication no #415   Type :   Html | Bib | Both

Created: 2007-11-17 01:16:41     Modified: 2011-06-07 19:51:00

415 Charles Choy, Jesper Jansson, Kunihiko Sadakane and Wing-Kin Sung. Computing the maximum agreement of phylogenetic networks. In Proceedings of Computing: the Tenth Australasian Theory Symposium (CATS'04), Vol. 91:134-147 of Electronic Notes in Theoretical Computer Science, 2004. Keywords: dynamic programming, FPT, level k phylogenetic network, MASN, NP complete, phylogenetic network, phylogeny. Note: http://www.df.lth.se/~jj/Publications/masn6_CATS2004.pdf.         Toggle 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." @InProceedings{CJSS2004,       AUTHOR = {Choy, Charles and Jansson, Jesper and Sadakane, Kunihiko and Sung, Wing-Kin},       TITLE = {Computing the maximum agreement of phylogenetic networks},       YEAR = {2004},       BOOKTITLE = {Proceedings of Computing: the Tenth Australasian Theory Symposium (CATS'04)},       VOLUME = {91},       PAGES = {134-147},       SERIES = {Electronic Notes in Theoretical Computer Science},       URL = {http://dx.doi.org/10.1016/j.entcs.2003.12.009},       NOTE = {http://www.df.lth.se/~jj/Publications/masn6_CATS2004.pdf},       ANNOTE = {CITE : },       KEYWORDS = {dynamic programming, FPT, level k phylogenetic network, MASN, NP complete, phylogenetic network, phylogeny} }