Accelerating String Set Matching in FPGA Hardware for Bioinformatics Research
Author Information
Author(s): Dandass Yoginder S, Burgess Shane C, Lawrence Mark, Bridges Susan M
Primary Institution: Mississippi State University
Hypothesis
Can the Aho-Corasick algorithm be optimized for FPGA implementation to improve performance in proteomics?
Conclusion
The FPGA implementation is nearly 20 times faster than the traditional Aho-Corasick algorithm on a workstation.
Supporting Evidence
- The FPGA implementation achieved storage efficiencies of over 80%.
- The implementation operates at a clock frequency of 100 MHz.
- The FPGA design can be reused for different peptide sets by initializing the RAM block content.
Takeaway
This study shows how to make searching for protein sequences much faster by using special computer chips called FPGAs.
Methodology
The Aho-Corasick algorithm was adapted for FPGA devices, optimizing space and performance by splitting the algorithm into smaller finite state machines.
Limitations
The implementation is limited to searching for a maximum of 4,000 peptides at a time.
Digital Object Identifier (DOI)
Want to read the original?
Access the complete publication on the publisher's website