Subset seed automaton

Gregory Kucherov, Laurent Noé, Mikhail Roytberg

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

8 Citations (Scopus)

Abstract

We study the pattern matching automaton introduced in [1] 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 and present 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.

Original languageEnglish
Title of host publicationImplementation and Application of Automata - 12th International Conference, CIAA 2007, Revised Selected Papers
PublisherSpringer Verlag
Pages180-191
Number of pages12
ISBN (Print)9783540763352
DOIs
Publication statusPublished - 2007
Externally publishedYes
Event12th International Conference on Implementation and Application of Automata, CIAA 2007 - Prague, Switzerland
Duration: 16 Jul 200718 Jul 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4783 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Conference on Implementation and Application of Automata, CIAA 2007
Country/TerritorySwitzerland
CityPrague
Period16/07/0718/07/07

Keywords

  • Automaton
  • Seed sensitivity
  • Spaced seed
  • Subset seed

Fingerprint

Dive into the research topics of 'Subset seed automaton'. Together they form a unique fingerprint.

Cite this