Abstract FR:

Ce travail presente differentes methodes pour la recherche approchee, a erreurs pres, d'un motif p dans un texte t. Les erreurs considerees sont les substitutions de caracteres et les motifs sont, soit un mot, soit une classe de mots sur un alphabet. Deux des approches les plus efficaces, en theorie et en pratique, pour la recherche approchee sont les approches de type numerique qui se basent sur la manipulation de mots machine, et les approches de type boyer-moore. Nous avons concu une nouvelle methode de recherche qui tire profit, a la fois de l'efficacite de la demarche boyer-moore, et de la rapidite de programmation des algorithmes numeriques et en particulier de l'algorithme shift-add de baeza-yates et gonnet. Lorsque le mot n'est pas trop long, l'algorithme obtenu est lineaire dans le pire des cas. Si, de plus, l'alphabet est suffisamment grand, l'algorithme est sous-lineaire en moyenne. Une facon naturelle d'aborder le probleme de la recherche approchee consiste a construire un automate fini deterministe reconnaissant le langage l#p#,#k forme de tous les mots qui sont a une distance de p. Le probleme de cette approche par automate est que le temps de construction et la taille d'un tel automate sont importants. Nous montrons que, meme en considerant l'automate minimal reconnaissant l#p#,#k, l'espace memoire utilise reste grand. Nous nous interessons plus particulierement a appliquer les techniques de recherche approchee dans le cas de la prediction de motifs biologiques structures, et plus specialement des genes d'arnt. Notre nouvel algorithme fastrna est une amelioration de l'algorithme trnascan de fichant-burks du point de vue des resultats biologiques et de la rapidite d'execution. Le taux de reconnaissance obtenu pour differentes sequences biologiques est proche de 99%.