ISMatch: A real-time hardware accelerator for inexact string matching of DNA sequences on FPGA

Alberto Marchisio; Federico Teodonio; Antonello Rizzi; Muhammad Shafique

doi:10.1016/j.micpro.2023.104763

ISMatch: A real-time hardware accelerator for inexact string matching of DNA sequences on FPGA

Alberto Marchisio, Federico Teodonio, Antonello Rizzi, Muhammad Shafique

Electrical Engineering

Research output: Contribution to journal › Article › peer-review

Abstract

Since DNA strings suffer from variations like mutation, noisy sampling, and transmission, instead of searching for the exact match, the inexact string matching (ISM) of DNA sequences is preferred. Due to the large amount of data and massive data-dependency, the ISM algorithm is not suitable for being implemented into a general-purpose hardware. Towards this, we propose ISMatch, a novel specialized hardware architecture for computing the ISM in a fast and energy-efficient way. Our implementation on a Xilinx Ultrascale+ FPGA shows up to 70× and 2.2× clock cycles reduction compared to the ARM-based and the HLS implementations, respectively.

Original language	English (US)
Article number	104763
Journal	Microprocessors and Microsystems
Volume	97
DOIs	https://doi.org/10.1016/j.micpro.2023.104763
State	Published - Mar 2023

Keywords

DNA sequence
Energy efficiency
FPGA
Hardware accelerator
Hardware design
High Level Synthesis
Inexact string matching
Levenshtein distance
Performance

ASJC Scopus subject areas

Software
Hardware and Architecture
Computer Networks and Communications
Artificial Intelligence

Access to Document

10.1016/j.micpro.2023.104763

Cite this

@article{1dde6692632c4c17a31467e3a3c40691,

title = "ISMatch: A real-time hardware accelerator for inexact string matching of DNA sequences on FPGA",

abstract = "Since DNA strings suffer from variations like mutation, noisy sampling, and transmission, instead of searching for the exact match, the inexact string matching (ISM) of DNA sequences is preferred. Due to the large amount of data and massive data-dependency, the ISM algorithm is not suitable for being implemented into a general-purpose hardware. Towards this, we propose ISMatch, a novel specialized hardware architecture for computing the ISM in a fast and energy-efficient way. Our implementation on a Xilinx Ultrascale+ FPGA shows up to 70× and 2.2× clock cycles reduction compared to the ARM-based and the HLS implementations, respectively.",

keywords = "DNA sequence, Energy efficiency, FPGA, Hardware accelerator, Hardware design, High Level Synthesis, Inexact string matching, Levenshtein distance, Performance",

author = "Alberto Marchisio and Federico Teodonio and Antonello Rizzi and Muhammad Shafique",

note = "Publisher Copyright: {\textcopyright} 2023 The Author(s)",

year = "2023",

month = mar,

doi = "10.1016/j.micpro.2023.104763",

language = "English (US)",

volume = "97",

journal = "Microprocessors and Microsystems",

issn = "0141-9331",

publisher = "Elsevier",

}

TY - JOUR

T1 - ISMatch

T2 - A real-time hardware accelerator for inexact string matching of DNA sequences on FPGA

AU - Marchisio, Alberto

AU - Teodonio, Federico

AU - Rizzi, Antonello

AU - Shafique, Muhammad

PY - 2023/3

Y1 - 2023/3

N2 - Since DNA strings suffer from variations like mutation, noisy sampling, and transmission, instead of searching for the exact match, the inexact string matching (ISM) of DNA sequences is preferred. Due to the large amount of data and massive data-dependency, the ISM algorithm is not suitable for being implemented into a general-purpose hardware. Towards this, we propose ISMatch, a novel specialized hardware architecture for computing the ISM in a fast and energy-efficient way. Our implementation on a Xilinx Ultrascale+ FPGA shows up to 70× and 2.2× clock cycles reduction compared to the ARM-based and the HLS implementations, respectively.

AB - Since DNA strings suffer from variations like mutation, noisy sampling, and transmission, instead of searching for the exact match, the inexact string matching (ISM) of DNA sequences is preferred. Due to the large amount of data and massive data-dependency, the ISM algorithm is not suitable for being implemented into a general-purpose hardware. Towards this, we propose ISMatch, a novel specialized hardware architecture for computing the ISM in a fast and energy-efficient way. Our implementation on a Xilinx Ultrascale+ FPGA shows up to 70× and 2.2× clock cycles reduction compared to the ARM-based and the HLS implementations, respectively.

KW - DNA sequence

KW - Energy efficiency

KW - FPGA

KW - Hardware accelerator

KW - Hardware design

KW - High Level Synthesis

KW - Inexact string matching

KW - Levenshtein distance

KW - Performance

UR - http://www.scopus.com/inward/record.url?scp=85146050413&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85146050413&partnerID=8YFLogxK

U2 - 10.1016/j.micpro.2023.104763

DO - 10.1016/j.micpro.2023.104763

M3 - Article

AN - SCOPUS:85146050413

SN - 0141-9331

VL - 97

JO - Microprocessors and Microsystems

JF - Microprocessors and Microsystems

M1 - 104763

ER -

ISMatch: A real-time hardware accelerator for inexact string matching of DNA sequences on FPGA

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this