Efficient methods for reconstructing large phylogenies according to the maximum likelihood principle

Molecular phylogenetic reconstruction aim at recovering the evolutionary tree (or phylogeny) of a set of homologous sequences. The maximum likelihood method seems to be the most reliable approach. Unfortunately, the computing time required by classical methods to pinpoint the phylogeny of maximum likelihood quickly becomes unacceptable as the number of sequences increases. Therefore, such methods cannot deal with large data sets. Two kinds of methods are available for reconstructing large phylogenies according to the maximum likelihood principle: distance based methods and quartet methods. Both divide the original problem in sub-problems made of few sequences that they can rapidly solve (according to the maximum likelihood principle). They then combine the solution of those sub-problems in a solution to the original one. After a presentation of main phylogenetic reconstruction methods, we describe a new quartet method (Weight Optimization) that has both better theoretical properties and better topological accuracy than Quartet Puzzling (a widely used quartet method). We then explain why quartet methods are not adapted to infer large phylogenies according to the maximum likelihood principle and how they can be used, efficiently, to solve other kind of problems. Finally, we propose an approach combining distance methods and maximum likelihood in an original way. This approach, called TripleML, improves the reliability of distance-based methods by replacing the distance they use by distances obtained via a local optimization of the likelihood of triplets of taxa (or set of taxa).; La reconstruction de phylogénies moléculaires consiste à retrouver l'arbre évolutif (ou phylogénie) d'un ensemble de séquences homologues. La méthode de reconstruction la plus fiable actuellement, semble être la méthode du maximum de vraisemblance. Les méthodes classiques pour rechercher la phylogénie de vraisemblance maximale deviennent, rapidement, très coûteuses en temps de calcul lorsque le nombre de séquences augmente. Elles ne peuvent donc pas traiter de grandes phylogénies. Actuellement, les deux types de méthodes qui permettent de reconstruire de grandes phylogénies suivant le principe du maximum de vraisemblance sont : les méthodes de distances et les méthodes de quadruplets. Toutes deux divisent le problème initial en sous-problèmes contenant peu de séquences. Elles peuvent alors résoudre rapidement (suivant le principe du maximum de vraisemblance) chacun de ces sous-problèmes, puis combiner les solutions obtenues pour proposer une phylogénie de l'ensemble des séquences. Après avoir présenté les principales méthodes de reconstruction phylogenetique, nous décrivons une nouvelle méthode de quadruplets (Weight Optimization) qui possède de bonnes propriétés théoriques et reconstruit des arbres plus fiables que Quartet Puzzling (une méthode de quadruplets très populaire). Nous expliquons ensuite en quoi les méthodes de quadruplets sont mal adaptées pour reconstruire de grandes phylogénies suivant le principe du maximum de vraisemblance, et comment ces méthodes peuvent résoudre efficacement d'autres problèmes. Puis, nous proposons une approche qui combine de manière originale les méthodes de distances et du maximum de vraisemblance. Cette approche que nous appelons TripleML permet d'améliorer la fiabilité de différentes méthodes de distances en remplaçant les distances qu'elles utilisent par des distances qui sont estimées en optimisant localement la vraisemblance de triplets de séquences (ou de groupes de séquences).