title: The position end-set tree: a small automaton for word recognition in biological sequences.
abstract: 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.
authors.affiliation: Genosphere Project, ERATO, JRDC, Tokai University School of Medicine, Kanagawa, Japan.
authors.forename: C
authors.initials: C
authors.lastname: Lefèvre
authors.forename: J E
authors.initials: JE
authors.lastname: Ikeda
mesh_terms: D000465:Algorithms; D001330:Electronic Data Processing; D008838:Microcomputers; D009862:Online Systems; D010363:Pattern Recognition, Automated; D011382:Programming, Linear; D017421:Sequence Analysis