Introduction à l’algorithmique du texte pour la bio informatique

Introduction `a l’algorithmique du texte pour la bioinformatiqueM1 Bioinformatique 2009-2010, 8h cours + 8h TDMathieu Raffinot3 d´ecembre 2009Table des mati`eres1 Introduction 22 Recherche exacte 22.1 Cadre de la recherche d’un mot dans un texte . . . . . . . . . . . . . . . . . . 2∗2.2 Recherche avant par l’automate Σ p . . . . . . . . . . . . . . . . . . . . . . . 42.2.1 Algorithme de Morris-Pratt . . . . . . . . . . . . . . . . . . . . . . . . 52.2.2 Algorithme de Knuth-Morris-Pratt . . . . . . . . . . . . . . . . . . . . 92.2.3 Algorithme de Simon . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.2.4 Shift-And . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.3 Comment faire mieux? La recherche arri`ere par facteurs . . . . . . . . . . . . 152.3.1 Approche BDM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.3.2 BNDM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.4 Recherche d’expression r´eguli`ere . . . . . . . . . . . . . . . . . . . . . . . . . 192.4.1 Parsing en arbre binaire . . . . . . . . . . . . . . . . . . . . . . . . . . 202.4.2 Strat´egies de recherche exacte . . . . . . . . . . . . . . . . . . . . . . . 212.4.3 Automate de Thompson . . . . . . . . . . . . . . . . . . . . . . . . . . 212.4.4 Recherche avec l’automate de Thompson. . . . . . . . . . . . . . . . . 232.4.5 Sur le report des occurrences . . . . . . . . . . . . . . . . . . . . . . . 233 Recherche ...