Vidéo pédagogique
Notice
Lieu de réalisation
Grenoble
Sous-titrage
Sous-titre
Langue :
Anglais
Crédits
François Rechenmann (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/c0x5-4639
Citer cette ressource :
François Rechenmann. Inria. (2015, 5 février). 3.6. Boyer-Moore algorithm , in 3. Gene prediction. [Vidéo]. Canal-U. https://doi.org/10.60527/c0x5-4639. (Consultée le 19 mars 2024)

3.6. Boyer-Moore algorithm

Réalisation : 5 février 2015 - Mise en ligne : 9 mai 2017
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
Descriptif

We have seen how we can make gene predictions more reliable through searching for all the patterns,all the occurrences of patterns. We have seen, for example, howif we locate the RBS, Ribosome Binding Site, upstream gene we can make the prediction of the coding sequence more reliable. So it is clear that pattern searching isa central topic in sequence analysis. So let's have a look at searching algorithms for strings or patterns and their performance. First,what we call the naive algorithm. What does it mean? The naive algorithm consists in comparing every letter of the pattern toevery letter of the text, so if N is the length of the stringor the pattern to be searched and M is the length of the searchable text then in the worst case, the number of comparisons to be executed is in the order of M multiplied by M minus N. Let's see why. Let's see this example of a pattern of six characters to be searched in a textof 32 characters. Well you understand the principle,you first compare the first character, if it matches youlook for the second one, if it doesn't match so you just advance of one position and do the comparison again. Here it doesn't match so it's useless to have a look at the other position of the pattern tobe searched and we can go ahead, here this is correct but this is not, so again and again and again.

Intervention

Dans la même collection

Avec les mêmes intervenants et intervenantes