New balance indices and metrics for phylogenetic trees

Abstract

[eng] The belief that the shape of a phylogenetic tree re ects the properties of the evolutionary processes underlying it has motivated the study of indices quantifying the graph-theoretical properties of phylogenetic trees and of metrics allowing for their comparison. The main contribution of this PhD Thesis is then the addition to the set of available techniques for the analysis and comparison of phylogenetic trees of the total cophenetic balance index, the family of Collesslike balance indices, and the family of cophenetic metrics. The total cophenetic index turns out to be a good alternative to other popular balance indices like Sackin's and Colless' indices. This index is de ned for multifurcating trees and it achieves its maximum value exactly at the combs and its minimum value among the multifurcating trees exactly at the star trees and among the bifurcating trees at the maximally balanced trees, being the rst balance index published in the literature satisfying this last property. We have computed closed formulas for its expected value under the Yule and the uniform models of bifurcating phylogenetic tree growth and a simple recurrence for its variance under the uniform model. As a by-product of this study, we have obtained a closed formula for the expected value of the Sackin index under the uniform model, a problem that remained open so far. The Colless-like indices provide the rst sound extension to multifurcating trees of the Colless index for bifurcating trees, in the sense that, when restricted to bifurcating trees, they give the classical Colless index up to a constant factor, and, for any given number of leaves, the only multifurcating trees that yield their minimum value are exactly the fully symmetric. These Colless-like indices depend on the choice of a dissimilarity function and of a size of rooted trees, and we show that this choice may a ect how they measure the balance of a tree. In connection with these indices, we introduce in this Thesis our R package \CollessLike", available on the CRAN, that allows to perform goodness of t tests of a phylogenetic tree with null model any - -model. Finally, we have de ned the family of cophenetic metrics d';p, with p 2 f0g [ [1;1[, for phylogenetic trees with possibly nested taxa and weights on the arcs. On di erent types of spaces of non-weighted trees, we have computed their least non-zero value, the order of their diameter, and the neighborhood of any given tree. Moreover, we have obtained closed formulas for the expected value under the Yule and the uniform models of the square of the metric d';2.

[spa] La creencia que la forma de un arbol logen etico es un re ejo de las propiedades de los procesos evolutivos subyacentes ha motivado el estudio de ndices que cuanti quen las propiedades gr a cas de un arbol logen etico y de las m etricas que permitan la comparaci on de arboles logen eticos. La principal contribuci on de esta tesis doctoral es entonces la incorporaci on al conjunto de t ecnicas disponibles para el an alisis y la comparaci on de arboles logen eticos del ndice de balance cofen etico total, la familia de ndices de balance Colless-like y la familia de m etricas cofen eticas. El ndice cofen etico total resulta ser una buena alternativa a otros ndices populares de balance como los ndices de Sackin y Colless. Este ndice est a de nido para arboles no binarios, y alcanza su valor m aximo exactamente en los arboles de tipo peine y su valor m nimo entre los arboles arbitrarios exactamente en los arboles estrella y entre los arboles binarios en los m aximo balanceados, siendo el primer ndice de balance publicado que satisface esta ultima propiedad. Hemos calculado f ormulas expl citas para su valor esperado bajo los modelos de Yule y uniforme de crecimiento de arboles logen eticos binarios y una recurrencia simple para su varianza bajo el modelo uniforme. En el decurso de este estudio, hemos obtenido una f ormula expl cita para el valor esperado del ndice de Sackin bajo el model uniforme, un problema que a un permanec a abierto. La familia de los ndices Colless-like proporciona la primera extensi on s olida a arboles logen eticos arbitrarios del ndice de Colless cl asico para arboles binarios, en el sentido de que cuando se restringen a arboles binarios coinciden con el ndice de Colless cl asico salvo un factor constante y, para cualquier n umero de hojas, los unicos arboles que alcanzan su valor m nimo son exactamente los totalmente sim etricos. Estos ndices dependen de la elecci on de una funci on de disimilitud y de un tama~no de arboles, y mostramos que esta elecci on puede afectar la forma en que miden el balance del arbol. En relaci on con estos ndices, presentamos en esta tesis nuestro paquete de R \CollessLike", disponible en la CRAN, que permite realizar pruebas de bondad de ajuste de un arbol logen etico con cualquier modelo - para arboles no binarios como modelo nulo. Finalmente, hemos de nido la familia de las m etricas cofen eticas d';p, con p 2 f0g [ [1;1[, para arboles logen eticos con, posiblemente, nodos interiores etiquetados y pesos en las aristas. Para diferentes tipos de espacios de arboles logen eticos sin pesos en las aristas, hemos calculado el valor m nimo estrictamente positivo de estas m etricas, el orden de magnitud de su di ametro y los entornos de los arboles. Adem as, hemos obtenido f ormulas expl citas para el valor esperado bajo los modelos de Yule y uniforme del cuadrado de la m etrica d';2.

[cat] La creen ca que la forma d'un arbre logen etic es un re ex de les propietats dels processos evolutius que hi ha al darrere ha motivat l'estudi d' ndexs que quanti quin les propietats gr a ques dels arbres logen etics i de m etriques que permetin la seva comparaci o. La contribuci o principal d'aquesta tesi doctoral es aleshores la incorporaci o al conjunt de t ecniques disponibles per a l'an alisi i la comparaci o d'arbres logen etics de l' ndex de balan c cofen etic total, la fam lia d' ndexs Colless-like i la fam lia de m etriques cofen etiques. L' ndex cofen etic total es una bona alternativa a altres ndexs de balan c populars com ara els de Sackin i de Colless. Aquest ndex est a de nit per a arbres no binaris, i assoleix el seu valor m axim exactament als arbres de tipus pinta i el seu valor m nim entre els arbres arbitraris exactament als arbres estrella (no binaris) i entre els arbres binaris exactament als arbres m axim balancejats, sent el primer ndex de balan c publicat que satisf a aquesta darrera propietat. Hem calculat f ormules expl cites per al seu valor esperat sota els models de creixement d'arbres logen etics binaris de Yule i uniforme i una recurr encia simple per a la seva vari ancia sota el model uniforme. Com a part d'aquest estudi, hem obtingut una f ormula expl cita per al valor esperat de l' ndex de Sackin sota el model uniforme, un problema que romania obert. Els ndexs Colless-like s on la primera extensi o s olida publicada per a arbres no binaris de l' ndex de Colless, en el sentit que quan es restringeixen a arbres binaris coincideixen amb l' ndex de Colless cl assic llevat d'un factor constant i, per a cada nombre de fulles, els arbres que assoleixen el seu valor m nim s on exactament els totalment sim etrics. Aquests ndexs depenen de l'elecci o d'una funci o de dissimilitud i d'una mida d'arbres, i mostrem que aquesta tria pot afectar la forma com mesuren el balan c. En relaci o amb aquests ndexs, presentem en aquesta tesi el nostre paquet de R \CollessLike", disponible a la CRAN, que permet realitzar proves de bondat d'ajust d'un arbre logen etic amb qualsevol model - per a arbres no binaris com a model nul. Finalment, hem de nit les m etriques cofen etiques d';p, amb p 2 f0g[[1;1[, per a arbres logen etics amb, potser, nodes interiors etiquetats i pesos a les arestes. Per a alguns tipus d'espais d'arbres logen etics sense pesos a les arestes, hem calculat el valor m nim no nul d'aquestes m etriques, l'ordre de magnitud del seu di ametre i els entorns dels arbres. A m es, donem f ormules explicites per a l'esperan ca sota els models de Yule i uniforme del quadrat de d';2.