Who is Who in Phylogenetic Networks

Publication no #2268   Type :   Html | Bib | Both

Created: 2012-12-10 16:40:19     Modified: 2014-08-19 20:09:48

2268 Peter J. Humphries, Simone Linz and Charles Semple. On the complexity of computing the temporal hybridization number for two phylogenies. In DAM, Vol. 161:871-880, 2013. Keywords: agreement forest, APX hard, characterization, from rooted trees, hybridization, NP complete, phylogenetic network, phylogeny, reconstruction, time consistent network. Note: http://ab.inf.uni-tuebingen.de/people/linz/publications/TAFapx.pdf.         Toggle abstract "Phylogenetic networks are now frequently used to explain the evolutionary history of a set of species for which a collection of gene trees, reconstructed from genetic material of different parts of the species' genomes, reveal inconsistencies. However, in the context of hybridization, the reconstructed networks are often not temporal. If a hybridization network is temporal, then it satisfies the time constraint of instantaneously occurring hybridization events; i.e. all species that are involved in such an event coexist in time. Furthermore, although a collection of phylogenetic trees can often be merged into a hybridization network that is temporal, many algorithms do not necessarily find such a network since their primary optimization objective is to minimize the number of hybridization events. In this paper, we present a characterization for when two rooted binary phylogenetic trees admit a temporal hybridization network. Furthermore, we show that the underlying optimization problem is APX-hard and, therefore, NP-hard. Thus, unless P=NP, it is unlikely that there are efficient algorithms for either computing an exact solution or approximating it within a ratio arbitrarily close to one. © 2012 Elsevier B.V. All rights reserved." @Article{HLS2013,       AUTHOR = {Humphries, Peter J. and Linz, Simone and Semple, Charles},       TITLE = {On the complexity of computing the temporal hybridization number for two phylogenies},       YEAR = {2013},       JOURNAL = {DAM},       VOLUME = {161},       PAGES = {871-880},       URL = {http://dx.doi.org/10.1016/j.dam.2012.11.022},       NOTE = {http://ab.inf.uni-tuebingen.de/people/linz/publications/TAFapx.pdf},       KEYWORDS = {agreement forest, APX hard, characterization, from rooted trees, hybridization, NP complete, phylogenetic network, phylogeny, reconstruction, time consistent network} }