Principales méthodes de reconstruction phylogénétique

Principales méthodes de reconstruction phylogénétique

Recherche de l’arbre optimum

Les méthodes de reconstruction phylogénétique reposent presque toujours sur l’optimisation d’un critère permettant de comparer les phylogénies possibles d’un ensemble de taxons. Comme nous l’avons vu au chapitre précédent, le nombre de phylogénies possibles pour un ensemble de n taxons est 3 5 7 × × × × − … ( n 2 5 ) (équation (1) page 13), et ce nombre augmente très rapidement en fonction de n. Dès que le nombre de taxons étudiés dépasse une dizaine, il est impossible de considérer toutes les phylogénies possibles pour en trouver une qui soit optimale pour le critère considéré.

Néanmoins, pour certains critères, par exemple celui optimisé par l’algorithme Q* (Berry et Gascuel 2000), il est possible de trouver un arbre optimal en un temps polynomial. Cependant, pour la plupart des critères utilisés en reconstruction phylogénétique, la recherche d’un arbre optimal est un problème NP-difficile (Foulds et Graham 1982 ; Steel 1992). Dans ce cas, il est nécessaire d’utiliser une heuristique, de manière à proposer un arbre « satisfaisant » au sens du critère choisi, en un temps raisonnable.

Cette partie décrit les quatre approches sur lesquelles reposent la majorité des heuristiques utilisées en reconstruction phylogénétique pour chercher un arbre optimal. Les deux premières sont des processus de construction gloutons permettant d’obtenir un arbre satisfaisant au sens du critère considéré. Les deux autres approches effectuent des améliorations itératives permettant de garantir que l’arbre proposé est au moins un optimum local. 

Processus agglomératif

Dans cette approche, on considère initialement une phylogénie complètement irrésolue qui contient un seul nœud interne relié à chacun des taxons étudiés. A chaque étape, la phylogénie courante contient un seul nœud interne u de degré supérieur à trois ; deux voisins de ce nœud particulier sont choisis pour être agglomérés. Pour réaliser cette agglomération, on ajoute un nouveau nœud interne dont les trois voisins sont les deux nœuds agglomérés et le nœud u.

A chaque étape le nombre de voisins du nœud n diminue et le processus s’arrête lorsque u n’a plus que trois voisins. L’agglomération choisie est celle qui permet d’obtenir la meilleure phylogénie partiellement résolue au sens du critère 2.1 Recherche de l’arbre optimum 31 considéré. Le processus s’arrête lorsque l’on obtient une phylogénie complètement résolue ou lorsque le critère n’est amélioré par aucune des agglomérations possibles. La Figure 4 montre comment on peut obtenir la phylogénie complètement résolue de la Figure 1.b (page 12) en suivant ce processus agglomératif.

Figure 4 : processus d’agglomération 5 3 2.1.2 Processus d’insertion Le processus d’insertion construit un arbre phylogénétique à partir d’une phylogénie à trois taxons sur laquelle sont successivement greffés les autres taxons. La branche sur laquelle le nouveau taxon est inséré est choisie de manière à ce que la phylogénie partielle ainsi obtenue soit la meilleure possible au sens du critère considéré. La Figure 5 illustre la manière dont l’arbre de la Figure 1.b (page 12) peut être obtenu en suivant un processus d’insertion. 32 Chapitre 2 Principales méthodes de reconstruction phylogénétique 

Ré-arrangement d’arbres Lorsque l’on construit un arbre suivant un processus d’insertion ou d’agglomération, les choix effectués à une étape ne sont jamais remis en cause par la suite. Une fois qu’un taxon est inséré, il ne change plus de position par la suite. Ces approches « gloutonnes », où les choix sont définitifs, ont l’avantage d’être rapides, mais ne reconstruisent que rarement l’arbre optimum. Il est possible d’améliorer l’arbre reconstruit par un processus d’amélioration itérative en testant des ré-arrangements possibles de cet arbre.

Si l’une de ces modifications de l’arbre améliore le critère que l’on cherche à optimiser, alors on conserve ce nouvel arbre. On teste ensuite les ré-arrangements possibles de ce nouvel arbre. Le processus s’arrête lorsqu’il n’est plus possible d’améliorer l’arbre en lui faisant subir un des ré-arrangements que l’on a définis comme étant possibles. Pour les méthodes utilisant ce type d’approche, le temps de calcul dépend donc notamment du nombre de réarrangements effectués, ce qui complique l’analyse de leur complexité en temps de calcul.