Best Match Graphs

Ponente(s): Alitzel López Sánchez

Un árbol filogenético es un grafo sin ciclos que no contiene nodos internos de grado dos, y en el cual las hojas representan entidades biológicas, tales como genes. A partir de las relaciones que guardan los genes en este árbol, construimos un grafo donde los nodos representan genes y las aristas esas relaciones entre ellos. A este grafo le llamamos the Best Match Graph. Sea T un árbol filogenético y S una asignación de las hojas de T a un conjunto de especies, un best match graph es un grafo dirigido que tiene un arco que va de x a y si los genes x y y residen en especies diferentes y y es uno de los posibles parientes evolutivamente cercanos de x comparado con todos los demás genes contenidos en la especie S(y). En esta contribución, presentamos una caracterización de los best match graphs así como también se demuestra que podemos saber en un tiempo cúbico y espacio cuadrático si un grafo (G,S) es un best match graph. Si es así, entonces existe un único Árbol Filogenético Mínimamente Resuelto que explica (G,S) , el cual puede ser construido en tiempo cúbico.