Vidéo pédagogique
Notice
Sous-titrage
Sous-titre
Langue :
Français
Crédits
François Rechenmann (Intervention), Thierry Parmentelat (Intervention)
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.
DOI : 10.60527/r2ec-f682
Citer cette ressource :
François Rechenmann, Thierry Parmentelat. Inria. (2015, 1 juin). 4.5. Un alignement de séquences vu comme un chemin dans une grille , in 4. Comparaison de séquences. [Vidéo]. Canal-U. https://doi.org/10.60527/r2ec-f682. (Consultée le 19 septembre 2024)

4.5. Un alignement de séquences vu comme un chemin dans une grille

Réalisation : 1 juin 2015 - Mise en ligne : 4 octobre 2016
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
Descriptif

Pour comparer deux séquences entre elles, il faut donc les aligner. Aligner ces deux séquences suppose faire des hypothèses d'insertion, délétion, aux bons endroits. Ça signifie, d'un point de vue séquence de caractères, insérer des caractères "blank", le tiret, aux endroits appropriés. Approprié dans quel sens ? Au sens que la distance entre les deux séquences soit minimale. On appliquera le même processus pour toute perte de séquence, et systématiquement, on retiendra comme étant la mesure de similarité, la distance minimale entre cette paire de séquences. Comment déterminer ces endroits d'insertion, de délétion, comment émettre ces hypothèses d'insertion, délétion et obtenir un alignement de coût minimal ? Pour ce faire, nous allons raisonner sur une grille. Ici, telle qu'elle est figurée là, où on a la première séquence en ligne et la seconde séquence à aligner comparée en colonne. Ceci nous définit une grille avec des noeuds numérotés 00 ici, 6-7 ici, dans le cas de deux séquences extrêmement courtes, mais vous l'avez bien vu, de longueurs différentes. Que va être un alignement de ces deux séquences ? Un alignement de ces deux séquences va être un chemin dans la grille qui relie le noeud d'origine au noeud extrémité, ici au noeud de coordonnée 6-7...

Intervention

Dans la même collection

Avec les mêmes intervenants et intervenantes

Sur le même thème