Encodage linéaire d'automates pondérés. Filtrage de motifs génomiques et application sur l'architecture prototype R-disk
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 FPGA. On peut matérialiser des automates à transitions au moyen de 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. L'encodage linéaire des automates pondérés a été implémenté sur R-disk, 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 peu structurées : on obtient des traitements nouveaux et accélérés pour l'interrogation de banques de données génomiques.
We show that the linear encoding scheme (or one-hot scheme) efficiently simulates weighted finite automata (WFA). Those automata carry weights on every transition and model substitution errors in proteic patterns. Automata with transitions can be avantageously hardwired with operators. This scheme solves pattern matching problems by feeding a pipeline with one character every clock cycle. Such automata are well suited for use in FPGA devices, especially within the R-disk prototype, a hardware architecture devoted to content-based searches inside non-indexed large databanks: data is filtered on-the-fly at the output of storage devices, using distributed and reconfigurable processing elements. This improves the speed of parsing genomic databanks.
M.GIRAUD, S.GUYETANT, D.LAVENIER
banques génomiques, recherche de motifs, automates finis, automates pondérés, encodage linéaire, filtrage, traitements à la volée, architecture reconfigurable, FPGA.
genomic banks, pattern matching, non-deterministic finite automata, weighted finite automata, one-hot encoding, linear encoding, filtering, on-the-fly processing, reconfigurable hardware, FPGA.
Français
|
