Best Match Graphs: un problema de eventos evolutivos en genes

Ponente(s): Maribel Hernández Rosales, Alitzel López, Dulce Valdivia

Un árbol filogenético es un árbol cuyos nodos internos tienen grado mayor o igual a 3, a excepción de la raíz que puede tener grado 2 y de las hojas que tienen grado 1. Este árbol describe la historia evolutiva de un conjunto de entidades biológicas. En este trabajo, nos enfocamos particularmente en los árboles filogenéticos de genes, donde las hojas del árbol representan genes existentes y los nodos internos genes ancestrales. Un grafo best match es un grado dirigido en donde existe un arco de x a z, si los genes en el árbol filogenético residen en diferentes especies, y además, z es uno de los muchos genes más cercanos evolutivamente comparado con todos aquéllos genes que residen en la misma especie que z. En este trabajo caracterizamos los grafos best match y mostramos que se pueden saber en tiempo cúbico y espacio cuardrático si un grafo es derivado de un árbol filogenético.