Un esquema de aproximación de tiempo polinómico para inferir árboles evolutivos a partir de topologías de cuartetos y su aplicación

Inferir árboles evolutivos ha sido durante mucho tiempo un problema desafiante tanto para biólogos como para científicos de la computación. En los últimos años, la investigación se ha centrado en el paradigma del método de cuartetos para inferir árboles evolutivos. Los métodos de cuartetos proceden primero a inferir la historia evolutiva para cada conjunto de cuatro especies (resultando en un conjunto Q de topologías de cuarteto inferidas) y luego recombinan estas topologías de cuarteto inferidas para formar un árbol evolutivo. Este documento presenta dos resultados sobre el paradigma del método de cuartetos. El primero es un esquema de aproximación de tiempo polinómico (PTAS) para recombinar las topologías de cuarteto inferidas de manera óptima. Este es un resultado importante ya que, hasta la fecha, no ha habido algoritmos de tiempo polinómico con garantías de rendimiento para métodos de cuartetos. Para lograr este resultado, se explota la densidad natural del conjunto Q. El segundo resultado es una nueva técnica, llamada limpieza de cuartetos, que detecta y corrige errores en el conjunto Q con garantías de rendimiento. Este resultado tiene una importancia particular ya que los métodos de cuartetos suelen ser muy sensibles a errores en los datos. Se muestra cómo la limpieza de cuartetos puede aumentar dramáticamente la precisión de los métodos de cuartetos.