L'inférence de phylogénies à partir de matrices de distance multiples (stage M2 ou thèse)

Encadrants: Fabio Pardi et Olivier Gascuel

Contexte et résumé: Une phylogénie représente l’évolution d’une collection d’organismes, de gènes ou d’objets biologiques en général, typiquement sous forme d'un arbre. Les phylogénies sont aujourd’hui reconstruites à partir de séquences moléculaires (ADN ou protéines) et trouvent un grand nombre d’applications en biologie, depuis l’étude des épidémies jusqu’à la prédiction de la fonction des gènes en passant par les études de biodiversité. Les méthodes de distance constituent une approche classique pour inférer rapidement les phylogénies [1,2]. Elles se basent sur une matrice contenant des estimations des distances évolutives entre chaque paire de séquences. On propose dans ce stage/thèse de généraliser ces méthodes au cas où plusieurs matrices sont données, typiquement pour répondre au cas où chaque matrice est estimée à partir d’une région génomique différente. Dans le cadre d'une thèse on traitera aussi le cas où, à cause de la recombination entre genomes (très commune par exemple pour les virus), il faut abandonner la représentation classique d’arbre phylogénétique pour adopter celle de réseau phylogénétique.

Mots clés: algorithmique, algèbre linéaire, régression linéaire, programmation, phylogénomique.

Full description: Traditionally, phylogenies have been inferred from sequence datasets of moderate size, consisting of one gene per organism. The tree inferred from this gene’s copies across the organisms was taken as the phylogeny of those organisms. As genome sequencing techniques become more and more efficient, the inference of phylogenies is increasingly made on the basis of data coming from large numbers of genomic regions. The problem then arises of how to use efficiently all this information. As an alternative to the main approaches that have been proposed for this task (e.g. the ‘supermatrix’ and the ‘supertree’ approach), we intend to pursue the idea of using a collection of distance matrices, one per genomic region across the different organisms. This idea has already been explored by Criscuolo et al. [3], who attacked this problem by combining all the input matrices into a single matrix, to be analyzed with classical distance methods. Now, instead, we would like to modify the distance methods themselves, so as to make them able to deal with multiple matrices: the goal is to find the tree (or network) that best fits the given matrices, for instance by optimizing a weighted least-squares criterion, generalizing the well-known case of a single distance matrix [2]. The first step will be to study the analytic solvability of optimizing such criteria and the efficiency of the resulting algorithms [4]. Then the algorithmics of the search for an optimal phylogeny will also be tackled [1]. Particularly challenging (but this will only be tackled by PhD candidates) is the case of phylogenetic networks, for which there may be multiple optimal branch length assignments, and which has a much larger search space (even when we constrain the network to only have one cycle). The student will work on the mathematics and algorithmics of these problems and will develop tools that will be applied to real biological data.

Collaborations: the developed methods will be applied to virus, mammalian and plant genomes, in collaborations with the IRD (Institut de Recherche pour le Développement), the ISEM (Institut des Sciences de l'Evolution de Montpellier) and the CIRAD (Centre de coopération internationale en recherche agronomique), respectively.

[1] Desper R, Gascuel O. The minimum evolution distance-based approach to phylogenetic inference, in Gascuel O. (ed.) Mathematics of Evolution and Phylogeny (2005) [pdf]

[2] Felsenstein J. Inferring phylogenies. Chapter 11 (2004)

[3] Criscuolo A, Berry V, Douzery EJP, Gascuel O. SDM: a fast distance-based approach for (super)tree building in phylogenomics, Systematic Biology 55: 740-755 (2006) [pdf]

[4] Bryant D, Waddell P. Rapid evaluation of least-squares and minimum-evolution criteria on phylogenetic trees, Molecular Biology and Evolution 15: 1346-1359 (1998) [pdf]