MERCURY BLASTN: FASTER DNA SEQUENCE COMPARISON USING A STREAMING HARDWARE ARCHITECTURE

Large-scale DNA sequence comparison, as implemented by BLAST and related algorithms, is one of the pillars of mod-ern genomic analysis. One way to accelerate these com-putations is with a streaming architecture, in which proces-sors are arranged in a pipeline that replicates the multistage structure of the algorithm. To achieve high performance, the processor hardware implementing the critical seed matching and ungapped extension stages of BLAST should be special-ized to execute these stages as quickly as possible. However, accelerating these stages requires solving two key problems: rst, the seed matching stage is not of a form which has traditionally been amenable to hardware acceleration; and second, the accelerated implementation of BLAST should re-tain sensitivity at least comparable to that of the original software. We describe Mercury BLASTN, an FPGA-based imple-mentation of BLAST for DNA. Mercury BLASTN combines a Bloom ltering approach to seed matching with a modi-ed ungapped extension algorithm. On a previous gener-ation FPGA hardware platform, Mercury BLASTN runs 5 to 11 times faster than NCBI BLASTN current-generation general-purpose CPUs, with the prospect of a further eight-fold speedup on current-generation FPGAs. Moreover, its sensitivity to signicant DNA sequence alignments is 99% of that observed with software NCBI BLASTN. 1