title: Single Pass Streaming BLAST on FPGAs.
abstract: Approximate string matching is fundamental to bioinformatics and has been the subject of numerous FPGA acceleration studies. We address issues with respect to FPGA implementations of both BLAST- and dynamic-programming- (DP) based methods. Our primary contribution is a new algorithm for emulating the seeding and extension phases of BLAST. This operates in a single pass through a database at streaming rate, and with no preprocessing other than loading the query string. Moreover, it emulates parameters turned to maximum possible sensitivity with no slowdown. While current DP-based methods also operate at streaming rate, generating results can be cumbersome. We address this with a new structure for data extraction. We present results from several implementations showing order of magnitude acceleration over serial reference code. A simple extension assures compatibility with NCBI BLAST.
authors.affiliation: Department of Electrical and Computer Engineering, Boston University; Boston, MA 02215, Web: http://www.bu.edu/caadlab .
authors.forename: Martin C
authors.initials: MC
authors.lastname: Herbordt
authors.forename: Josh
authors.initials: J
authors.lastname: Model
authors.forename: Bharat
authors.initials: B
authors.lastname: Sukhwani
authors.forename: Yongfeng
authors.initials: Y
authors.lastname: Gu
authors.forename: Tom
authors.initials: T
authors.lastname: Vancourt