dc.contributor |
Centre de Recerca Matemàtica |
dc.contributor.author |
Bonet Carbonell, Maria Luisa |
dc.contributor.author |
St. John, Katherine |
dc.contributor.author |
Mahindru, Ruchi |
dc.contributor.author |
Amenta, Nina |
dc.date.accessioned |
2006-05-19T11:10:15Z |
dc.date.available |
2006-05-19T11:10:15Z |
dc.date.issued |
2006-03 |
dc.identifier.uri |
http://hdl.handle.net/2072/2028 |
dc.format.extent |
292829 bytes |
dc.format.mimetype |
application/pdf |
dc.language.iso |
eng |
dc.publisher |
Centre de Recerca Matemàtica |
dc.relation.ispartofseries |
Prepublicacions del Centre de Recerca Matemàtica;669 |
dc.rights |
Aquest document està subjecte a una llicència d'ús de Creative Commons, amb la qual es permet copiar, distribuir i comunicar públicament l'obra sempre que se'n citin l'autor original, la universitat i el centre i no se'n faci cap ús comercial ni obra derivada, tal com queda estipulat en la llicència d'ús (http://creativecommons.org/licenses/by-nc-nd/2.5/es/) |
dc.subject |
Filogènia |
dc.subject |
Mètodes estadístics |
dc.subject |
Arbres (Teoria dels grafs) |
dc.title |
Approximating subtree distances between Phylogenies |
dc.type |
info:eu-repo/semantics/preprint |
dc.description.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 by Bordewich and Semple [5]. This paper presents the first approximation result for this important tree distance. The algorithm follows a standard format for tree distances such as Rodrigues et al. [24] and Hein et al. [13]. 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. |