Identifiant pérenne de la notice : 247810126
Notice de type
Notice de regroupement
Note publique d'information : Les recherches de motifs concernent des motifs exacts, pondérés, ou des langages définis
par des distances de similarité ou par des grammaires. Les architectures reconfigurables
traitent efficacement ces recherches dans les banques de données génomiques. La thèse
propose d'étendre l'encodage linéaire aux automates pondérés : les transitions et
les états sont directement matérialisés sur une architecture spécialisée. Nous obtenons
une borne de O(t log t) nouvelles transitions lors de la suppression d'epsilon-transitions
sur un automate rectiligne de taille t. Cette borne est optimale sous une contrainte
d'équivalence par chemins. Nous avons implémenté les automates pondérés sur une architecture
prototype, Rdisk, dans l'outil Wapam. En l'appliquant à une nouvelle méthode bioinformatique
qui filtre un sous-ensemble de traces de séquençage, l'assemblage ciblé, nous avons
découvert plus de 400 nouveaux gènes de récepteurs olfactifs sur un séquençage récent
du chien.