Motifs cachés dans les textes

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…