For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2017/10/01
Online ISSN: 1745-1361
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.