Accelerating Weeder: A DNA Motif Search Tool Using the Micron Automata Processor and FPGA

Qiong WANG  Mohamed EL-HADEDY  Kevin SKADRON  Ke WANG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E100-D   No.10   pp.2470-2477
Publication Date: 2017/10/01
Online ISSN: 1745-1361
Type of Manuscript: PAPER
Category: Computer System
Keyword: 
automata processor,  Weeder,  motif search,  FPGA,  

Full Text: PDF(1.7MB)
>>Buy this Article


Summary: 
Motif searching, i.e., identifying meaningful patterns from biological data, has been studied extensively due to its importance in the biomedical sciences. In this work, we seek to improve the performance of Weeder, a widely-used tool for automatic de novo motif searching. Weeder consists of several functions, among which we find that the function oligo_scan, which handles the pattern matching, is the bottleneck, especially when dealing with large datasets. Motivated by this observation, we adopt the Micron Automata Processor (AP) to accelerate the pattern-matching stage of Weeder. The AP is a massively-parallel, non-von-Neumann semiconductor architecture that is purpose-built for symbolic pattern matching. Relying on the fact that AP is capable of performing matching for thousands of patterns in parallel, we develop an AP-accelerated Weeder implementation in this work. In particular, we describe how to map Weeder's pattern matching to the AP chip and use the high-end FPGA on the AP board to postprocess the output from AP. Our experiment shows that the AP-accelerated Weeder achieves 751x speedup on pattern matching, compared to a single-threaded CPU implementation.