Choux romanesco, Vache qui rit et intégrales curvilignes

Évoluez-les tous !

Dans le numéro de Juillet-Août de Annals of Improbable Research (le journal des organisateurs des prix IgNobel), une équipe composée de trois entomologistes américains et du très célèbre Professeur Chen s'intéresse à l'épineux problème... de la phylogénie des Pokémon. En étudiant minutieusement leurs aptitudes, les 4 chercheurs ont réussi à recréer l'arbre évolutif des célèbres monstres de Nintendo.

Arbre_extrait
Le clade des Pokémon électriques, extrait de l'arbre évolutif des Pokémon
Un arbre phylogénique est une représentation graphique des liens de parentées entres des espèces
Plus une branche est longue, plus les Pokémon sont éloignés.
On découvre sans surprise que Posipi et Négapi sont évolutivement proches, tout comme Boréas et Fulguris. La proximité entre Emolga et Electhor est un peu plus étonnante !

Phylogénie des Pokemon
L'équipe menée par le professeur Chen s'est en fait servi des méthodes de reconstruction classiques en taxinomie. Bien que celles-ci soient plus souvent utilisées pour mettre en ordre Animalia ou Platae, rien n'empêche de les employer pour ranger les Pokémon ! Dans la pratique, ils ont été définis par leur caractéristiques dans le jeu : leurs types (108 possibles), leur groupe d'œufs (16 possibles), la forme de leur corps (14 possibles) et leurs attaques (559 possibles). Une fois les données rassemblées, l'arbre final des 646 Pokémon (regroupés par familles : Pichu, Pikachu et Raichu forment un même taxon, représenté par la créature la plus évoluée) est érigé par analyse bayésienne de type MCMC.

Cette étude a mis en évidence de nombreux faits cachés par Nintendo. Par exemple :
- Le plus "évolué" des Pokémon est M.Mime ! (Se dire qu'un Pokémon mime est le summum de l'évolution est profondément désespérant)
- La vie Pokémon a commencé dans l'eau, puis est devenue terrestre de trois façons indépendantes : l'ancêtre de Locklass a donné naissance à la clade des Pokémon de glace, l'ancêtre de Marill a engendré la famille des Pokémon vol et psy (dont M.Mime) et tous les autres Pokémon dérivent d'un ancêtre proche de Kaïminus.
- Les types spéciaux (feu, plante, glace, poison, psy...) forment des clades monophylétique. Ainsi, l'ensemble des Pokémon feu descendent d'un même ancêtre aux traits canins, alors que les Pokémon plante descendent d'un ancêtre proche de Bulbizarre.
- La plupart des groupes d'oeufs forment des clades polyphylétiques : ils sont répartis à tous les coins de l'arbre. Même remarque sur la forme des corps.

Méthodes de reconstructions
Avant les années 60, la classification des espèces se basait essentiellement sur des caractères observables à l'oeil nu : morphologie, comportement... Les méthodes avaient leurs limites, un même caractère pouvant apparaître à deux endroits différent de l'arbre évolutif. C'est d'ailleurs cette classification qui a donné le regroupement des reptiles, qui n'a plus lieu d'être aujourd'hui (bien que des arguments morphologiques permettent également de réfuter l'existence d'un tel groupe). Avec l'arrivée du séquençage de l'ADN et des protéines, le domaine a évolué, donnant naissance à la phylogénie moléculaire. Pour comparer plusieurs espèces, ce sont maintenant des régions clés de l'ADN que l'on compare ; une proximité entre ces molécules implique un ancêtre commun proche (les séquences ayant muté depuis une même séquence plus ancienne).

Pour reconstituer un arbre phylogénétique, les plus simples des méthodes consistent à mesurer la proximité entre les espèces qui nous intéressent (on peut par exemple mesurer le degré de différence entre une même protéine). On consrtuit alors une matrice des distances, qui servira de base à l'élaboration de l'arbre. De nombreux algorithmes de reconstructions existent, et, grâce à la recherche, deviennent meilleurs au fil des années. Voyons dans le détail ces différentes méthodes.

L'algorithme UPGMA
Le plus simple est l'algorithme UPGMA ("Unweight Pair Group Method with Arithmetic mean") : à chaque étape, on cherche les deux OTUs ("operationnal taxonomic units", les entités que l'on cherche à classer ; ici, ce sont des Pokémon) les plus proches et on les regroupe. On transforme alors la matrice des distances M entre prenant les moyenne des deux OTUs considérées. Dans le contexte de la phylogénie, cette méthode permet de reconstruire l'arbre des espèces.

Testons plutôt sur un exemple. Nous allons prendre ce qui se fait de plus kawaï en matière de Pokémon : Rondoudou, Nanméouïe, Leveinard, Mélofée et Togepi. Les distances ont été reccueillies sur l'arbre de l'équipe de Chen. Dans la pratique, ces distances peuvent se calculer à partir du degré de ressemblance morphologique de deux espèces, ou à partir de la proximité de séquence Adn SIMILAIRES;

UPGMA_1
Les deux Pokémon les plus proches sont Mélofée et Togepi (distance de 16). Dans la matrice des distances, on remplace les valeurs par la moyenne des deux colonnes. La nouvelle matrice indique alors que les plus proches sont Nanméouïe et Leveinard (distance 19) :

UPGMA_2

Troisième étape : on raccroche {Nanméouïe, Leveinard} avec {Mélofée, Togepi} (distance 24), puis on raccroche le tout avec Rondoudou (distance 38)

UPGMA_3

Cette méthode présente un inconvénient majeur, chaque OTU est à la même distance de la racine de l'arbre. Puisqu'il n'y a aucune raison pour que les branches aient exactement le même taux de mutation, il faut améliorer cet algorithme.

L'algorithme NJ
L'algorithme NJ (Neighbor-Joining) améliore ce point : il permet des branches de différentes tailles. Cependant, le résultat est un arbre sans racine. Pour mettre en place l'algorithme, on part d'un graphe étoilé comme celui-ci.

NJ_1

Le principe de NJ reste grosso le même que UPGMA, mais on change un peu la métrique pour prendre en compte l'ensemble des OTU. Pour cela, on construit une nouvelle matrice de distances Q de la façon suivante:

Q(i,j)=d(i,j)-[r(i)+r(j)]/(N-2)

où N est le nombre d'OTU, d(i,j) est la distance entre i et j, et r(i)=∑d(i,k). En fait, Q(i,j) représente l'éloignement moyen du couple (i,j) des autres OTU.

Les deux OTU les plus proches (disons i et j) selon cette nouvelle matrice sont liés par un nouveau noeud. Pour tenir compte des éventuelles longueurs de branches différentes, la distance entre ce noeud n et l'extrémité i est donné par :

d(n,i)=d(i,j)/2+[r(i)-r(j)]/2(N-2)

Reprenons l'exemple précédent. La matrice des distances M donne une nouvelle matrice Q. Celle-ci montre que Nanméouïe et Leveinard sont les plus proche. Selon la formule, le noeud intermédiaire sera placé à une distance de 7.5 de Leveinard :

NJ_2

On recommence alors avec une nouvelle matrice de distances M. Dans celle-ci, i et j sont remplacées par le nouveu noeud n, sa distance avec un autre noeud k étant:

d(k,n)=(d(k,i)+d(k,j)-d(i,j))/2

NJ_3
Nouvelle matrice de distance

On continue alors l'algorithme avec la nouvelle matrice, ce qui donne l'arbre final :

NJ_4
Toutes les boules roses ne se valent pas.

Et ce ne sont là que les deux principales manières d'interpréter graphiquement un tableau de distance. Mais dans la pratique, le domaine de la phylogénie n'utilise ces méthodes basées sur les distances qu'en première approche. Bien qu'elles soient rapides à utiliser, la construction des matrices de distance entraînent une grande perte d'informations.

Les méthodes de MP
Du coup, pour ne pas perdre de vue les séquences ADN, il faut les garder dans le calcul. Les méthodes les plus simples restent les méthodes MP (Maximum de Parcimonie), qui cherchent parmi tous les arbres celui qui implique le minimum de changements. Les résultats sont bien meilleurs que les méthodes basées sur le calcul des distances, mais sont bien plus coûteuses en temps de calcul.

L'idée principale de MP est de construire toutes les topologies d'arbres possibles et, pour chacun de ces arbres, calculer le nombre de mutations qu'il implique (oublions ici que les séquences d'ADN peuvent muter autrement que par substitution). On part alors de l'hypothèse que le meilleur des arbres est celui qui est le plus économe en transformations.

Le mieux, c'est de prendre un exemple. Avec quatre Pokémon (Nanméouïe, Togepi, Leveinard et Mélofée), il faut tester 3 arbres différents (avec cinq, il aurait fallu en tester 15, et la croissance est plus qu'exponentielle [OEIS : A001147]). En guise d'ADN, on va prendre la suite des 100 CT de la génération V : 1 si le Pokémon peut apprendre la CT, 0 sinon.

N : 0011010001101111111111011011110110100100010110011000000110100000001001001000100000101110010110000000
T : 0010010001100001111111000010110110100100010110011000000100100000000001001000100000101110010001000000
L : 0001011001101111110111011110111100101110010110011000000110100000001101001000110100101110010011000000
M : 0011010001101101111111011011111110100100010110011000000110100000001001001000100000101110010001000000

ADN de Nanméouïe, Togepi, Leveinard et Mélofée

Par soucis de visibilité, on va éliminer les sites n'apportant pas d'informations. En effet, si le caractère est partagé (ou non partagé) par les quatre espèce étudiées, pas la peine de s'y intéresser. On ne garde donc que 23 CT intéressantes :

N : 11011111101010011000110
T : 10000010000010000000001
L : 01111101110101111111011
M : 11011011101110011000001
ADN épuré de Nanméouïe, Togepi, Leveinard et Mélofée

Maintenant, il est temps d'évaluer le poids d'un arbre donné. Prenons celui qui relie Nanméouïe-Togepi à Leveinard-Mélofée :

MP_1

Il faut maintenant recréer le code génétique des deux ancêtres communs. Pour cela, on procède caractère par caractère.
- Le 1er caractère (CT3) par exemple, est partagé entre Nanméouie, Togepi et Mélofée : on compte donc une mutation, sur la branche e. (on pourrait aussi supposer trois mutations indépendantes sur les branches b, c et d, mais cette hypothèse est moinsprobable). 
- Le 6ème caractère (CT15) est partagé entre Nanméouïe et Leveinard : deux mutations ont eu lieu indépendemment sur les branches b et e.
- Le 12e caractère (CT31) est partagé entre Mélofée et Leveinard : une seule mutation s'est produite, sur la branche a.

Au total, cet arbre implique 26 mutations.

Pour déterminer ce nombre de mutation, on peut en fait restreindre davantage le nombre de CT à analyser. Un caractère partagé entre 3 Pokémon sur 4 impliquera une seule mutation, quel que soit l'arbre. On peut donc finalement se limiter à l'étude de 4 CT :

N : 1 1 0 1
T : 0 0 0 0
L : 1 0 1 1
M : 0 1 1 0
ADN très épuré de Nanméouïe, Togepi, Leveinard et Mélofée

En faisant les compte, on peut conclure que l'arbre le plus parcimonieux est celui mettant d'un côté le couple Nanméouïe-Leveinard et de l'autre le couple Togepi-Mélofée. Tout concorde ! Tout comme la méthode NJ, l'algorithme ne permet malheureusement pas de d'obtenir un arbre.

MP_2
Trois arbres possibles, un seul vainqueur.

L'approche Bayésienne
Bien que de nombreux algorithmes basés sur le principe de parcimonie existent, les reconstructions phylogéniques se servent surtout de méthodes empruntées aux statistiques et aux probabilités, à base d'inférence bayésienne (estimation de la vraisemblance d'un résultat par des arguments probabilistes). L'idée d'utiliser en phylogénie les probabilités pour estimer la vraisemblance d'un résultat n'est pas nouvelle, mais l'approche bayésienne mise au point à la fin des années 90 est aujourd'hui incontournables. C'est d'ailleurs celles-ci qui ont été utilisées par les 4 chercheurs dans leur étude des Pokémon.

L'idée générale est d'estimer, grâce à la formule de Bayes, les probabilités que chaque arbre correspondent aux données. Le problème, c'est que le nombre trop important d'arbre rend impossible ce calcul. Pour cela, on utilise une marche aléatoire (MCMC : Markov Chain Monte-Carlo) : on se promène sur l'ensemble des arbres de manière à visiter le plus souvent les arbres les plus probables. Après un très grand nombre de pas, il suffit de regarder par où l'on est passé : les arbres les plus visités seront les meilleurs.

Arbre_extrait_2La clade des pokémon trop mignons, autre extrait de l'arbre évolutif des Pokémon. Celui-ci est construit par inférence bayésienne.


L'analyse phylogénétique est un domaine qui continue de progresser. Outre ses applications de généalogie d'espèces, ces méthodes peuvent aussi être employées en médecine, pour retracer l'histoire d'une contamination par un virus. Les algorithmes bayésiens n'ont d'ailleurs pas encore révélés tous leur secrets, plusieurs problèmes dans ce domaine sont encore ouverts... 


Sources
Annals of Improbable Research, juillet-août 2012, volume 18, n°4
Les méthodes probabilistes en phylogénie moléculaire, Frédéric Delsuc et Emmanuel J. P. Douzery.
Génétique, phylogénie et évolution, cours du réseau Génet.

Posté par El Jj à 10:00 - Commentaires [11] - Permalien [#]
Tags : , , ,

Commentaires sur Évoluez-les tous !

    Et dire qu'on trouve encore des gens qui pensent que les données récoltées par les pokédex ne servent à rien !

    Posté par Guillaum, 28 octobre 2012 à 11:49 | | Répondre
  • Et comment tu as choisi tes pokémon kawaii ? Y a eu une étude pour déterminer quels sont les pokémon les plus mignons ?

    Posté par Kaki, 29 octobre 2012 à 13:43 | | Répondre
  • étrange, mew ( avec mr mime ) est le pokémon le plus évolué, pourtant dans pokémon c'est mew l'ancêtre de tous les pokémon.

    les créateurs de pokémon ont visiblement séché leurs cours de svt.

    Posté par grude, 14 novembre 2012 à 19:59 | | Répondre
  • Les méthodes de MP

    Malgré le caractère « improbable » de cette recherche, ça n’en reste pas moins ludiquement intéressant et pas sans enseignement.
    Ça me rappelle d’ailleurs la « 1ère classification phylogénétique d'Heroic Fantasy » de votre co-cafetier M. Colin .


    J’ai cependant quelques questions et considérations à propos du paragraphe « Les méthodes de MP » (et j’en profite pour tester si l’HTML fonctionne ^^).

    Premièrement, et d’autant plus que ce blog est à la base dédié aux mathématiques, pourquoi ne pas avoir ajouté un petit paragraphe annexe où démontrer que le nombre d’arbres binaires entiers non enracinés non ordonnés à feuilles étiquetées suit bien la suite A001147 ? (Idem si les arbres sont enracinés, il faut juste prendre la valeur suivante de la suite .)
    Ou même, simplement donner quelques pistes de réflexion pour que le lecteur puisse, comme exercice, le redémontrer de lui-même ?

    Deuxièmement, si je ne me suis pas trompé, le « seul vainqueur » parmi les « [t]rois arbres possibles » n’est pas l’arbre du haut mais celui d’en bas à droite (25 mutations contre 26 pour les autres), c’est-à-dire celui avec Nanméouïe et Leveinard d’un côté et Mélofée et Togepi de l’autre (même résultat qu’avec UPGMA et NJ  !)

    Troisièmement, l’arbre du haut ne peut pas être considéré a priori comme « celui qui [fait] de Togepi et Leveinard deux proches cousins » : certes, cet arbre place bien Togepi et Leveinard d’un côté et Nanméouie et Mélofée de l’autre, mais ce n’est pas pour autant que chaque paire constitue respectivement des proches cousins.
    En effet, l’algorithme MP donne des arbres sans racine, or la racine (pour orienter l’arbre et donc ajouter le facteur temps de l’évolution) peut être ajoutée sur n’importe laquelle des 5 branches (MP ne permet pas de choisir) : si on vient par exemple placer la racine sur la branche de Togepi, il ne sera pas un proche cousin de Leveinard mais un taxon ayant divergé des 3 autres.

    Enfin, on peut épurer encore plus l’ADN de nos 4 candidats : si un caractère est partagé par tous les taxons sauf un (cas du 1er caractère) ou par aucun taxon sauf un (cas du 3e caractère), ça comptera pour une et exactement une mutation (sur la branche menant à au taxon singulier), et ce quelle que soit la forme des arbres à départager par MP, on peut donc s’en passer dans le cadre de cet algorithme.
    Or c’est le cas de 19 des 23 caractères ayant passé la première épuration, restent donc après la seconde épuration les 6e, 11e, 12e et 22e caractères, soit : N : 1101 / T : 0000 / L : 1011 / M : 0110.
    Ça accélère la comparaison des 3 arbres, non  ?
    Bon par contre, il est vrai que plus le nombre de taxons augmente, plus le nombre de caractères susceptibles d’être filtrés par ces épurations diminuera.

    Posté par Ethaniel, 19 novembre 2012 à 19:40 | | Répondre
  • HTML

    Ah ben non, l’HTML est purement et simplement retiré !
    Donc, le lien vers la « 1ère classification phylogénétique d'Heroic Fantasy » est : http://svtcolin.blogspot.fr/2011/04/normal-0-21-false-false-false-fr-x-none.html

    Posté par Ethaniel, 19 novembre 2012 à 19:42 | | Répondre
  • Ethaniel > Merci pour ce long commentaire, j'ai amélioré l'article en fonction ! L'erreur dans l'arbre venait d'une bête inversion lors de la rédaction.

    Mon article était suffisamment long comme ça, j'ai préféré limiter au maximum les digressions. La démonstration du nombre d'arbre n'est en fait pas bien compliquée si on s'y penche un peu. Il faut simplement remarquer qu'un arbre à n feuilles s'obtient à partir du précédent en branchant une nouvelle feuille sur l'une des arrêtes. Brancher une feuille ajoute deux arrêtes, si bien qu'il y a 2n-1 choix à chaque étape. Au final, on peut construire 1*1*3*5*7*...*(2n-1) arbre à l'étape n. (Il y a peut-être des décalages d'indice à faire, je n'y ai pas trop réfléchi ici)

    Posté par El Jj, 23 novembre 2012 à 22:38 | | Répondre
  • Salut ! Je lis souvent les articles ici mais ne commente pas, je ne suis pas bien calé en maths. Cependant ici on est plus dans mon domaine alors je vais me le permettre ! En tout cas c’est chouette de voir des explications claires des différentes méthodes de phylogénies, je n’ai jamais osé le faire (peur d’être chiant), ici tu as bien su profiter de l’occasion Donald et moi, blogueurs du blog « les poissons n’existent pas » voulions justement faire un article sur la phylogénie des pokémons mais hop, tu nous as devancés ^^ Cependant, après avoir lu l’article original (pas le tiens hein), je l’ai trouvé assez… mauvais, pour un article de phylogénie. Et je pense qu’il ne serait jamais passé dans une revue de systématique. Donc si tu me le permets, j’aimerais bien plus tard rédiger un article moi aussi sur le sujet sur notre blog, qui serait plus phylogénétique que mathématique. Par exemple on peut tout à fait critiquer le fait que les pokémons sont d’origine aquatique, ce qui revient par ailleurs, à remettre en cause la longue branche de Mr Mime (qui n’implique en plus pas qu’il soit plus évolué !) !

    Je tiens quand même à réagir sur une phrase : "Avant les années 60, la classification des espèces se basait essentiellement sur des caractères observables à l'oeil nu : morphologie, comportement... Les méthodes avaient leurs limites, un même caractère pouvant apparaître à deux endroits différents de l'arbre évolutif. C'est d'ailleurs cette classification qui a donné le regroupement des reptiles, qui n'a plus lieu d'être aujourd'hui.". Ca laisse largement penser que la morphologie entraîne les groupes comme les reptiles. Or c’est faux : la réfutation de ces groupes c’est faite dans un contexte purement morphologique. C’est plus tard que le moléculaire est apparu pour donner des données supplémentaires. La théorie phylogénétique était largement construite quand le moléculaire est arrivé. Les méthodes probabilistes aussi ! D’ailleurs parcimonie et UPGMA ont été mis en place dans un cadre strictement morphologique. Et, je ne sais pas si c’est fait pour ne pas allonger l’article ou pour éviter la redondance avec le bayésien, mais on utilise aussi des méthodes dites de vraisemblances. Certes si je ne me trompe pas, le théorème de Bayes incorpore la fonction de vraisemblance, mais les deux méthodes ne fonctionnent pas et ne sont pas utilisées de la même manière

    Bref, pour ce qui est nos chers monstres de poches, je me réserve les discussions « biologiques pour un prochain article

    Posté par Nicobola, 03 décembre 2012 à 18:53 | | Répondre
  • @Nicobola
    J'ai ajouté quelques phrases dans mon article à propos des reptiles et de UPGMA, pour éviter les malentendus. Je suis conscient que je n'ai fait que survoler l'ensemble des techniques existantes (en particulier les méthodes probabilistes), mais j'ai préféré évoquer les différentes approches, et ne rentrer dans le détail que quand les calculs s'y prêtaient .

    En tout cas, j'attends avec impatience de vous lire sur le même sujet !

    Posté par EL Jj, 03 décembre 2012 à 20:32 | | Répondre
  • @El Jj

    « Merci pour ce long commentaire, j'ai amélioré l'article en fonction ! »
    Oh, les nouveaux arbres avec le code couleur sont mignons tout plein, super, merci =).

    « La démonstration du nombre d'arbre n'est en fait pas bien compliquée si on s'y penche un peu. »
    Ah mais je n’ai jamais dit que c’était compliqué, j’évoquais d’ailleurs « un *petit* paragraphe annexe » ou « *quelques* pistes de réflexion », quelques lignes suffisent comme cela a de fait été montré dans la démonstration .

    Posté par Ethaniel, 04 décembre 2012 à 09:42 | | Répondre
  • Bah pour Mew, considérez que c'est un Pokemon légendaire, donc un truc plus divin que animal. Vu qu'il apprends Morphing, il est sensé avoir une infinité de formes possibles.

    Posté par marciogrelha, 01 mai 2013 à 14:09 | | Répondre
  • Faut éliminer la problématique des Pokemon légendaires qui sont pas sensés se reproduire et qui sont en plus "immortels", donc ni mort, ni vivant.

    Posté par marciogrelha, 01 mai 2013 à 14:13 | | Répondre
Nouveau commentaire
Licence Creative Commons
Ce(tte) œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 3.0 France.