On the complexity of computing the temporal hybridization number for two phylogenies

Show simple item record

dc.contributor.author Humphries, Peter J en
dc.contributor.author Linz, Simone en
dc.contributor.author Semple, Charles en
dc.date.accessioned 2015-02-03T01:09:59Z en
dc.date.issued 2013-05 en
dc.identifier.citation Discrete Applied Mathematics, 2013, 161 (7-8), pp. 871 - 880 en
dc.identifier.issn 0166-218X en
dc.identifier.uri http://hdl.handle.net/2292/24381 en
dc.description.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. en
dc.relation.ispartofseries Discrete Applied Mathematics en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. Details obtained from http://www.elsevier.com/about/open-access/open-access-policies/article-posting-policy#accepted-author-manuscript http://www.sherpa.ac.uk/romeo/issn/0166-218X/ en
dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.title On the complexity of computing the temporal hybridization number for two phylogenies en
dc.type Journal Article en
dc.identifier.doi 10.1016/j.dam.2012.11.022 en
pubs.issue 7-8 en
pubs.begin-page 871 en
pubs.volume 161 en
dc.description.version AM - Accepted Manuscript en
pubs.end-page 880 en
dc.rights.accessrights http://purl.org/eprint/accessRights/OpenAccess en
pubs.subtype Article en
pubs.elements-id 460395 en
pubs.org-id Science en
pubs.org-id School of Computer Science en
pubs.record-created-at-source-date 2015-02-03 en

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace