title: Approximating subtree distances between phylogenies.
abstract: We give a 5-approximation algorithm to the rooted Subtree-Prune-and-Regraft (rSPR) distance between two phylogenies, which was recently shown to be NP-complete. This paper presents the first approximation result for this important tree distance. The algorithm follows a standard format for tree distances. The novel ideas are in the analysis. In the analysis, the cost of the algorithm uses a "cascading" scheme that accounts for possible wrong moves. This accounting is missing from previous analysis of tree distance approximation algorithms. Further, we show how all algorithms of this type can be implemented in linear time and give experimental results.
authors.affiliation: Lenguajes y Sistemas Informaticos, LSI, Universidad Politecnica de Catalunya, UPC, Barcelona, Spain.
authors.forename: Maria Luisa
authors.initials: ML
authors.lastname: Bonet
authors.forename: Katherine
authors.initials: K
authors.lastname: St John
authors.forename: Ruchi
authors.initials: R
authors.lastname: Mahindru
authors.forename: Nina
authors.initials: N
authors.lastname: Amenta
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology / Q000379:methods*; D008954:Models, Biological; D010802:Phylogeny