Approximating subtree distances between Phylogenies

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.

Modelo de cuentas estelares de la Vía Láctea

Son muchos los estudios que se han realizado sobre la Vía Láctea. El Grupo de Investigación de Morfología y Dinámica de la Vía Láctea del Instituto de Astrofísica de Canarias (IAC) ha realizado numerosos trabajos acerca de la estructura galáctica, entre los cuales son de especial relevancia los relativos a la estructura del disco fino, el bulbo y la barra larga. Sin embargo, el grupo carece de un código propio que unifique en un modelo común el conocimiento actual de la estructura galáctica. En este proyecto de final de carrera se presenta la implementación de un código informático de un modelo de cuentas estelares de la Vía Láctea realizado en colaboración con investigadores del IAC.