Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 27 Février 2001

Motifs cachés dans les textes

par Brigitte Vallée (GREYC)

Le problème de la recherche d'un motif donné dans un texte est un probleme très classique et très bien connu d'un double point de vue algorithmique et probabiliste. Ici, le problème traité est plus général, car nous nous intéressons aux occurrences de ce motif lorsque les symboles contigus du motif n'apparaissent plus nécessairement de manière contigue dans le texte. Par exemple, baba n'apparait pas comme motif dans le texte abracadabra, mais il apparait 3 fois comme sous séquence de ce texte: on peut considérer que baba est 3 fois "caché" dans le texte. Ce problème qui se pose naturellement dans des contextes liés à la biologie ou à la sécurité informatique n'a jamais été réellement abordé d'un point de vue probabiliste: on se donne un motif, un ensemble de contraintes sur les écarts acceptés entre les occurrences des symboles du motif, et on se pose la question: que peut-on dire du nombre de fois où le motif apparait comme sous-séquence admise dans un texte aléatoire? La réponse à cette question est essentielle si on veut pouvoir séparer les occurrences anormalement fréquentes (en plus ou en moins) des occurrences normalement fréquentes. Nous répondons ici de manière très précise à la question...

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr