Recherche multiple d'association d'expressions régulières flexibles dans les grandes séquences génétiques

Robin Gras 1
1 REPCO - Knowledge Representation
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Résumé : Nous nous intéressons à la recherche de motifs particuliers dans les grandes séquences génétiques. Bien que motivés par une application biologique, les résultats présentés restent applicable à n'importe quel type de séquences. Nous présentons un algorithme permettant la recherche de co-occurrence de motifs de type expression régulière avec erreurs. Nous utilisons le langage A défini par Myers comme formalisme de représentation des motifs complexes que nous recherchons. Ce langage permet de définir l'association de deux motifs comme la présence du second à un intervalle de distances donné du premier. Notre algorithme est basé sur un pré-traitement de la séquence à analyser, en temps linéaire par rapport à sa taille, sous forme d'arbre des suffixes. Nous utilisons tout d'abord l'arbre comme "support" d'un algorithme de programmation dynamique optimisé qui cherche tous les appariements différents entre le premier motif et les mots de la séquence. Dans une deuxième étape, nous utilisons l'arbre pour trouver toutes les occurrences dans la séquence des appariements préalablement identifiés. Ceci s'effectue en temps linéaire sur le nombre d'occurrences. Enfin, nous utilisons l'arbre pour élaguer les recherches successives des motifs associés en limitant les parcours de l'arbre lors de la première étape aux seuls sous-mots de l'arbre susceptibles de se trouver dans l'intervalle de distance autorisé du motif précédent. L'ordre dans lequel sont recherchés les sous-motifs influe considérablement sur l'efficacité de la recherche. En effet, moins un sous-motif a d'occurrences et moins il y aura de positions possible pour le prochain sous-motif corrélé et donc plus l'élagage sera efficace. Nous proposons un critère, uniquement basé sur le nombre de sous-mots différents qui peuvent s'apparier avec un sous-motif, représentant le nombre potentiel d'occurrences d'un sous-motif donné par rapport à une séquence aléatoire et cela sans avoir recours à une simulation. Nous utilisons ce critère pour déterminer un ordre de recherche des sous-motifs optimum vis à vis du nombre d'opérations nécessaire pour la recherche du motif complet. Une fois l'arbre des suffixes construit, cet algorithme permet de faire des recherches de motifs complexes en un temps indépendant de la taille de la séquence. Il s'avère donc particulièrement adapté et meilleur que celui de Myers pour faire des recherches multiples de tels motifs dans les grandes séquences génétiques.
Type de document :
Rapport
[Rapport de recherche] RR-3240, INRIA. 1997
Liste complète des métadonnées

https://hal.inria.fr/inria-00073449
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 12:50:10
Dernière modification le : mercredi 16 mai 2018 - 11:23:04
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:46:58

Fichiers

Identifiants

  • HAL Id : inria-00073449, version 1

Citation

Robin Gras. Recherche multiple d'association d'expressions régulières flexibles dans les grandes séquences génétiques. [Rapport de recherche] RR-3240, INRIA. 1997. 〈inria-00073449〉

Partager

Métriques

Consultations de la notice

103

Téléchargements de fichiers

250