Octavian CREŢ, Zsolt MATHE, Paul CIOBANU, Sonia MĂRGINEAN, Adrian DĂRĂBANT
A Hardware Algorithm for The Exact Subsequence Matching Problem in DNA Strings

Abstract. This paper introduces an algorithm for DNA string detection and proposes an efficient hardware implementation of it on FPGA devices. Its main application field is intended to be the detection of intron and exon strings in DNA chains, but its applicability is not limited to Genetics. The GenDiv algorithm is based on the dynamic programming method. For the software implementation, the algorithm's complexity is O(m ∙ n), where m and n are the sizes of the two DNA strings being processed; in hardware, after a few adaptations that are presented, the algorithm can be implemented in a systolic array and its running time becomes linear O(m + n). Simultaneously, the necessary circuitry resources in the FPGA chip are also showing a linear trade-off. The simulations and tests that have been run show a gain of speed of several orders of magnitude of the hardware implementation over the software one.

READ THE PDF