J’ouvre avec cette note une série de plusieurs notes, que sauf événement improbable — trad. : publication — rien ne viendra déranger. Cette série est consacrée à la “correction” des exercices proposés à la fin de chaque chapitre du livre de John Maynard-Smith, Evolutionary genetics, en insistant particulièrement sur les computer projects. L’objectif de cette série de notes est donc de présenter des grandes notions d’évolution, avec une approche un peu plus “analytique” que la présentation de résultats récents. Les computer projects seront effectués en R, et les scripts — écrits de manière pas forcément optimale — sont donnés à la fin de chaque note. Le code R n’est pas expliqué dans les notes, pour ne pas décourager les gens normaux qui pourraient lire ces lignes — mais la discussion est ouverte en commentaires. Les packages seqinr
et ape
sont utilisés. Les notes seront probablement assez longues, mais une lecture en diagonale est possible.
La note qui ouvre cette série est toute entière ou presque consacrée à la figure emblématique de Richard Dawkins, et plus précisément à son fameux toy model d’évolution par sélection naturelle. Dans ce modèle, Dawkins nous montre comment on peut, en partant de n’importe quelle chaîne de n caractères, aboutir à methinks it is a weasel
, soit il me semble que c’est une belette
.
Le modèle de Dawkins est simple. Chaque “phrase” (une chaîne de caractères) représente le patrimoine génétique d’un individu. A chaque nouvelle génération, un individu donne 10 descendants, et chaque “gène” (lettre de la “phrase”) du descendant est susceptible d’être muté — avec une fréquence que l’on choisit, mais qui dans notre cas sera de 1/100, soit une chance sur cent que chaque lettre de la phrase soit remplacée par une autre à chaque génération. Sur ces 10 descendants, mutés, tous ne sont pas aussi performants. On choisit donc celui qui est le plus proche de ce qu’on veut atteindre — ce point est discuté dans les conclusions — et on l’utilise comme seul survivant de la génération, pour qu’il donne à nouveau d’autres descendants. Dans notre cas, si aucun des descendants n’est meilleur que les autres, on en choisit un au hasard.
Commençons par analyser le problème avant de le modéliser. Notre phrase de départ possède 23 lettres (19 lettres et 4 espaces). Notre alphabet se compose de 27 lettres (26 et l’espace). Dans notre situation de départ, nous prenons chacune des 23 lettres de manière aléatoire. Nous supposons ici que nous sommes confrontés à un événement de mutation (sans quoi il faudrait multiplier toutes les probabilités par Pμ, probabilité de mutation). La probabilité Pi qu’au moins une lettre soit à la bonne place est donc
![Methinks it is a weasel (Maynard-Smith, chapitre 1) P_{i}=23{\times}\frac{1}{27}](http://media.paperblog.fr/i/110/1105072/methinks-it-is-weasel-maynard-smith-chapitre--L-1.jpeg)
Cela revient à répéter 23 fois un jeu dans lequel on a une chance sur 27 de gagner. Si l’on veut la probabilité P1 qu’exactement une lettre soit à la bonne place, il faut prendre en compte le fait que nos répétitions ne sont plus indépendantes, ce qui revient à écrire
![Methinks it is a weasel (Maynard-Smith, chapitre 1) P_{1}=\frac{1}{27}{\times}\left(\frac{26}{27}\right)^{22}](http://media.paperblog.fr/i/110/1105072/methinks-it-is-weasel-maynard-smith-chapitre--L-2.jpeg)
Soit environ 1,6 pour cent. On peut généraliser cette écriture sans difficultés majeures, en cherchant la probabilité Pn que n lettres soient à leur place
![Methinks it is a weasel (Maynard-Smith, chapitre 1) P_{n}=\left(\frac{1}{27}\right)^n{\times}\left(\frac{26}{27}\right)^{23-n}](http://media.paperblog.fr/i/110/1105072/methinks-it-is-weasel-maynard-smith-chapitre--L-3.jpeg)
Et pour dépasser le cadre du problème de Dawkins, si on a un alphabet de α lettres et une phrase de longueur L, Pn devient
![Methinks it is a weasel (Maynard-Smith, chapitre 1) P_{n}=\left(\frac{1}{\alpha}\right)^n{\times}\left(\frac{\alpha-1}{\alpha}\right)^{L-n}](http://media.paperblog.fr/i/110/1105072/methinks-it-is-weasel-maynard-smith-chapitre--L-4.jpeg)
Ces probabilités concernent la situation initiale. Le modèle stipule que quand une lettre est bonne, elle n’est plus mutée, et ce pour une raison très simple : on choisit toujours le meilleur mutant — on verra dans la partie modélisation comment s’en assurer, où justement contourner cette spécificité pour permettre des réversions; or, passer d’une mutation favorable à une mutation neutre fait baisser le score du mutant, qui ne sera pas sélectionnée à la génération suivante. Le modèle fait en sorte qu’il n’y aie pas de réversion. Cette propriété nous permet de calculer la probabilité Pk+1 d’obtenir au moins un mutant avec une mutation favorable à la génération suivante, sachant le nombre k de lettres à leur place.
![Methinks it is a weasel (Maynard-Smith, chapitre 1) P_{k+i}=(23-k){\times}{\frac{1}{27}](http://media.paperblog.fr/i/110/1105072/methinks-it-is-weasel-maynard-smith-chapitre--L-5.jpeg)
Dans les mêmes conditions, la probabilité Pk+1 d’obtenir exactement un mutant de ce type est
![Methinks it is a weasel (Maynard-Smith, chapitre 1) P_{k+1}=\frac{1}{27}{\times}\left(\frac{26}{27}\right)^{k-1}](http://media.paperblog.fr/i/110/1105072/methinks-it-is-weasel-maynard-smith-chapitre--L-6.jpeg)
En traçant la fonction
![Methinks it is a weasel (Maynard-Smith, chapitre 1) f(k)=(23-k){\times}{\frac{1}{27}](http://media.paperblog.fr/i/110/1105072/methinks-it-is-weasel-maynard-smith-chapitre--L-7.jpeg)
on obtient la probabilité de découvrir au moins une nouvelle lettre à chaque événement de mutation, en fonction du nombre de lettres déjà placées. D’après l’allure de la formule, on voit que cette probabilité s’amenuise. Le résultat est présenté dans la figure ci-dessous :
![Methinks it is a weasel (Maynard-Smith, chapitre 1) probas.png](http://media.paperblog.fr/i/110/1105072/methinks-it-is-weasel-maynard-smith-chapitre--L-8.jpeg)
A partir de ce que nous avons appris des équations précédentes, nous pouvons commencer à répondre à la grande question : quelle sera l’allure de la courbe qui donne le “score” (autrement dit, le nombre de lettres en place) en fonction du temps? Puisque, plus on connaît de lettres, plus le travail de recherche est difficile — ce qui est prévisible, on réduit le nombre de “tirages”, pour parler comme mes anciens profs de stats —, donc moins on progresse vite.
Vérifions cette hypothèse en modélisant l’évolution de notre phrase de départ. Avant de commencer, il est nécessaire de créer un alphabet, et une phrase but, ici methinks it is a weasel. Vous pouvez essayer avec tout autre chose, nothing in biology makes sense but in the light of evolution ou votre passage préféré de l’Origine des Espèces — notez en passant qu’il faut construire un alphabet adapté à chaque phrase. Des phrases plus longues ne prennent pas nécessairement plus de temps de calcul (il ne faut pas beaucoup plus de générations pour les résoudre) puisque comme on l’a vu juste avant, les étapes chronophages sont les dernières — où l’on démontre encore une fois qu’il faut regarder ce qu’on étudie avant de se lancer dedans…
On peut commencer l’estimation à la louche — on pourrait être beaucoup plus rigoureux, mais ce n’est pas nécessaire puisqu’on va simuler juste après — du nombre de générations nécessaires pour trouver notre phrase en entier. En reprenant la formulation de f(k), il est facile de trouver la probabilité de trouver la kième lettre. On peut cumuler facilement, pour obtenir Pk, la probabilité cumulée
![Methinks it is a weasel (Maynard-Smith, chapitre 1) P_k=\sum_{i=0}^kP_i=\sum_{i=0}^k\left(\left(23-i\right){\times}{\frac{1}{27}\right)](http://media.paperblog.fr/i/110/1105072/methinks-it-is-weasel-maynard-smith-chapitre--L-9.jpeg)
A partir de cette probabilité cumulée, on peut calculer Gk le nombre de générations qu’il faut pour arriver à k lettres correctes. Il suffit de prendre l’inverse de cette probabilité, et prendre en compte le nombre de descendants (10), ainsi que Pμ le taux de mutation (ici 1/100). On obtient l’écriture suivante
![Methinks it is a weasel (Maynard-Smith, chapitre 1) G_k=\frac{1}{10{\times}P_k}{\times}P_\mu=\frac{10^{-3}}{P_k}](http://media.paperblog.fr/i/110/1105072/methinks-it-is-weasel-maynard-smith-chapitre--L-10.jpeg)
Si l’on représente graphiquement f(k)=Gk, on obtient la courbe suivante
![Methinks it is a weasel (Maynard-Smith, chapitre 1) theor_cor.png](http://media.paperblog.fr/i/110/1105072/methinks-it-is-weasel-maynard-smith-chapitre--L-11.jpeg)
On a donc de bonnes chances de résoudre notre problème en moins de 2500 générations.
Avec le modèle fourni dans le document r attaché, on obtient les résultats suivants
![Methinks it is a weasel (Maynard-Smith, chapitre 1) weasel.png](http://media.paperblog.fr/i/110/1105072/methinks-it-is-weasel-maynard-smith-chapitre--L-12.jpeg)
Le caractère probabiliste de cette approche fait que le nombre de générations nécessaire varie à chaque fois qu’on lance la simulation. Mon record personnel est de 849 générations, et le nombre moyen de générations nécessaire est de 1500 — notre estimation à la louche nous a fourni le bon ordre de grandeur.
Que se passe t-il maintenant avec des chaînes beaucoup plus longues?
Prenons — en enlevant tous les caractères qui ne font pas partie de notre alphabet — le texte suivant :
C’est l’Ennui! - l’oeil chargé d’un pleur involontaire,
Il rêve d’échafaud en fumant son houka.
Tu le connais, lecteur, ce monstre délicat,
- Hypocrite lecteur, - mon semblable, - mon frère!
Sa complexité est beaucoup plus importante que le simple methinks it is a weasel. Nous allons tester deux modèles différents, l’un dans lequel la réversion est possible, l’autre dans lequel on ne peut pas perdre une mutation avantageuse. Si vous voulez reproduire la manœuvre chez vous, prenez garde au temps de calcul, qui va monter assez vite (notamment si vous permettez les réversions, il faut beaucoup de générations).
Pour permettre ou non les réversions, le code est très simple. Si on veut empêcher le modèle de perdre un caractère avantageux, il suffit de ne pas prendre de nouveau message si le score maximum de la nouvelle génération est inférieur au score de la génération parentale.
Soit en R (regardez le code pour comprendre les fonctions — les deux variantes sont présentes, il suffit de décommenter celle que l’on veut utiliser)
if(best.score<-out[1:length(message.init)] score<-c(score,best.score) } else { score<-c(score,score[i]) boucle(best.message) }
Avec notre test, cela nous donne le résultat suivant (pour les deux cas suivants, le nombre de génération étant long et mon MacBook ayant tendance à chauffer rapidement, j’ai interrompu à 10000 générations, indépendamment du fait que le message optimal aie été trouvé. Dès que j’aurais un ordinateur autre que portable, je relancerai le modèle sur des phrases longues pour voir combien de générations il met à tourner.
![Methinks it is a weasel (Maynard-Smith, chapitre 1) longNR.png](http://media.paperblog.fr/i/110/1105072/methinks-it-is-weasel-maynard-smith-chapitre--L-13.png)
Dans le cas ou une réversion est possible, il suffit de ne pas faire ce test, et d’écrire simplement
best.message<-out[1:length(message.init)] score<-c(score,best.score)
On obtient donc le résultat suivant
![Methinks it is a weasel (Maynard-Smith, chapitre 1) longR.png](http://media.paperblog.fr/i/110/1105072/methinks-it-is-weasel-maynard-smith-chapitre--L-14.png)
Ou il apparaît que quand on a résolu beaucoup de lettres, le travail d’optimisation est difficile (inutile de dire que je n’ai pas cherché à pousser cette simulation jusqu’à la résolution complète…).
On peut se poser une grande question ‘biologique’ vis-à-vis de ce modèle. Au commencement, on donne un but à l’évolution. Il faut considérer ce but comme étant le résultat de contraintes auxquelles notre ‘génome’ devra faire face, et l’ensemble des propriétés auxquelles il devra répondre. Cette manipulation toute simple explique bien comment on peut générer l’improbable, en procédant par sélection naturelle. On remarquera aussi qu’on n’explore pas l’univers des possibles : chaque amélioration devient une contrainte supplémentaire, et finit par canaliser le processus vers un optimum.
Télécharger le fichier : Note: There is a file embedded within this post, please visit this post to download the file.