Árboles Filogenéticos: Grafos Hoja-potencias

MARISA GUTIERREZ; MARÍA PÍA MAZZOLENI

Tandil

Congreso; LX Reunión Anual de Comunicaciones Científicas. 2010; 2010

El presente trabajo está basado en el survey de A. Brandstadt: "Leaf Powers, Phylogenetic Trees and Substitution of Clique".   Un problema fundamental en biología es reconstruir la evolución histórica de un conjunto de especies basándose en datos biológicos cuantitativos. Generalmente, la historia de la evolución es modelada por un árbol de evolución denominado filogénea, el cual es un  árbol cuyas hojas representan especies y cada vértice interno da origen a dos o más especies nuevas.   Se dan los conceptos de k-hoja raíz y k-hoja raíz básica los cuales son necesarios para tratar este tipo de problemas.   Un árbol T es una k-hoja raíz de un grafo finito no dirigido G=(V,E) si el conjunto de hojas de T es V y para cualesquiera dos vértices x e y vértices de G, xy adyacentes en G si y sólo si la distancia de x e y en T es a lo sumo k. Un grafo G es una k-hoja potencia si tiene una k-hoja raíz; éste es una hoja potencia si tiene una hoja raíz para algún k >1.   Una k-hoja raíz T de una k-hoja potencia G es básica si todo vértice interno de T es adyacentea lo sumo a una hoja. Una k-hoja potencia es básica si tiene una k-hoja raíz básica.   Además, se dan algunos resultados básicos de grafos hoja potencia, y de la sustitución de completos en grafos hoja potencia básicos. En particular, se estudia la estructura de las 3-hoja potencia y de las 4-hoja potencia básicas.   Se observa que los grafos 5-hoja potencia son muy difíciles de caracterizar, aunque actualmente se ha descubierto un algoritmo de tiempo lineal para reconocerlos. Mientras que la caracterización de k-hoja potencias para k> 5 es un problema que queda abierto.