The Prague Stringology Club Workshop '98

Glen Herrmannsfeldt

A Highly Parallel Finite State Automaton Processor for Biological Pattern Matching

Finite State Automata are useful for string searching problems mostly because they are fast. For very large problems, a software implementation will not be fast enough. I describe here a parallel implementation of a hardware Deterministic Finite State Automaton processor. It can rapidly search a large database for approximately matching strings, as a filter for more detailed processing later. As the most important parts, large Random Access Memory chips, are continually getting cheaper, it should be possible and affordable to make large arrays of such processors.

Download paper: Article in PostScript Article in PDF
 PostScript   PDF