Chapitre 7 • Algorithmes pour la phylogénie moléculaire
80
On cherche à calculer le nombre minimum de changements nécessaires pour ce
site et cette topologie. On commence par raciner arbitrairement l’arbre. Le nombre
cherché est obtenu par un calcul progressif qui part des feuilles de l’arbre pour
remonter jusqu’à sa racine. À chaque nœud ou feuille de l’arbre, deux quantités sont
calculées : P, le nombre minimal de changements dans le sous-arbre dont ce nœud
est racine, et X, l’ensemble des résidus possibles à ce nœud pour qu’il y ait P changements dans le sous-arbre. Le nombre recherché est donc la quantité P associée à la
racine. Il est immédiatement possible de calculer P et X pour une feuille de l’arbre :
P = 0, X = {résidu observé au site pour cette séquence}. La figure 7.3 détaille
comment, connaissant les valeurs P 1 , X 1 et P 2 , X 2 pour deux nœuds fils, on peut
calculer P et X pour leur nœud père.
Il en ressort que :
Le calcul se termine quand les quantités et
P X associées à la racine de l’arbre ont
été obtenues.
Figure 7.3 – Algorithme de Fitch.
La partie gauche de la figure indique les ensembles X et les nombres de changements P associés à deux nœuds fils et leur nœud père. La partie droite indique
quels résidus ancestraux sont compatibles avec ces valeurs . On voit en haut à
P
droite que, s’il existe des résidus communs aux ensembles X 1 et X 2 , n’importe
quel résidu commun peut être placé aux trois nœuds considérés et conduit au
nombre minimal de changements P 1 +P 2 au nœud père. On voit en bas à droite
que le nombre minimal de changements au nœud père vaut P 1 +P 2 +1 et que tous
les résidus de X 1 ainsi que tous ceux de X 2 sont compatibles avec ce nombre.
si X 1 X 2
, alors X X 1 X 2
et P P 1 P 2
+
=
=
si X 1 X 2
= , alors X X 1 X 2
et P P 1 P 2 1
+
+
=
=
80
On cherche à calculer le nombre minimum de changements nécessaires pour ce
site et cette topologie. On commence par raciner arbitrairement l’arbre. Le nombre
cherché est obtenu par un calcul progressif qui part des feuilles de l’arbre pour
remonter jusqu’à sa racine. À chaque nœud ou feuille de l’arbre, deux quantités sont
calculées : P, le nombre minimal de changements dans le sous-arbre dont ce nœud
est racine, et X, l’ensemble des résidus possibles à ce nœud pour qu’il y ait P changements dans le sous-arbre. Le nombre recherché est donc la quantité P associée à la
racine. Il est immédiatement possible de calculer P et X pour une feuille de l’arbre :
P = 0, X = {résidu observé au site pour cette séquence}. La figure 7.3 détaille
comment, connaissant les valeurs P 1 , X 1 et P 2 , X 2 pour deux nœuds fils, on peut
calculer P et X pour leur nœud père.
Il en ressort que :
Le calcul se termine quand les quantités et
P X associées à la racine de l’arbre ont
été obtenues.
Figure 7.3 – Algorithme de Fitch.
La partie gauche de la figure indique les ensembles X et les nombres de changements P associés à deux nœuds fils et leur nœud père. La partie droite indique
quels résidus ancestraux sont compatibles avec ces valeurs . On voit en haut à
P
droite que, s’il existe des résidus communs aux ensembles X 1 et X 2 , n’importe
quel résidu commun peut être placé aux trois nœuds considérés et conduit au
nombre minimal de changements P 1 +P 2 au nœud père. On voit en bas à droite
que le nombre minimal de changements au nœud père vaut P 1 +P 2 +1 et que tous
les résidus de X 1 ainsi que tous ceux de X 2 sont compatibles avec ce nombre.
si X 1 X 2
, alors X X 1 X 2
et P P 1 P 2
+
=
=
si X 1 X 2
= , alors X X 1 X 2
et P P 1 P 2 1
+
+
=
=