© Dunod – Toute reproduction non autorisée est un délit.
83
7.1 • Parcimonie
minimal. La parcimonie ne permet de privilégier aucun de ces arbres. Il est fréquent
de présenter alors l’arbre consensus exact des arbres optimaux. Cela consiste à ne
dessiner que les branches internes partagées par tous les arbres optimaux, les parties
où les arbres sont en désaccord se traduisant par des multifurcations.
7.1.4 Implémentations
Les programmes DNAPARS et PROTPARS du package PHYLIP implémentent le
calcul d’arbre phylogénétique pour les données nucléotidiques et protéiques, respectivement. L’heuristique employée est la suivante :
1. Définir un ordre arbitraire des séquences.
2. Débuter avec les trois premières séquences et leur unique arbre possible.
3. Essayer de greffer la prochaine séquence sur toutes les branches de cet arbre ;
retenir la position de coût minimal.
4. Évaluer tous les voisins NNI de l’arbre courant ; tout voisin de coût inférieur
devient le nouvel arbre courant.
5. Retourner en 3. avec la prochaine séquence tant qu’il en reste une.
6. Évaluer tous les voisins SPR de l’arbre courant ; tout voisin de coût inférieur
devient le nouvel arbre courant.
Avec cette heuristique, un arbre portant sur une trentaine de séquences peut être
calculé en quelques secondes, alors que le calcul exhaustif exact de tous les arbres
possibles serait irréalisable. Donc, cette heuristique n’évalue qu’une partie infime de
tous les arbres possibles. Une stratégie fréquente et efficace est de recommencer
plusieurs fois tout le calcul en changeant à chaque fois aléatoirement l’ordre dans
lequel les séquences sont ajoutées à l’arbre. Il est recommandé de faire 5 à 10 telles
itérations. Très fréquemment, on trouve un arbre de coût inférieur à la 4° ou la 7°
itération. Le programme SeaView utilise DNAPARS et PROTPARS pour ses calculs
par parcimonie.
Le programme PAUP* propose les deux heuristiques NNI et SPR. Il propose aussi
un calcul exact (option Branch and Bound qui ne calcule pas le coût des topologies
dont l’algorithme sait démontrer qu’il sera supérieur à l’optimum courant) qui n’est
faisable que pour un très petit nombre de séquences (≤ 20).
Le programme de parcimonie le plus efficace en termes de vitesse de calcul et
d’efficacité de l’heuristique est TNT (http://www.cladistics.com/aboutTNT.html)
qui peut nécessiter une licence. Il utilise une heuristique très élaborée trop complexe
pour être décrite ici.
7.1.5 Longueurs de branches des arbres de parcimonie
On l’a déjà mentionné, on ne peut pas donner un sens unique à la longueur d’une
branche d’un arbre au sens de la parcimonie, puisque plusieurs longueurs possibles
sont également acceptables. En conséquence, les arbres de parcimonie sont souvent
dessinés avec des branches dont la longueur est arbitraire. Le défaut de cette approche
est qu’il est très difficile de ne pas donner un sens quantitatif à la longueur des branches
83
7.1 • Parcimonie
minimal. La parcimonie ne permet de privilégier aucun de ces arbres. Il est fréquent
de présenter alors l’arbre consensus exact des arbres optimaux. Cela consiste à ne
dessiner que les branches internes partagées par tous les arbres optimaux, les parties
où les arbres sont en désaccord se traduisant par des multifurcations.
7.1.4 Implémentations
Les programmes DNAPARS et PROTPARS du package PHYLIP implémentent le
calcul d’arbre phylogénétique pour les données nucléotidiques et protéiques, respectivement. L’heuristique employée est la suivante :
1. Définir un ordre arbitraire des séquences.
2. Débuter avec les trois premières séquences et leur unique arbre possible.
3. Essayer de greffer la prochaine séquence sur toutes les branches de cet arbre ;
retenir la position de coût minimal.
4. Évaluer tous les voisins NNI de l’arbre courant ; tout voisin de coût inférieur
devient le nouvel arbre courant.
5. Retourner en 3. avec la prochaine séquence tant qu’il en reste une.
6. Évaluer tous les voisins SPR de l’arbre courant ; tout voisin de coût inférieur
devient le nouvel arbre courant.
Avec cette heuristique, un arbre portant sur une trentaine de séquences peut être
calculé en quelques secondes, alors que le calcul exhaustif exact de tous les arbres
possibles serait irréalisable. Donc, cette heuristique n’évalue qu’une partie infime de
tous les arbres possibles. Une stratégie fréquente et efficace est de recommencer
plusieurs fois tout le calcul en changeant à chaque fois aléatoirement l’ordre dans
lequel les séquences sont ajoutées à l’arbre. Il est recommandé de faire 5 à 10 telles
itérations. Très fréquemment, on trouve un arbre de coût inférieur à la 4° ou la 7°
itération. Le programme SeaView utilise DNAPARS et PROTPARS pour ses calculs
par parcimonie.
Le programme PAUP* propose les deux heuristiques NNI et SPR. Il propose aussi
un calcul exact (option Branch and Bound qui ne calcule pas le coût des topologies
dont l’algorithme sait démontrer qu’il sera supérieur à l’optimum courant) qui n’est
faisable que pour un très petit nombre de séquences (≤ 20).
Le programme de parcimonie le plus efficace en termes de vitesse de calcul et
d’efficacité de l’heuristique est TNT (http://www.cladistics.com/aboutTNT.html)
qui peut nécessiter une licence. Il utilise une heuristique très élaborée trop complexe
pour être décrite ici.
7.1.5 Longueurs de branches des arbres de parcimonie
On l’a déjà mentionné, on ne peut pas donner un sens unique à la longueur d’une
branche d’un arbre au sens de la parcimonie, puisque plusieurs longueurs possibles
sont également acceptables. En conséquence, les arbres de parcimonie sont souvent
dessinés avec des branches dont la longueur est arbitraire. Le défaut de cette approche
est qu’il est très difficile de ne pas donner un sens quantitatif à la longueur des branches