dc.contributor.author |
Linz, Simone |
en |
dc.contributor.author |
St. John, K |
en |
dc.contributor.author |
Semple, Charles |
en |
dc.date.accessioned |
2015-02-03T22:40:31Z |
en |
dc.date.issued |
2013-11-18 |
en |
dc.identifier.citation |
Theoretical Computer Science, 2013, 513 pp. 129 - 136 |
en |
dc.identifier.issn |
0304-3975 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/24393 |
en |
dc.description.abstract |
Given a set R of rooted phylogenetic trees on overlapping taxa, it takes polynomial time to decide whether or not there exists a rooted phylogenetic tree that is compatible with R. Since not all evolutionary histories for a set of species can be explained by a single tree, it is natural to ask for the minimum number of rooted phylogenetic trees needed such that each tree in R is compatible with at least one tree. This paper shows that it is computationally hard to compute this minimum number. In particular, if R contains rooted triples (rooted binary phylogenetic trees on three leaves), it is NP-complete to decide whether there exist two rooted phylogenetic trees such that each rooted triple in R is compatible with at least one of the two trees. Furthermore, for a set Σ of binary characters and a positive integer k , we show that to decide if there exists a set P of k rooted phylogenetic trees such that each character in Σ is compatible with at least one tree in P is NP-complete for all k⩾3, but solvable in polynomial time for k=2. This generalizes the result for k=1, where it is well-known to be polynomial time. |
en |
dc.language |
aa |
en |
dc.relation.ispartofseries |
Theoretical Computer Science |
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
http://www.sherpa.ac.uk/romeo/issn/0304-3975/ |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.title |
Optimizing tree and character compatibility across several phylogenetic trees |
en |
dc.type |
Journal Article |
en |
dc.identifier.doi |
10.1016/j.tcs.2013.10.015 |
en |
pubs.begin-page |
129 |
en |
pubs.volume |
513 |
en |
dc.description.version |
Pre-print |
en |
pubs.end-page |
136 |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |
pubs.subtype |
Article |
en |
pubs.elements-id |
460401 |
en |
pubs.org-id |
Science |
en |
pubs.org-id |
School of Computer Science |
en |
pubs.record-created-at-source-date |
2014-11-09 |
en |