Améliorations et limites des méthodes de quadruplets

Comme nous l’avons vu, la méthode de maximum de vraisemblance est actuellement la méthode de référence en reconstruction phylogénétique. Cette méthode statistique offre des garanties théoriques solides et reconstruit des phylogénies fiables. Plusieurs améliorations de la version originale (Felsenstein  est certainement celle, décrite dans le chapitre précédent (§ 2.4.4), de FASTDNAML (Olsen et al. 1994). Malgré tout, ces méthodes de maximum de vraisemblance restent coûteuses en temps de calcul et ne peuvent traiter que des jeux de données de taille faible. Dès que le nombre n de taxons traités devient important, il est beaucoup plus rapide d’utiliser le maximum de vraisemblance pour résoudre tous les problèmes portant sur 4 de ces n taxons, que de l’utiliser pour résoudre directement le problème sur n taxons. En combinant les résultats obtenus par maximum de vraisemblance sur 4 taxons, les méthodes de quadruplets essayent de profiter de la force du maximum de vraisemblance en un temps de calcul raisonnable. La méthode de quadruplets proposée par (Strimmer et Von Haeseler 1996) semblait particulièrement prometteuse. En effet, lors des premiers tests effectués par ses auteurs, les arbres reconstruits par Quartet Puzzling (QP) étaient presque aussi fiables que ceux reconstruits par DNAML. De plus, ses auteurs ont fait un travail important de développement pour permettre d’utiliser QP avec de très nombreux modèles d’évolution et assurer la compatibilité de QP avec les programmes existants. Pour toutes ces raisons, QP est encore actuellement la méthode de quadruplets la plus utilisée.

Cependant, nos travaux ont permis de mettre en évidence certaines faiblesses de cette méthode. En particulier, QP tend à reconstruire des arbres ayant une topologie particulière. Pour palier ces faiblesses, nous avons proposé plusieurs modifications qui améliorent les performances et les propriétés théoriques de QP ; la méthode ainsi obtenue est appelée Weight Optimization (WO). Grâce à ces améliorations, et à l’augmentation de la puissance des machines, nous avons pu tester de manière plus intensive les performances de ces méthodes de quadruplets et les comparer avec celles obtenues par des méthodes de distances et de maximum de vraisemblance. Ces tests nous ont permis de montrer que ces méthodes de quadruplets sont paradoxalement moins fiables que les méthodes de distances tout en nécessitant un temps de calcul bien plus élevé. Ce chapitre présente nos travaux sur les méthodes de quadruplet en s’appuyant sur l’article (Ranwez et Gascuel 2001a) qui constitue l’annexe 1 de cette thèse, et sur l’article (Ranwez et Gascuel 2001b) qui constitue l’annexe 2. Dans un premier temps, nous décrivons les principales méthodes de quadruplets existantes. Dans un second temps, nous détaillons plus particulièrement l’algorithme QP (Strimmer et Von Haeseler 1996), et nous mettons en évidence plusieurs faiblesses de cet algorithme. Puis, nous décrivons l’algorithme WO (Ranwez et Gascuel 2001a) en soulignant les différences existantes entre WO et QP. Nous comparons ensuite ces méthodes de quadruplets avec les autres méthodes de reconstruction phylogénétique et nous analysons les limites des méthodes de quadruplets.

Méthodes de quadruplets

Nous commençons par présenter les avantages pratiques des méthodes de quadruplets. Puis nous détaillons la manière dont le calcul de la vraisemblance se simplifie pour un 4-arbre. Nous présentons ensuite différentes méthodes existantes pour combiner les 4-arbres obtenus en une phylogénie globale. Ces méthodes sont regroupées en fonctions du type d’information qu’elles prennent en compte pour chaque quadruplet. Les phylogénies contenant deux ou trois taxons ont toutes la même topologie ; elles ne contiennent que des bipartitions triviales. En utilisant des phylogénies portant sur deux ou trois taxons, on ne dispose d’informations que sur les distances qui les séparent et non sur la manière dont ces taxons se regroupent. Il est donc nécessaire de considérer au moins quatre taxons pour disposer d’informations topologiques. Pour chaque quadruplet {,2, , }134, il existe trois 4-arbres différents, et chaque 4-arbre contient une seule bipartition non- triviale qui est induite par la seule arête interne du 4-arbre. On note, 12|34 le 4-arbre dont l’arête interne sépare les taxons 1 et 2 des taxons 3 et 4. La Figure 14 résume ces différentes remarques. Premièrement, le nombre de topologies différentes pour une phylogénie ayant n feuilles augmente de manière exponentielle en fonction de n. Il est donc, en général, impossible d’examiner toutes les topologies possibles pour le problème initial. Par contre il n’y a que trois 4-arbres possibles pour un quadruplet. Pour un ensemble de n taxons, il est donc assez rapide de considérer tous les 4-arbres possibles, il y en a 3 × C4