Processing Repetitive Sequence Structures with Mismatches at Streaming Rate

摘要

With the accelerating growth of biological databases and the beginning of genome-scale processing, cost-effective high-performance se-quence analysis remains an essential problem in bioinformatics. We ex-amine the use of FPGAs for finding repetitive structures such as tandem repeats and palindromes under various mismatch models. For all prob-lems addressed here, we process strings in streaming mode and obtain processing times of 5ns per character for arbitrary length strings. Using a Xilinx XC2VP100, we can find: (ⅰ) all repeats up to size 1024, each with any number of mismatches; (ⅱ) all precise tandem arrays with repeats up to size 1024; (ⅲ) all palindromes up to size 256, each with any number of mismatches, or (ⅳ) a somewhat smaller size of (ⅰ) and (ⅲ) with a single insertion or deletion. The speed-up factors range from 250 to 6000 over an efficient serial implementation which is itself many times faster than a direct implementation of a theoretically optimal serial algorithm.