© Dunod – Toute reproduction non autorisée est un délit.
91
7.3 • Maximum de vraisemblance
produit de la vraisemblance pour chaque site. En pratique, on calcule le logarithme
naturel de la vraisemblance, car le produit d’une grande quantité de nombres petits
peut être trop petit pour une représentation informatique :
La vraisemblance en un site se calcule à partir d’un ingrédient fondamental donné
par les résultats présentés auparavant concernant les modèles évolutifs markoviens.
Il s’agit de la matrice de transition, notée P, qui donne la probabilité de tout état en
fin de branche, pour toute longueur de branche, et tout état en début de branche. On
a vu que, pour une branche de longueur l, P = e Ql , puisque, Q étant normalisée, une
longueur de branche est équivalente à une durée évolutive.
La vraisemblance en un site est la somme des probabilités de toutes les histoires
évolutives possibles qui se terminent par les résidus observés dans les séquences au
site traité. Pour l’exemple de la figure 7.11, cela donne :
où les sommes portent sur tous les résidus possibles (4 ou 20), P xy (l) indique le
terme x,y de la matrice P pour une branche de longueur l, et Sz indique le résidu
présent dans la séquence z au site considéré. Le terme
représente la fréquence du
résidu ancestral inconnu.
7.3.3 L’algorithme de Felsenstein
L’équation ci-dessus met en évidence que l’on cumule les probabilités de tous les
scénarios ancestraux, mais un tel calcul deviendrait trop lourd pour un arbre de plus
grande taille. L’algorithme de Felsenstein permet un calcul progressif de la vraisemblance
d’un site, des feuilles vers la racine, pour un arbre de taille quelconque. En notant L
e,i
la vraisemblance du sous-arbre raciné au nœud e et possédant le résidu i à ce nœud,
et (e 1 , e 2 ) ses nœuds fils, s’il en a, on voit que :
L
log
L site
log
sites
=
L site
=
P l 1
P l 2
P l 3
P S1 l 4
P S3 l 7
P S6 l 8
P S5 l 5
P l 6
P S2 l 9
P S4 l 10
Si e est une feuille :
L
e i
1 si i est le résidu observé dans cette feuille au site
sinon 0
=
Sinon :
L
e i
P e 1 j | e i
=
=
L
e 1 j
P e 2 k | e i
=
=
L
e 2 k
k
j
=
91
7.3 • Maximum de vraisemblance
produit de la vraisemblance pour chaque site. En pratique, on calcule le logarithme
naturel de la vraisemblance, car le produit d’une grande quantité de nombres petits
peut être trop petit pour une représentation informatique :
La vraisemblance en un site se calcule à partir d’un ingrédient fondamental donné
par les résultats présentés auparavant concernant les modèles évolutifs markoviens.
Il s’agit de la matrice de transition, notée P, qui donne la probabilité de tout état en
fin de branche, pour toute longueur de branche, et tout état en début de branche. On
a vu que, pour une branche de longueur l, P = e Ql , puisque, Q étant normalisée, une
longueur de branche est équivalente à une durée évolutive.
La vraisemblance en un site est la somme des probabilités de toutes les histoires
évolutives possibles qui se terminent par les résidus observés dans les séquences au
site traité. Pour l’exemple de la figure 7.11, cela donne :
où les sommes portent sur tous les résidus possibles (4 ou 20), P xy (l) indique le
terme x,y de la matrice P pour une branche de longueur l, et Sz indique le résidu
présent dans la séquence z au site considéré. Le terme
représente la fréquence du
résidu ancestral inconnu.
7.3.3 L’algorithme de Felsenstein
L’équation ci-dessus met en évidence que l’on cumule les probabilités de tous les
scénarios ancestraux, mais un tel calcul deviendrait trop lourd pour un arbre de plus
grande taille. L’algorithme de Felsenstein permet un calcul progressif de la vraisemblance
d’un site, des feuilles vers la racine, pour un arbre de taille quelconque. En notant L
e,i
la vraisemblance du sous-arbre raciné au nœud e et possédant le résidu i à ce nœud,
et (e 1 , e 2 ) ses nœuds fils, s’il en a, on voit que :
L
log
L site
log
sites
=
L site
=
P l 1
P l 2
P l 3
P S1 l 4
P S3 l 7
P S6 l 8
P S5 l 5
P l 6
P S2 l 9
P S4 l 10
Si e est une feuille :
L
e i
1 si i est le résidu observé dans cette feuille au site
sinon 0
=
Sinon :
L
e i
P e 1 j | e i
=
=
L
e 1 j
P e 2 k | e i
=
=
L
e 2 k
k
j
=