Chapitre 7 • Algorithmes pour la phylogénie moléculaire
82
7.1.2 Heuristiques
Une approche heuristique considère à tout moment un (ou plusieurs) arbre(s) candidat(s) et leur coût, puis évalue le coût de tous les arbres voisins du (ou des) candidat(s), et remplace le candidat par le voisin s’il est de coût inférieur. L’heuristique se
termine dès qu’aucun voisin de coût inférieur n’existe. C’est la notion précise
d’arbre voisin qui définit l’identité et la qualité d’une heuristique. Deux heuristiques
appliquées aux mêmes données qui envisagent des voisinages différents sont susceptibles d’obtenir des résultats distincts. Une heuristique qui envisage les mêmes
voisins qu’une autre, plus d’autres, sera plus gourmande en calcul, mais sera avec
certitude meilleure.
Il a été démontré mathématiquement qu’il n’existe pas d’algorithme connu beaucoup plus rapide que l’évaluation de toutes les topologies possibles et qui garantisse
de trouver l’arbre de coût minimal.
Les notions de Nearest Neighbor Interchange (échange du plus proche voisin,
abrégé en NNI) et Subtree Pruning and Regrafting (taille et greffe de sous-arbre,
abrégé en SPR) sont utiles pour définir précisément ces heuristiques. L’opération
NNI consiste à organiser les quatre sous-arbres voisins d’une branche interne différemment les uns par rapport aux autres. Si l’on note A, B, C, et D ces sous-arbres, et
que leur relation de départ est ((A,B),(C,D)), deux NNI sont possibles qui sont les
arbres ((A,C),(B,D)) et ((A,D),(B,C)). Un arbre non raciné à n feuilles contient n–3
branches internes. Il existe donc 2(n–3) arbres distincts voisins d’un arbre donné au
sens de l’opération NNI. L’opération SPR consiste à considérer un sous-arbre quelconque d’un arbre, à le « couper », et à le « recoller ailleurs ». Un SPR est donc le
déplacement d’un sous-arbre dans un arbre, sans modifier la topologie ni le racinement de ce sous-arbre. On peut établir qu’il existe 4(n–3)(n–2) voisins d’un arbre
donné au sens du SPR. Un NNI est un cas particulier de SPR : déplacer un sousarbre en ne lui faisant franchir qu’un nœud. Une heuristique qui procède par SPR
sera donc plus lente mais nécessairement plus exacte qu’une heuristique basée sur
l’opération NNI. Enfin, l’opération Tree Bisection and Reconnection (bissection et
reconnexion d’arbre, abrégé en TBR) définit des voisinages d’arbre encore plus
vastes. Ici, on coupe une branche interne de l’arbre de départ, ce qui conduit à deux
sous-arbres que l’on déracine et reconnecte en joignant n’importe quelle branche de
l’un à n’importe quelle branche de l’autre. Le nombre de voisins par TBR d’un arbre
dépend de la topologie de cet arbre. Ce nombre est nécessairement supérieur au
nombre de ses voisins par SPR (puisqu’un SPR est un cas particulier d’un TBR) et
vaut (2n–3)(n–3) 2 au maximum.
7.1.3 Propriétés
La méthode de parcimonie produit des arbres non racinés, puisque le coût de chaque
arbre est indépendant de la position de la racine. L’emploi d’un groupe externe
permet alors de raciner le résultat obtenu.
La méthode de parcimonie recherche l’arbre de coût minimal, aussi appelé arbre
le plus parcimonieux. Il est très fréquent que plusieurs arbres distincts soient de coût
82
7.1.2 Heuristiques
Une approche heuristique considère à tout moment un (ou plusieurs) arbre(s) candidat(s) et leur coût, puis évalue le coût de tous les arbres voisins du (ou des) candidat(s), et remplace le candidat par le voisin s’il est de coût inférieur. L’heuristique se
termine dès qu’aucun voisin de coût inférieur n’existe. C’est la notion précise
d’arbre voisin qui définit l’identité et la qualité d’une heuristique. Deux heuristiques
appliquées aux mêmes données qui envisagent des voisinages différents sont susceptibles d’obtenir des résultats distincts. Une heuristique qui envisage les mêmes
voisins qu’une autre, plus d’autres, sera plus gourmande en calcul, mais sera avec
certitude meilleure.
Il a été démontré mathématiquement qu’il n’existe pas d’algorithme connu beaucoup plus rapide que l’évaluation de toutes les topologies possibles et qui garantisse
de trouver l’arbre de coût minimal.
Les notions de Nearest Neighbor Interchange (échange du plus proche voisin,
abrégé en NNI) et Subtree Pruning and Regrafting (taille et greffe de sous-arbre,
abrégé en SPR) sont utiles pour définir précisément ces heuristiques. L’opération
NNI consiste à organiser les quatre sous-arbres voisins d’une branche interne différemment les uns par rapport aux autres. Si l’on note A, B, C, et D ces sous-arbres, et
que leur relation de départ est ((A,B),(C,D)), deux NNI sont possibles qui sont les
arbres ((A,C),(B,D)) et ((A,D),(B,C)). Un arbre non raciné à n feuilles contient n–3
branches internes. Il existe donc 2(n–3) arbres distincts voisins d’un arbre donné au
sens de l’opération NNI. L’opération SPR consiste à considérer un sous-arbre quelconque d’un arbre, à le « couper », et à le « recoller ailleurs ». Un SPR est donc le
déplacement d’un sous-arbre dans un arbre, sans modifier la topologie ni le racinement de ce sous-arbre. On peut établir qu’il existe 4(n–3)(n–2) voisins d’un arbre
donné au sens du SPR. Un NNI est un cas particulier de SPR : déplacer un sousarbre en ne lui faisant franchir qu’un nœud. Une heuristique qui procède par SPR
sera donc plus lente mais nécessairement plus exacte qu’une heuristique basée sur
l’opération NNI. Enfin, l’opération Tree Bisection and Reconnection (bissection et
reconnexion d’arbre, abrégé en TBR) définit des voisinages d’arbre encore plus
vastes. Ici, on coupe une branche interne de l’arbre de départ, ce qui conduit à deux
sous-arbres que l’on déracine et reconnecte en joignant n’importe quelle branche de
l’un à n’importe quelle branche de l’autre. Le nombre de voisins par TBR d’un arbre
dépend de la topologie de cet arbre. Ce nombre est nécessairement supérieur au
nombre de ses voisins par SPR (puisqu’un SPR est un cas particulier d’un TBR) et
vaut (2n–3)(n–3) 2 au maximum.
7.1.3 Propriétés
La méthode de parcimonie produit des arbres non racinés, puisque le coût de chaque
arbre est indépendant de la position de la racine. L’emploi d’un groupe externe
permet alors de raciner le résultat obtenu.
La méthode de parcimonie recherche l’arbre de coût minimal, aussi appelé arbre
le plus parcimonieux. Il est très fréquent que plusieurs arbres distincts soient de coût