2 2
CHAPITRE 6. PROCESSUS D’ÉVOLUTION GÉNÉTIQUE
Remarque 6.4.1 Le temps de coalescence de 2 lignées est une variable aléatoire exponentielle de paramètre 1 et pour k individus, le premier temps auquel une paire a un ancêtre
commun est donc l’infimum de
k(k−1)
2
variables aléatoires exponentielles de paramètre 1
indépendantes.
Nous allons ainsi pouvoir définir le k-coalescent comme processus limite, quand N tend
vers l’infini, du processus qui décrit la généalogie de k individus.
Définition 6.4.2 Soit k ∈ N
∗ . On appelle k-coalescent, la chaîne de Markov (Π t ) t à
valeurs dans l’ensemble P k des partitions de {1, . . . , k} définie de la manière suivante :
• Π 0 = {{1}, . . . , {k}}.
• Soit T i le i-ème temps de coalescence. On pose T 0 = 0. Alors les intervalles de temps T i −
T i−1 sont indépendants et suivent des lois exponentielles de paramètre
(k − i)(k − i + 1)
2
.
• A chaque temps de saut, deux blocs de la partition sont choisis uniformément parmi les
paires de blocs existantes et coalescent, au sens où les deux sous-blocs sont regroupés en
un seul.
Remarquons que la définition donnée du k-coalescent permet d’en déduire facilement un
algorithme de simulation :
• On se donne k individus. On pose ˜
Π 0 = {{1}, . . . , {k}}.
• On simule une variable aléatoire exponentielle de paramètre
k(k−1)
2
. Pour ce faire, on
considère une variable aléatoire U de loi uniforme sur [0, 1] et on pose T 1 =
2
k(k−1)
log(1/U ).
(cf [55]).
• On choisit uniformément au hasard deux blocs distincts de la partition, (donc avec
probabilité
2
k(k−1)
). On regroupe ces deux blocs en un seul bloc. On appelle alors ˜
Π 1
cette nouvelle partition.
• On réitère cette procédure. Après l’étape i−1, on simule une variable aléatoire exponentielle de paramètre
(k−i+1)(k−i)
2
. On choisit uniformément au hasard deux blocs distincts
de la partition composée de k − i + 1 blocs, (donc avec probabilité
2
(k−i)(k−i+1)
). On
regroupe ces blocs en un seul ensemble. On obtient ainsi ˜
Π i .
• On pose alors
Π t =
i
˜
Π i 1 {Ti≤t
A chaque temps de coalescence, le nombre d’éléments de la partition diminue de 1, et
donc il sera réduit à un élément au bout de k − 1 événements de coalescence. Cet élément
est le plus récent ancêtre commun aux k individus (PRAC). Le temps T où l’on a trouvé
cet ancêtre est T = T k−1 .
Une représentation d’un coalescent est donnée en Figure 6.2 (Partie 6.5.2), pour une
échantillon de 8 individus.
2
CHAPITRE 6. PROCESSUS D’ÉVOLUTION GÉNÉTIQUE
Remarque 6.4.1 Le temps de coalescence de 2 lignées est une variable aléatoire exponentielle de paramètre 1 et pour k individus, le premier temps auquel une paire a un ancêtre
commun est donc l’infimum de
k(k−1)
2
variables aléatoires exponentielles de paramètre 1
indépendantes.
Nous allons ainsi pouvoir définir le k-coalescent comme processus limite, quand N tend
vers l’infini, du processus qui décrit la généalogie de k individus.
Définition 6.4.2 Soit k ∈ N
∗ . On appelle k-coalescent, la chaîne de Markov (Π t ) t à
valeurs dans l’ensemble P k des partitions de {1, . . . , k} définie de la manière suivante :
• Π 0 = {{1}, . . . , {k}}.
• Soit T i le i-ème temps de coalescence. On pose T 0 = 0. Alors les intervalles de temps T i −
T i−1 sont indépendants et suivent des lois exponentielles de paramètre
(k − i)(k − i + 1)
2
.
• A chaque temps de saut, deux blocs de la partition sont choisis uniformément parmi les
paires de blocs existantes et coalescent, au sens où les deux sous-blocs sont regroupés en
un seul.
Remarquons que la définition donnée du k-coalescent permet d’en déduire facilement un
algorithme de simulation :
• On se donne k individus. On pose ˜
Π 0 = {{1}, . . . , {k}}.
• On simule une variable aléatoire exponentielle de paramètre
k(k−1)
2
. Pour ce faire, on
considère une variable aléatoire U de loi uniforme sur [0, 1] et on pose T 1 =
2
k(k−1)
log(1/U ).
(cf [55]).
• On choisit uniformément au hasard deux blocs distincts de la partition, (donc avec
probabilité
2
k(k−1)
). On regroupe ces deux blocs en un seul bloc. On appelle alors ˜
Π 1
cette nouvelle partition.
• On réitère cette procédure. Après l’étape i−1, on simule une variable aléatoire exponentielle de paramètre
(k−i+1)(k−i)
2
. On choisit uniformément au hasard deux blocs distincts
de la partition composée de k − i + 1 blocs, (donc avec probabilité
2
(k−i)(k−i+1)
). On
regroupe ces blocs en un seul ensemble. On obtient ainsi ˜
Π i .
• On pose alors
Π t =
i
˜
Π i 1 {Ti≤t
A chaque temps de coalescence, le nombre d’éléments de la partition diminue de 1, et
donc il sera réduit à un élément au bout de k − 1 événements de coalescence. Cet élément
est le plus récent ancêtre commun aux k individus (PRAC). Le temps T où l’on a trouvé
cet ancêtre est T = T k−1 .
Une représentation d’un coalescent est donnée en Figure 6.2 (Partie 6.5.2), pour une
échantillon de 8 individus.
2