Vidéo pédagogique

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

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

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...

Intervenants
Thèmes
Notice
Sous-titrage
Sous-titre
Langue :
Français
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:
Inria. (2015, 1 juin). 4.5. Un alignement de séquences vu comme un chemin dans une grille. [Vidéo]. Canal-U. https://www.canal-u.tv/87347. (Consultée le 4 juillet 2022)
Contacter
Documentation

Dans la même collection

Avec les mêmes intervenants

Sur le même thème