Header menu link for other important links
X
Hardware-Algorithm Codesign for Fast and Energy Efficient Approximate String Matching on FPGA for Computational Biology
V.Y. Gudur, S. Maheshwari, S. Bhardwaj, , R. Shafik
Published in
2022
Volume: 2022-July
   
Pages: 87 - 90
Abstract
Myers bit-vector algorithm for approximate string matching (ASM) is a dynamic programming based approach that takes advantage of bit-parallel operations. It is one of the fastest algorithms to find the edit distance between two strings. In computational biology, ASM is used at various stages of the computational pipeline, including proteomics and genomics. The computationally intensive nature of the underlying algorithms for ASM operating on the large volume of data necessitates the acceleration of these algorithms. In this paper, we propose a novel ASM architecture based on Myers bit-vector algorithm for parallel searching of multiple query patterns in the biological databases. The proposed parallel architecture uses multiple processing engines and hardware/software codesign for an accelerated and energy-efficient design of ASM algorithm on hardware. In comparison with related literature, the proposed design achieves 22× better performance with a demonstrative energy efficiency of 500× 10^{9 cell updates per joule. © 2022 IEEE.}, keywords={Bioinformatics; Computational efficiency; Dynamic programming; Energy efficiency; Field programmable gate arrays (FPGA); Integrated circuit design; Molecular biology; Parallel architectures; String searching algorithms, Approximate string matching; Bit-parallel; Bit-vector algorithms; Co-designs; Computational biology; Edit distance; Energy efficient; Fast algorithms; Hardware algorithm; Parallel operations, Hardware-software codesign, algorithm; biology; computer; energy conservation; software, Algorithms; Computational Biology; Computers; Conservation of Energy Resources; Software}, publisher={Institute of Electrical and Electronics Engineers Inc.}, issn={1557170X}, isbn={9781728127828}, pubmed_id={36086088}, language={English}, abbrev_source_title={Proc. Annu. Int. Conf. IEEE Eng. Med. Biol. Soc. EMBS}, document_type={Conference Paper}, source={Scopus},
About the journal
JournalProceedings of the Annual International Conference of the IEEE Engineering in Medicine and Biology Society, EMBS