使用FM-Index的硬件可编程自定义计算机字符串匹配国际研讨会( IEEE International Symposium on Field-Programmable Custom Computing Machines String Matching in Hardware using the FM-Index )

WNSL Edward Fern

—String matching is a ubiquitous problem that arises in a wide range of applications in computing, e.g., packet routing, intrusion detection, web querying, and genome analysis. Due to its importance, dozens of algorithms and several data structures have been developed over the years. A recent breakthrough in this field is the FM-index, a data structure that synergistically combines the Burrows-Wheeler transform and the suffix array. In software, the FM-index allows searching (exact and approximate) in times comparable to the fastest known indices for large texts (suffix trees and suffix arrays), but has the additional advantage of being more space-efficient than those approaches. In this paper, we describe the first FPGA-based hardware implementation of the FM-index for exact pattern matching. We report experimental results on the problem of mapping short DNA sequences to a reference genome. We show that the throughput of the FM-index is significantly higher than the nave (brute force) approach. Like the Bowtie software tool, the FM-index can abandon early the hardware matching. It outperforms Bowtie by two orders of magnitude . I.

SciDown文献求助系统（解决99%问题） Public Download FreePatentsOnline Citeseer core.ac.uk en.zl50.com Citeseer pdfs.semanticscholar.org cial.csie.ncku.edu.tw