A Cluster Reduction for Computing the Subtree Distance Between Phylogenies

Show simple item record

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


Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record

Share

Search ResearchSpace


Browse

Statistics