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

Qiong WANG  Mohamed EL-HADEDY  Kevin SKADRON  Ke WANG  

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

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

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.