 |
3.6. L’algorithme de Boyer-Moore | |
| Auteur(s) : RECHENMANN FRANCOIS, PARMENTELAT THIERRY
01-06-2015,
01-06-2015
Éditeur(s) : Description : 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... Mots-clés libres : génomique, Algorithmique, bioinformatique, biologie cellulaire et moléculaire, Modélisation Classification générale : Sciences de la vie, Biologie, Biochimie, Ecologie Accès à la ressource : http://www.canal-u.tv/video/inria/3_6_l_algorithme... rtmpt://fms2.cerimes.fr:80/vod/fuscia/des.fenetres... http://www.canal-u.tv/video/inria/dl.1/3_6_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 : 212.77 Mo Durée d'exécution : 5 minutes 44 secondes |
| Exporter au format XML |