Subset seed automaton

Gregory Kucherov 1, 2 Laurent Noé 1, 2, * Mihkail Roytberg 3
* Auteur correspondant
2 SEQUOIA - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : We study the pattern matching automaton introduced in [KucherovNoeRoytbergJBCB06] for the purpose of seed-based similarity search. We show that our definition provides a compact automaton, much smaller than the one obtained by applying the Aho-Corasick construction. We study properties of this automaton andpresent an efficient implementation of the automaton construction. We also present some experimental results and show that this automaton can be successfully applied to more general situations.
Liste complète des métadonnées

https://hal.inria.fr/inria-00170414
Contributeur : Laurent Noé <>
Soumis le : vendredi 7 septembre 2007 - 16:38:24
Dernière modification le : mardi 6 mars 2018 - 17:40:54
Document(s) archivé(s) le : jeudi 8 avril 2010 - 21:45:41

Fichiers

main.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Gregory Kucherov, Laurent Noé, Mihkail Roytberg. Subset seed automaton. CIAA 2007, Jul 2007, Prague, Czech Republic. 4783, pp.180-191, 2007, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/y824l20554002756/〉. 〈10.1007/978-3-540-76336-9_18〉. 〈inria-00170414〉

Partager

Métriques

Consultations de la notice

298

Téléchargements de fichiers

127