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/gbyc-tk29
Citer cette ressource :
François Rechenmann, Thierry Parmentelat. Inria. (2015, 1 juin). 3.6. L’algorithme de Boyer-Moore , in 3. Prédiction des gènes. [Vidéo]. Canal-U. https://doi.org/10.60527/gbyc-tk29. (Consultée le 24 juillet 2024)

3.6. L’algorithme de Boyer-Moore

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

Vous avez compris que la recherche de motifs, c'est-à-dire de sous-chaînes de caractères dans une chaîne plus importante, était un composant important de beaucoup d'algorithmes de bio-informatique. Les algorithmiciens ont toujours cette obsession de l'efficacité de leurs algorithmes. Pourquoi ? Parce qu'on travaille sur des textes qui sont assez longs, on en a vu des ordres de grandeur, et moins, on aura à faire de comparaison, plus rapide sera l'exécution de nos algorithmes. 

Donc, travailler sur l'efficacité des algorithmes de recherche de motifs est largement justifié. Regardons en effet, quelle est l'efficacité de l'algorithme qu'on appelle naïf ? Naïf au sens de : on applique l'algorithme le plus basique auquel on pourrait penser. De quoi s'agit-il ? Vous avez un motif ici de taille 6, qui est le motif à rechercher dans un texte, dans une séquence plus longue de longueur M. Comment faites-vous ? Eh bien, vous placez votre motif au début de la séquence et vous comparez : ici ça correspond, ici ça ne correspond pas. Donc, ce n'est pas la peine de continuer, j'avance mon motif d'une position. Et je refais la comparaison avec la première lettre, il n'y a pas de correspondance. J'avance. Comparaison avec la première lettre, une correspondance. Par contre ici, G et A ne sont pas en correspondance. J'avance. Ici même chose, le A "match" comme on dit avec la position courante de la séquence. Par contre, pas la lettre suivante. Donc j'avance même chose, j'avance. Ici, correspondance, correspondance, pas de correspondance. Donc j'avance et ainsi de suite jusqu'à effectivement trouver ou pas une occurrence de mon motif dans la séquence complète...

Intervention

Dans la même collection

Avec les mêmes intervenants et intervenantes

Sur le même thème