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

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