Vidéo pédagogique

5.4. L’algorithme UPGMA

Durée : 00:05:15 -Réalisation : 1 juin 2015 -Mise en ligne : 1 juin 2015
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
  • audio 1 audio 2 audio 3
Descriptif

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.

Intervenant
Thème
Notice
Sous-titrage
Sous-titre
Langue :
Français
Crédits
François Rechenmann (Intervenant), Thierry Parmentelat (Intervenant)
Conditions d'utilisation
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.
Citer cette ressource :
François Rechenmann, Thierry Parmentelat. Inria. (2015, 1 juin). 5.4. L’algorithme UPGMA. [Vidéo]. Canal-U. https://www.canal-u.tv/87361. (Consultée le 22 septembre 2023)
Contacter
Documentation

Dans la même collection

  • 5.6. La diversité des algorithmes informatiques
    Vidéo pédagogique
    00:07:56
    5.6. La diversité des algorithmes informatiques
    Rechenmann
    François
    Parmentelat
    Thierry

    Nous n'avons vu dans ce cours qu'un exemple extrêmement réduit d'algorithme bio informatique. Il existe en effet une très grande diversité de ces algorithmes bio informatiques qui sont motivés par l

  • 5.2. L’arbre, objet abstrait
    Vidéo pédagogique
    00:03:11
    5.2. L’arbre, objet abstrait
    Rechenmann
    François
    Parmentelat
    Thierry

    Vous l'aurez compris un arbre phylogénétique est un arbre abstrait qui n'a qu'un lointain rapport métaphorique avec un véritable arbre. L'arbre des bio-informaticiens et des informaticiens se

  • 5.1. L’arbre des espèces
    Vidéo pédagogique
    00:05:03
    5.1. L’arbre des espèces
    Rechenmann
    François
    Parmentelat
    Thierry

    Dans cette cinquième et dernière partie de notre cours sur le génome et les algorithmes, qui se veut une introduction à l'analyse informatique de l'information génétique, nous regarderons de plus près

  • 5.5. Quand les différences sont trompeuses
    Vidéo pédagogique
    00:05:52
    5.5. Quand les différences sont trompeuses
    Rechenmann
    François
    Parmentelat
    Thierry

    Il y a plusieurs raisons pour lesquelles la méthode UPGMA, que nous venons de voir, se révèle simpliste. L'une des raisons par exemple, c'est pourquoi quand on recalcule les distances, quand on a

  • 5.3. Remplir un tableau de distances
    Vidéo pédagogique
    00:04:02
    5.3. Remplir un tableau de distances
    Rechenmann
    François
    Parmentelat
    Thierry

    Pour tenter de construire l'arbre phylogénétique d'un ensemble d'espèces, nous allons utiliser les données et génotypique ou des données génotypiques disponibles sur ces espèces. Plus clairement, nous

  • 5.7. Les applications en microbiologie
    Vidéo pédagogique
    00:07:15
    5.7. Les applications en microbiologie
    Rechenmann
    François
    Parmentelat
    Thierry

    Une très grande diversité, on l'a vu, d'algorithmes en bio-informatique, motivé par la résolution de problèmes différents. Ces algorithmes, ces recherches en bio-informatique, s'appuient sur des

Avec les mêmes intervenants

  • 5.6. La diversité des algorithmes informatiques
    Vidéo pédagogique
    00:07:56
    5.6. La diversité des algorithmes informatiques
    Rechenmann
    François
    Parmentelat
    Thierry

    Nous n'avons vu dans ce cours qu'un exemple extrêmement réduit d'algorithme bio informatique. Il existe en effet une très grande diversité de ces algorithmes bio informatiques qui sont motivés par l

  • 4.8. Un algorithme récursif
    Vidéo pédagogique
    00:06:17
    4.8. Un algorithme récursif
    Rechenmann
    François
    Parmentelat
    Thierry

    Nous avons désormais en main tous les éléments pour écrire notre algorithme de détermination d'un alignement optimal, ici d'un chemin optimal. Avec les notations que nous avons introduites, je vous

  • 5.2. L’arbre, objet abstrait
    Vidéo pédagogique
    00:03:11
    5.2. L’arbre, objet abstrait
    Rechenmann
    François
    Parmentelat
    Thierry

    Vous l'aurez compris un arbre phylogénétique est un arbre abstrait qui n'a qu'un lointain rapport métaphorique avec un véritable arbre. L'arbre des bio-informaticiens et des informaticiens se

  • 5.5. Quand les différences sont trompeuses
    Vidéo pédagogique
    00:05:52
    5.5. Quand les différences sont trompeuses
    Rechenmann
    François
    Parmentelat
    Thierry

    Il y a plusieurs raisons pour lesquelles la méthode UPGMA, que nous venons de voir, se révèle simpliste. L'une des raisons par exemple, c'est pourquoi quand on recalcule les distances, quand on a

  • 4.7. Coûts et alignement
    Vidéo pédagogique
    00:04:39
    4.7. Coûts et alignement
    Rechenmann
    François
    Parmentelat
    Thierry

    Nous avons vu l'ébauche de notre algorithme d'alignement optimal en considérant la possibilité de calculer le coût optimal, ou score optimal, de ce dernier noeud. Et nous avons vu que le coût de ce

  • 5.1. L’arbre des espèces
    Vidéo pédagogique
    00:05:03
    5.1. L’arbre des espèces
    Rechenmann
    François
    Parmentelat
    Thierry

    Dans cette cinquième et dernière partie de notre cours sur le génome et les algorithmes, qui se veut une introduction à l'analyse informatique de l'information génétique, nous regarderons de plus près

  • 4.10. Cet algorithme est-il efficace ?
    Vidéo pédagogique
    00:07:07
    4.10. Cet algorithme est-il efficace ?
    Rechenmann
    François
    Parmentelat
    Thierry

    La version itérative de notre algorithme d'alignement optimal de séquences est indéniablement beaucoup plus efficace que sa version récursive, puisque nous avons vu qu'il permettait d'éviter que le

  • 4.2. Évolution et similarité de séquences
    Vidéo pédagogique
    00:03:43
    4.2. Évolution et similarité de séquences
    Rechenmann
    François
    Parmentelat
    Thierry

    Avant de chercher à quantifier ce qu'est la similarité de séquence, on peut se poser la question même de savoir pourquoi des séquences de génome sont similaires entre organismes. La réponse tient dans

  • 5.3. Remplir un tableau de distances
    Vidéo pédagogique
    00:04:02
    5.3. Remplir un tableau de distances
    Rechenmann
    François
    Parmentelat
    Thierry

    Pour tenter de construire l'arbre phylogénétique d'un ensemble d'espèces, nous allons utiliser les données et génotypique ou des données génotypiques disponibles sur ces espèces. Plus clairement, nous

Sur le même thème