dc.contributor.author |
Linz, Simone |
en |
dc.contributor.author |
Semple, Charles |
en |
dc.date.accessioned |
2015-02-02T03:54:21Z |
en |
dc.date.issued |
2011-09 |
en |
dc.identifier.citation |
Annals of Combinatorics, 2011, 15 (3), pp. 465 - 484 |
en |
dc.identifier.issn |
0218-0006 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/24366 |
en |
dc.description.abstract |
Calculating the rooted subtree prune and regraft (rSPR) distance between two rooted binary phylogenetic trees is a frequently applied process in various areas of molecular evolution. However, computing this distance is an NP-hard problem and practical algorithms for computing it exactly are rare. In this paper, a divide-and-conquer approach to calculating the rSPR distance is established. This approach breaks the problem instance into a number of smaller and more tractable subproblems. Two reduction rules which were previously used to show that computing the rSPR distance is fixed-parameter tractable can easily be used to complement this new theoretical result, and so a significant positive impact on the running time of calculating this distance in practice is likely. |
en |
dc.relation.ispartofseries |
Annals of Combinatorics |
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.springer.com/gp/open-access/authors-rights/self-archiving-policy/2124
http://www.sherpa.ac.uk/romeo/issn/0218-0006/ |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.title |
A Cluster Reduction for Computing the Subtree Distance Between Phylogenies |
en |
dc.type |
Journal Article |
en |
dc.identifier.doi |
10.1007/s00026-011-0108-3 |
en |
pubs.issue |
3 |
en |
pubs.begin-page |
465 |
en |
pubs.volume |
15 |
en |
dc.description.version |
AM - Accepted Manuscript |
en |
pubs.end-page |
484 |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |
pubs.subtype |
Article |
en |
pubs.elements-id |
460387 |
en |
pubs.org-id |
Science |
en |
pubs.org-id |
School of Computer Science |
en |
dc.identifier.eissn |
0219-3094 |
en |
pubs.record-created-at-source-date |
2015-02-02 |
en |