ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Auteurs : soumettez
votre article en ligne
Autres revues >>

Technique et Science Informatiques

0752-4072
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 24/6 - 2005  - pp.703-724  - doi:10.3166/tsi.24.703-724
TITRE
Encodage linéaire d'automates pondérés. Filtrage de motifs génomiques et application sur l'architecture prototype R-disk

RÉSUMÉ
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.


ABSTRACT
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.


AUTEUR(S)
Mathieu GIRAUD, Stéphane GUYETANT, Dominique LAVENIER

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.

KEYWORDS
genomic banks, pattern matching, non-deterministic finite automata, weighted finite automata, one-hot encoding, linear encoding, filtering, on-the-fly processing, reconfigurable hardware, FPGA.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (349 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier