Resumen de New results on old and new balance indices

Tomás Martínez Coronado

• español

  La principal motivación tras el estudio cuantitativo de las formas subyacentes a los árboles filogenéticos es la creencia de que reflejan propiedades de los procesos evolutivos que los han derivado. La contribución de nuestra investigación es la adición, al conjunto de técnicas cuantitativas existentes, de dos nuevos índices de equilibrio, además de probar algunos resultados sobre dos antiguos índices de equilibrio.

  El valor mínimo del índice de Colless, junto con los árboles que lo alcanzan, han sido desconocidos desde la introducción de éste en 1982. Nosotros resolvemos este problema, presentando una caracterización completa de dichos árboles, así como fórmulas cerradas para calcular su valor mínimo. Además, presentamos un nuevo índice de equilibrio para árboles binarios, el índice de Colless Cuadrático, definido como la suma de los cuadrados, y no de los valores absolutos, de la diferencia entre los números de hojas de los subárboles enraizados en cada nodo interno de un árbol dado. Esta nueva medida resulta ser más fácil de manipular, y hemos demostrado que el árbol máxime equilibrado y el árbol oruga son exactamente los árboles que alcanzan sus valores mínimo y máximo, respectivamente. También probamos que tiene mejores propiedades estadísticas, y calculamos su esperanza y varianza bajo los modelos de Yule y Uniforme.

  En su artículo fundacional de 1972, Sackin propuso el uso de la variación de la profundidad de las hojas como medida del equilibrio de un árbol. Aunque esta medida fue más o menos popular en las décadas de 1970 y 1980, nunca se estudió en profundidad y ha sido casi completamente olvidada. Estudiamos algunas de sus propiedades, caracterizando los árboles alcanzando su valor máximo como los árboles oruga, y presentando un algoritmo casi-lineal para construir aquellos que alcanzan su valor mínimo. Sin embargo, también demostramos que estos últimos casi nunca son máxime equilibrados. Acabamos el capítulo proporcionando fórmulas cerradas para su esperanza bajo los modelos de Yule y Uniforme, además de la varianza de los índices de Sackin y Cofenético y el Área Total bajo el modelo Uniforme.

  En el último de los capítulos centrales de esta memoria introducimos un nuevo índice de equilibrio para árboles multifurcados: el índice de Cuartetos. Encontramos los árboles multifurcados y binarios que alcanzan sus valores extremos: los árboles estrella y oruga en el primer caso, y los máxime equilibrados y oruga en el segundo. También damos una recurrencia para calcular su valor máximo para árboles binarios. Así, probamos que su rango de valores es el mayor de entre los índices de equilibrio existentes en la literatura. Además, calculamos su esperanza y varianza bajo los modelos probabilísticos de árboles filogenéticos $\beta$ y $\alpha$-$\gamma$. Por lo que sabemos, es el primer índice topológico de árboles filogenéticos del que se conocen sus primeros momentos bajo el modelo $\alpha$-$\gamma$. Finalmente, señalamos que este índice puede ser fácilmente generalizado a otras familias de grafos dirigidos preservando sus buenas propiedades estadísticas.

• català

  La principal motivació rere l'estudi quantiatiu de les formes subjacents als arbres filogenètics és la creença que aquestes reflecteixen propietats dels procesos evolutius de què es deriven. La contribució de la nostra recerca és l'adició, al conjunt de tècniques quantitatives existents, de dos nous índexos d'equilibri, a més de provar alguns resultats sobre dos d'antics.

  El valor mínim de l'índex de Colless, així com els arbres que l'assoleixen, han sigut desconeguts des de la introducció d'aquest en 1982. Nosaltres resolem aquest problema tot presentant una caracterització completa d'aquests arbres, així com fórmules tancades per a calcular el seu índex de Colless. A més, presentam un nou índex d'equilibri, l'índex de Colless Quadràtic, definit com la suma dels quadrats, i no dels valors absoluts, de les diferències entre els nombres de fulles dels subarbres arrelats a cada node interior d'un arbre donat. Aquesta nova mesura resulta ser més fàcil de manipular i hem sigut capaços de demostrar que l'arbre màximament equilibrat i l'arbre eruga són exactament els arbres que assoleixen els seus valors mínim i màxim, respectivament. També provam que té millors propietats estadístiques, i en calculam l'esperança i variància sota els models de Yule i Uniforme.

  Al seu article fundacional de 1972, Sackin va proposar l'ús de la variació de la profunditat de les fulles com a mesura de l'equilibri d'un arbre. Encara que aquesta mesura va ser més o menys popular als decenis de 1970 i 1980, mai se va estudiar en detall i ha sigut quasi completament oblidada. N'estudiam alguna de les propietats, caracteritzant els arbres binaris que en prenen el valor màxim com les erugues, i donant-ne un algorisme quasi-lineal per a construir aquells arbres que prenen el seu valor mínim. No obstant, també demostram que aquests darrers gairebé mai no són màximament equilibrats. Acabam el capítol proporcionant fórmules tancades per a la seva esperança sota els models de Yule i Uniforme, a més de la variància dels índexos de Sackin i Cofenètic i el Àrea Total sota el model Uniforme.

  En el darrer dels capítols centrals d'aquesta memòria, introduïm un nou índex d'equilibri per a arbres multifurcats: l'índex de Quartets. Trobam els arbres multifurcats i binaris que assoleixen els seus valors extrems: els arbres estrella i eruga en el primer cas, i els arbres màximament equilibrats i eruga en el segon. També donam una recurrència per a calcular el seu valor màxim per a arbres binaris. Així, provam que el seu rang de valors és el més gran d'entre els índexos de equilibri existents a la literatura. A més, calculam la seva esperança i variància sota els models probabilístics d'arbres filogenètics $\beta$ i $\alpha$-$\gamma$. Pel que sabem, aquest és el primer índex topològic d'arbres filogenètics del qual es coneixen els primers moments sota el model $\alpha$-$\gamma$. Finalment, indicam que aquest índex pot ser fàcilment generalitzat a altres famílies de grafs dirigits tot preservant les seves propietats estadístiques.

• English

  The main motivation behind the quantitative study of phylogenetic tree shapes is the belief that they reflect properties of the evolutionary processes that have derived them. The contribution of our research is the addition, to the existing set of quantitative techniques in this field, of two new balance indices, as well as the proof of some results concerning two old ones.

  The minimum value of the Colless index, as well as the trees attaining it, have been unknown ever since the introduction of this index in 1982. We solve this problem by providing a full characterization of these trees and closed formul\ae\ for the minimum value of the Colless index. We also introduce a new balance index for bifurcating trees, the Quadratic Colless index, defined as the sum of the squares, not the absolute values, of the difference in the number of leaves of the subtrees rooted at each internal node of a given tree. This new measure happens to be easier to manipulate, and we have proved that the maximally balanced tree and the caterpillar are exactly the trees attaining its minimum and maximum values, respectively. We also show that it has better statistical properties than those of the original Colless index, and we have been able to compute its expected value and variance under both the Yule and Uniform models.

  In his 1972 paper on tree balance, Sackin proposed the use of the variation of the leaves' depths as a measure of the balance of a tree. Although somewhat popular in the decades of 1970 and 1980, this measure was never thoroughly studied and is now almost completely forgotten. We study some of its properties, characterizing the trees attaining its maximum value as being the caterpillars, and providing a quasi-linear algorithm to compute the bifurcating trees attaining its minimum value. Nevertheless, we also show that these are almost never maximally balanced. We also provide closed formul\ae\ for its expected value under the Uniform and Yule models, as well as for the variance of the Sackin and Cophenetic indices and the Total Area under the Uniform model.

  In the last of the central chapters of this memoir we introduce a new balance index for multifurcating trees: the Quartet index. We find the multifurcating and bifurcating trees attaining its extreme values: exactly the stars and caterpillars in the multifurcating case, and the maximally balanced trees and the caterpillars in the bifurcating case. We also give a recurrence to compute its maximum value for bifurcating trees. Thus, we prove that its range of values is the largest among the balance indices existing in the literature. Furthermore, we give its expected value and variance under both the $\beta$ and $\alpha$-$\gamma$ probabilistic models for phylogenetic trees. To our knowledge, this is the first shape index for phylogenetic trees whose first moments under the $\alpha$-$\gamma$-model are known. We end this chapter by pointing out that this index can be easily generalized to other families of directed graphs and still preserve its good statistical properties.