Une introduction à la construction et à l’utilisation des Arbres de Suffixes

Travailler sur de grandes chaines de caractères et traiter celles-ci afin d’en extraire les motifs récurrents par correspondance exacte ou approchée est un travail aujourd’hui courant pour les chercheurs en Sciences de la Vie ou en fouille de données. Si l’on ne considère que la base de données GenBank, la taille et le nombre des séquences qui y sont stockées doubles tous les 16 mois. Cette augmentation nécessite par conséquent le développement de méthodes à même de répondre rapidement à de nombreuses requêtes sur des séquences toujours plus grandes, éventuellement distantes. Les arbres de suffixes sont une structure de données à même d’offrir une réponse rapide à des requetes s’apparentant à la recherche de motifs au sein d’une chaine de caractères.

Mots clés : Suffix Tree, Algorithme de Ukkonen, Algorithme de Hunt,TDD (Top-Down Disk-Based technique), recherche de motifs.

• Télécharger