Who is Who in Phylogenetic Networks

Publication no #2044   Type :   Html | Bib | Both

Created: 2010-08-17 18:46:19     Modified: 2010-08-17 18:46:56

2044 Mihaela Baroni and Mike Steel. Accumulation Phylogenies. In ACOM, Vol. 10(1):19-30, 2006. Keywords: abstract network, from clusters, from distances, phylogenetic network, phylogeny, polynomial, reconstruction, regular network. Note: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.1960.         Toggle abstract "We investigate the computational complexity of a new combinatorial problem of inferring a smallest possible multi-labeled phylogenetic tree (MUL tree) which is consistent with each of the rooted triplets in a given set. We prove that even the restricted case of determining if there exists a MUL tree consistent with the input and having just one leaf duplication is NP-hard. Furthermore, we show that the general minimization problem is NP-hard to approximate within a ratio of n 1-ε for any constant 0<ε≤1, where n denotes the number of distinct leaf labels in the input set, although a simple polynomial-time approximation algorithm achieves the approximation ratio n. We also provide an exact algorithm for the problem running in O *(7 n ) time and O *(3 n ) space. © 2009 Springer-Verlag Berlin Heidelberg." @Article{BaroniSteel2006,       AUTHOR = {Baroni, Mihaela and Steel, Mike},       TITLE = {Accumulation Phylogenies},       YEAR = {2006},       JOURNAL = {ACOM},       VOLUME = {10},       NUMBER = {1},       PAGES = {19-30},       URL = {http://dx.doi.org/10.1007/978-3-642-10631-6_121},       NOTE = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.1960},       KEYWORDS = {abstract network, from clusters, from distances, phylogenetic network, phylogeny, polynomial, reconstruction, regular network} }