5.4. L’algorithme UPGMA

Auteur(s) : RECHENMANN FRANCOIS, PARMENTELAT THIERRY    01-06-2015,  01-06-2015  Éditeur(s) :    Description : L'algorithme, que nous allons étudier pour la reconstruction d'arbres phylogénétiques à partir des distances, s'appelle UPGMA. Un nom plutôt compliqué pour une méthode qui est plutôt simple. Et même, on le verra trop simple. UPGMA signifie Unweighted Pair Group Method with Arithmetic Mean. Nous allons voir au fur et à mesure, la signification dans l'exécution de l'algorithme de chacun de ces termes. Le point de départ de cet algorithme est donc un tableau de distances, tel que nous avons pu le remplir dans la session précédente. Voilà l'exemple que nous allons traiter. C'est un exemple simple. Nous avons sept espèces différentes et nous avons calculé les distances entre ces espèces à travers le calcul des distances, entre les séquences d'un gène homologue de ces espèces, à toutes ces espèces. Vous vous souvenez que le tableau que nous avons calculé était d'une part symétrique et que d'autre part, les valeurs sur la diagonale étaient sans surprise égales à 0. Ici nous avons choisi de ne conserver et de n'afficher que les valeurs significatives. Donc inutile de montrer les valeurs qui sont les symétriques des autres. Et inutile d'afficher les 0 sur les diagonales. Ce qui explique que notre tableau apparaît incomplet d'une certaine manière. La première étape de l'algorithme consiste à rechercher parmi toutes ces valeurs de distance dans le tableau la plus petite. Ici, c'est 2 et c'est la distance qui sépare l'espèce F de l'espèce C. Raccourci de langage, la distance qui sépare les séquences associées aux espèces F et C. C'est la distance la plus faible. Elle nous pousse donc à grouper ces 2 espèces dans un même sous-graphe en créant un noeud ancêtre ici. Ces 2 espèces sont proches, sont similaires parce qu'elles possèdent un ancêtre commun récent... ERRATUM Sur la slide 3 l’orateur parle de 7 espèces différentes, en fait il y en a 6. Mots-clés libres : génomique, Algorithmique, bioinformatique, biologie cellulaire et moléculaire, Modélisation, arbre phylogénétique Classification générale : Sciences de la vie, Biologie, Biochimie, Ecologie Accès à la ressource : http://www.canal-u.tv/video/inria/5_4_l_algorithme... rtmpt://fms2.cerimes.fr:80/vod/fuscia/changer.l.ec... http://www.canal-u.tv/video/inria/dl.1/5_4_l_algor... Conditions d'utilisation : Droits réservés à l'éditeur et aux auteurs. Ces ressources de cours sont, sauf mention contraire, diffusées sous Licence Creative Commons. L’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications à l’œuvre originale.

DONNEES PEDAGOGIQUES Type pédagogique : cours / présentation Niveau : enseignement supérieur, licence, licence DONNEES TECHNIQUES Format : video/x-flv Taille : 193.36 Mo Durée d'exécution : 5 minutes 16 secondes

Exporter au format XML