Mathieu Giraud
IRISA / Université de Rennes 1, projet Symbiose
Architectures reconfigurables pour la recherche par automates de motifs dans les séquences génomiques
Soutenue le vendredi 2 décembre 2005, IRISA, Université de Rennes 1
http://www.lifl.fr/~giraud
Rapporteurs :
Les automates pondérés sont des automates avec des poids sur les transitions. En biologie, ils modélisent les erreurs de substitution utilisées dans les motifs représentant des domaines fonctionnels au sein des protéines. Nous montrons que l'encodage linéaire (one-hot) permet de simuler efficacement les automates finis ainsi que les automates pondérés grâce au parallélisme massif de solutions matérielles comme celui des circuits reconfigurables FPGAs. On matérialise des automates à t transitions au moyen de O(t) opérateurs matériels et résoudre des problèmes de recherche de motifs de manière pipelinée en acceptant un caractère par cycle.
Lorsqu'on ajoute des transitions d'insertion et de délétion, les automates pondérés sont au moins aussi expressifs que les méthodes de programmation dynamique. L'implémentation matérielle des epsilon-transitions étant limitée, nous étudions leur suppression sous l'angle du décompte de nouvelles transitions. Par une méthode récursive, nous supprimons les epsilon-transitions d'automates rectilignes avec n transitions au moyen de O(n log n) nouvelles transitions. Cette borne est optimale si l'on impose une contrainte d'équivalence par chemins.
L'encodage linéaire des automates pondérés a été implémenté sur Rdisk, une architecture spécialisée offrant des traitements à la volée à la sortie de dispositifs de stockage pour la recherche par le contenu sur de grandes banques de données faiblement structurées : des traitements nouveaux et accélérés sont obtenus lors de l'interrogation de banques de données génomiques. L'application résultante, WAPAM, a été intégrée à la plateforme web OuestGenopole.
Nous avons utilisé WAPAM dans une nouvelle méthode bioinformatique de découverte de gènes, l'assemblage ciblé, qui sélectionne un sous-ensemble de traces de séquençage réduit afin de n'assembler que les parties utiles. Cette méthode a découvert plus de 400 nouveaux gènes de récepteurs olfactifs chez le chien avant la publication de l'assemblage complet.
Mots-clés : banques génomiques, recherche de motifs, automates finis, automates pondérés, encodage linéaire, filtrage, traitements à la volée, architecture reconfigurable, FPGA, séquençage, assemblage, découverte de gènes.
Les liens ci-dessous sont des fichiers .ps, contactez-moi si vous avez besoin de .pdf.