IEICE TRANSACTIONS on Information
Accelerating Weeder: A DNA Motif Search Tool Using the Micron Automata Processor and FPGA
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E100-D No.10 pp.2470-2477
- Publication Date
- 2017/10/01
- Publicized
- 2017/06/29
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2017EDP7051
- Type of Manuscript
- PAPER
- Category
- Computer System
Authors
Qiong WANG
National University of Defense Technology
Mohamed EL-HADEDY
University of Illinois Urbana-Champaign
Kevin SKADRON
University of Virginia
Ke WANG
University of Virginia
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Qiong WANG, Mohamed EL-HADEDY, Kevin SKADRON, Ke WANG, "Accelerating Weeder: A DNA Motif Search Tool Using the Micron Automata Processor and FPGA" in IEICE TRANSACTIONS on Information,
vol. E100-D, no. 10, pp. 2470-2477, October 2017, doi: 10.1587/transinf.2017EDP7051.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2017EDP7051/_p
Copy
@ARTICLE{e100-d_10_2470,
author={Qiong WANG, Mohamed EL-HADEDY, Kevin SKADRON, Ke WANG, },
journal={IEICE TRANSACTIONS on Information},
title={Accelerating Weeder: A DNA Motif Search Tool Using the Micron Automata Processor and FPGA},
year={2017},
volume={E100-D},
number={10},
pages={2470-2477},
abstract={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.},
keywords={},
doi={10.1587/transinf.2017EDP7051},
ISSN={1745-1361},
month={October},}
Copy
TY - JOUR
TI - Accelerating Weeder: A DNA Motif Search Tool Using the Micron Automata Processor and FPGA
T2 - IEICE TRANSACTIONS on Information
SP - 2470
EP - 2477
AU - Qiong WANG
AU - Mohamed EL-HADEDY
AU - Kevin SKADRON
AU - Ke WANG
PY - 2017
DO - 10.1587/transinf.2017EDP7051
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E100-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 2017
AB - 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.
ER -
English
