The position end-set tree: a small automaton for word recognition in biological sequences.
We consider the basic function which locates a specific string of symbols within a longer sequence. When one is expecting to do many substring searches it is worthwhile to build an auxiliary index to the sequence to aid in the search. We propose a method to generate a compact index that can be viewed as a small (partial) deterministic finite automaton recognizing the subword structure of a sequence. We present an algorithm for its construction on-line in linear time. Such a data structure permits the efficient localization of subwords in a sequence and can be used in the development of interactive sequence analysis software.
Lefèvre
C
C
Genosphere Project, ERATO, JRDC, Tokai University School of Medicine, Kanagawa, Japan.
Ikeda
J E
JE
D000465:Algorithms; D001330:Electronic Data Processing; D008838:Microcomputers; D009862:Online Systems; D010363:Pattern Recognition, Automated; D011382:Programming, Linear; D017421:Sequence Analysis