High Speed Tablation System using an FPGA Designed for Distribution Tables of Frequent DNA Subsequences

A method is described for enumerating the frequencies of DNA subsequences on a system comprising a host computer and a field programmable gate array (FPGA) board with one FPGA. Frequencies of subsequences with lengths of up to K₀ + K₁ + K₂ (24 in the current implementation) are enumerated in three phases. In these three phases, subsequences with lengths of up to K₀, K₀ + K₁ and K₀ + K₁ + K₂, respectively, are enumerated; these three phases are executed simultaneously on a pipelined circuit, resulting in high performance. The enumeration of frequent subsequences in databases, which are becoming larger and larger, will enable subsequences that are unique and/or repeatedly used in many parts of the sequences to be found.