Time efficient segmented technique for dynamic programming based algorithms with FPGA implementation

ORCID Identifiers

0000-0003-1111-0304

Document Type

Article

Source of Publication

Journal of Circuits, Systems and Computers

Publication Date

12-15-2019

Abstract

© 2019 World Scientific Publishing Company. Although dynamic programming (DP) is an optimization approach used to solve a complex problem fast, the time required to solve it is still not efficient and grows polynomially with the size of the input. In this contribution, we improve the computation time of the dynamic programming based algorithms by proposing a novel technique, which is called "SDP: Segmented Dynamic programming". SDP finds the best way of splitting the compared sequences into segments and then applies the dynamic programming algorithm to each segment individually. This will reduce the computation time dramatically. SDP may be applied to any dynamic programming based algorithm to improve its computation time. As case studies, we apply the SDP technique on two different dynamic programming based algorithms; "Needleman-Wunsch (NW)", the widely used program for optimal sequence alignment, and the LCS algorithm, which finds the "Longest Common Subsequence" between two input strings. The results show that applying the SDP technique in conjunction with the DP based algorithms improves the computation time by up to 80% in comparison to the sole DP algorithms, but with small or ignorable degradation in comparing results. This degradation is controllable and it is based on the number of split segments as an input parameter. However, we compare our results with the well-known heuristic FASTA sequence alignment algorithm, "GGSEARCH". We show that our results are much closer to the optimal results than the "GGSEARCH" algorithm. The results are valid independent from the sequences length and their level of similarity. To show the functionality of our technique on the hardware and to verify the results, we implement it on the Xilinx Zynq-7000 FPGA.

ISSN

0218-1266

Publisher

World Scientific Publishing Co. Pte Ltd

Volume

28

Issue

13

First Page

1950227

Disciplines

Computer Sciences

Keywords

Dynamic programming, FPGA, LCS, NW, performance, time complexity

Scopus ID

85062242520

Indexed in Scopus

yes

Open Access

no

Link to Full Text

Share

COinS