Algebraic and semi-algebraic phylogenetic reconstruction

Abstract

Phylogenetics is the study of the evolutionary history and relationships among groups of biological entities (called taxa). The modeling of those evolutionary processes is done by phylogenetic trees whose nodes represent different taxa and whose branches correspond to the evolutionary processes between them. The leaves usually represent contemporary taxa and the root is their common ancestor. Nowadays, phylogenetic reconstruction aims to estimate the phylogenetic tree that best explains the evolutionary relationships of current taxa using solely information from their genome arranged in an alignment. We focus on the reconstruction of the topology of phylogenetic trees, which means reconstructing the shape of the tree considering labels at the leaves.To this end, one usually assumes that DNA sequences evolve according to a Markov process ruled by a prescribed model of nucleotide substitutions. These substitution models specify some transition matrices at the edges of the tree and a distribution of nucleotides at the root. Given a tree T and a substitution model, one can compute the distribution of nucleotide patterns at the leaves of T in terms of the model parameters. This joint distribution is represented by a vector whose entries can be expressed as polynomials on the model parameters and satisfy certain algebraic relationships. The study of these relationships and the geometry of the algebraic varieties defined by them (called phylogenetic varieties) have provided successful insight into the problem of phylogenetic reconstruction. However, from a biological perspective we are not interested in the whole variety, but only in the region of points that arise from stochastic parameters (the so-called phylogenetic stochastic region). The description of these regions leads to semi-algebraic constraints which play an important role since they characterize distributions with biological and probabilistic meaning. One of the main motivations for this thesis follows from the following question. Could the use of semi-algebraic tools improve the already existent algebraic tools for phylogenetic reconstruction?To answer this question, we compute the Euclidean distance of data points arising from an alignment of nucleotide to the phylogenetic varieties and their stochastic regions in a some scenarios of special interest in phylogenetics, such as trees with short external branches and/or subject to the long branch attraction phenomenon. In some cases, we compute these distances analytically and we can decide which tree has stochastic region closer to the data point. As a consequence, we can prove that, even if the data point was close to the phylogenetic variety of a given tree, it might be closer to the stochastic region of another tree. In particular, considering the stochastic phylogenetic region seems to be fundamental to cope with the phylogenetic reconstruction problem when dealing with the long branch attraction phenomenon.However, incorporating semi-algebraic tools into phylogenetic reconstruction methods can be extremely difficult and the procedure to do it is not evident at all. In this thesis, we present two phylogenetic reconstruction methods that combine algebraic and semi-algebraic conditions for the general Markov model. The first method we present is SAQ, which stands for Semi-Algebraic Quartet reconstruction method. Next, we introduce a more versatile method, ASAQ (for Algebraic and Semi-Algebraic Quartet reconstruction method}), which combines SAQ with the method Erik+2 (based on certain algebraic constraints). Both are phylogenetic reconstruction methods for DNA alignments on four taxa which have been proven to be statistically consistent.We test the suggested methods on simulated and real data to check their actual performance in several scenarios. Our simulation studies show that both methods SAQ and ASAQ are highly successful, even when applied to short alignments or data that violates their assumptions.

La filogenètica és l'estudi de la història evolutiva entre grups d'entitats biològiques (anomenades tàxons). Aquests processos evolutius estan modelitzats per arbres filogenètics els nodes dels quals representen diferents tàxons i les branques corresponen als processos evolutius entre ells. Les fulles normalment representen tàxons actuals i l'arrel és el seu avantpassat comú. Actualment, la reconstrucció filogenètica pretén estimar l'arbre filogenètic que millor explica les relacions evolutives de tàxons actuals utilitzant únicament informació del seu genoma organitzada en un alineament. En aquesta tesi ens centrem en la reconstrucció de la topologia dels arbres filogenètics, és a dir, reconstruir la forma de l'arbre tenint en compte els noms associats a les fulles. Amb aquesta finalitat, assumim que les seqüències d'ADN evolucionen segons un procés de Markov d'acord amb un model de substitució de nucleòtids. Aquests models de substitució assignem matrius de transició a les arestes d’un arbre i una distribució de nucleòtids a l'arrel. Donat un arbre i un model, es pot calcular la distribució de les possibles observacions de nucleòtids a les fulles en termes dels paràmetres del model. Aquesta distribució conjunta s’expressa en forma de vector, les entrades del qual es poden escriure com polinomis en funció dels paràmetres del model i satisfan certes relacions algebraiques. L'estudi d'aquestes relacions i de la geometria de les varietats algebraiques que defineixen (anomenades varietats filogenètiques) han servit per entendre millor el problema de la reconstrucció filogenètica. No obstant això, des d'una perspectiva biològica no estem interessats en tota la varietat, sinó només en la regió de punts que resulten de paràmetres estocàstics (l'anomenada regió estocàstica). La descripció d'aquestes regions condueix a restriccions semi-algebraiques que tenen un paper important ja que caracteritzen les distribucions amb significat biològic. Una de les principals motivacions d'aquesta tesi és la següent: Podria l'ús d'eines semi-algebraiques millorar les eines algebraiques ja existents per a la reconstrucció filogenètica? Per poder respondre, calculem la distància euclidiana entre punts de dades obtinguts a partir d’un alineament i varietats filogenètiques i les seves regions estocàstiques en escenaris d'especial interès en la filogenètica. En alguns casos, podem calcular aquestes distàncies de forma analítica i això ens permet demostrar que, fins i tot si un punt de dades fos proper a la varietat filogenètica d'un arbre donat, podria estar més a prop de la regió estocàstica d'un altre arbre. En particular, considerar la regió estocàstica sembla ser fonamental per fer front al problema de la reconstrucció filogenètica quan tractem amb del fenomen d'atracció de branques llargues. Tot i això, incorporar d'eines semi-algebraiques en els mètodes de reconstrucció filogenètica pot ser extremadament difícil i el procediment per fer-ho no és gens evident. En aquesta tesi, presentem dos mètodes de reconstrucció filogenètica que combinen condicions algebraiques i semi-algebraiques per al model general de Markov. El primer mètode que presentem és el SAQ, que rep el nom de Semi-Algebraic Quartet reconstruction method. A continuació, introduïm un mètode més versàtil, l'ASAQ (Algebraic and Semi-Algebraic Quartet reconstruction method), que combina el SAQ amb el mètode Erik+2 (basat en certes restriccions algebraiques). Tots dos són mètodes de reconstrucció filogenètica per a alineaments d'ADN per quatre tàxons i hem demostrat que tots dos són estadísticament consistents. Finalment, testem els mètodes proposats amb dades simulades i dades reals per comprovar el seu rendiment en diversos escenaris. Les nostres simulacions mostren que ambdós mètodes SAQ i ASAQ obtenen