Engineering Commons^™

Regular Expression Synthesis For Blast Two-Hit Filtering, Jordan Bradshaw

Theses and Dissertations

Genomic databases are exhibiting a growth rate that is outpacing Moore's Law, which has made database search algorithms a popular application for use on emerging processor technologies. NCBI BLAST is the standard tool for performing searches against these databases, which operates by transforming each database query into a filter that is subsequently applied to the database. This requires a database scan for every query, fundamentally limiting its performance by I/O bandwidth. In this dissertation we present a functionally-equivalent variation on the NCBI BLAST algorithm that maps more suitably to an FPGA implementation. This variation of the algorithm attempts to reduce …