| Publicació: |
Centre de Recerca Matemàtica 2006 |
| Resum: |
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. |
| Drets: |
Aquest document està subjecte a una llicència d'ús Creative Commons. Es permet la reproducció total o parcial, la distribució, i la comunicació pública de l'obra, sempre que no sigui amb finalitats comercials, i sempre que es reconegui l'autoria de l'obra original. No es permet la creació d'obres derivades.  |
| Llengua: |
Anglès |
| Col·lecció: |
Centre de Recerca Matemàtica. Prepublicacions |
| Col·lecció: |
Prepublicacions del Centre de Recerca Matemàtica ; 669 |
| Document: |
Article ; Prepublicació ; Versió de l'autor |
| Matèria: |
Filogènia ;
Mètodes estadístics ;
Arbres (Teoria dels grafs) |
visitant ::
identificació
