A Highly Parallel Finite State Automaton Processor for Biological Pattern Matching

Abstract. Finite State Automata are useful for string searching problems mostly because they are fast. For very large problems, a software implemen-tation 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 lter for more detailed processing later. As the most important parts, large Random Access Memory chips, are continually getting cheaper, it should be possible and aordable to make large arrays of such processors. Key words: nite automata, approximate string matching, high-speed search-ing, deterministic nite automata, massive parallelism 1 Finite State Automata for Biology An important problem in contemporary molecular biology is sequence comparison. One would like to compare DNA or protein sequences against other DNA or protein sequences and nd ones that are most similar. As the database of known DNA and protein sequences is growing exponentially, this problem is continually getting harder. It is useful to have a machine to rapidly compare a group of sequences against a large disk le of sequences and indicate which ones match most closely. All the examples will be done using a DNA alphabet size of four. The DNA database is much larger than the protein database, and so the larger, faster, processors are needed here rst. The processors should be designed to also handle the protein 20 character alphabet. This paper describes the design of hardware implementations of Finite State Au-tomata [HU79][W87] for processing biological sequences. In all cases described here, the Finite State Automata are Deterministic, though sometimes the acronym FSA will be used instead of DFSA or DFA