{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T16:26:25Z","timestamp":1775838385613,"version":"3.50.1"},"reference-count":26,"publisher":"World Scientific Pub Co Pte Ltd","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J CIRCUIT SYST COMP"],"published-print":{"date-parts":[[2019,12,15]]},"abstract":"<jats:p> 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 \u201cSDP: Segmented Dynamic programming\u201d. 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; \u201cNeedleman\u2013Wunsch (NW)\u201d, the widely used program for optimal sequence alignment, and the LCS algorithm, which finds the \u201cLongest Common Subsequence\u201d 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, \u201cGGSEARCH\u201d. We show that our results are much closer to the optimal results than the \u201cGGSEARCH\u201d 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. <\/jats:p>","DOI":"10.1142\/s021812661950227x","type":"journal-article","created":{"date-parts":[[2019,1,11]],"date-time":"2019-01-11T04:20:44Z","timestamp":1547180444000},"page":"1950227","source":"Crossref","is-referenced-by-count":8,"title":["Time Efficient Segmented Technique for Dynamic Programming Based Algorithms with FPGA Implementation"],"prefix":"10.1142","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1111-0304","authenticated-orcid":false,"given":"Talal","family":"Bonny","sequence":"first","affiliation":[{"name":"College of Engineering, University of Sharjah, P.\u00a0O.\u00a0Box 27272, Sharjah, UAE"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ridhwan Al","family":"Debsi","sequence":"additional","affiliation":[{"name":"College of Engineering, University of Sharjah, P.\u00a0O.\u00a0Box 27272, Sharjah, UAE"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohamed Basel","family":"Almourad","sequence":"additional","affiliation":[{"name":"Zayed University, College of Technological Innovation, Dubai, UAE"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2019,2,25]]},"reference":[{"key":"S021812661950227XBIB002","author":"Cao K.","year":"2018","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."},{"key":"S021812661950227XBIB003","doi-asserted-by":"publisher","DOI":"10.1109\/ISSSR.2016.026"},{"key":"S021812661950227XBIB004","volume-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst.","author":"Cao K.","year":"2018"},{"key":"S021812661950227XBIB006","doi-asserted-by":"publisher","DOI":"10.1109\/NetCoM.2009.10"},{"key":"S021812661950227XBIB008","doi-asserted-by":"publisher","DOI":"10.1109\/IVCNZ.2013.6726997"},{"key":"S021812661950227XBIB009","doi-asserted-by":"publisher","DOI":"10.1142\/S021812661750181X"},{"key":"S021812661950227XBIB010","volume":"9","author":"Bonny T.","year":"2018","journal-title":"Int. J. Adv. Comput. Sci. Appl."},{"key":"S021812661950227XBIB011","doi-asserted-by":"publisher","DOI":"10.1109\/PDP.2014.70"},{"key":"S021812661950227XBIB012","doi-asserted-by":"publisher","DOI":"10.1142\/S0218126615500449"},{"key":"S021812661950227XBIB013","doi-asserted-by":"publisher","DOI":"10.1142\/9789814749503_0073"},{"key":"S021812661950227XBIB014","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2016.7798474"},{"key":"S021812661950227XBIB015","doi-asserted-by":"publisher","DOI":"10.1109\/3DIMPVT.2011.53"},{"key":"S021812661950227XBIB016","first-page":"8590","volume-title":"IEEE\/ACM 21st Great Lake Symp. VLSI","author":"Affan Zidan M.","year":"2011"},{"key":"S021812661950227XBIB017","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-011-0185-0"},{"key":"S021812661950227XBIB018","doi-asserted-by":"publisher","DOI":"10.1142\/S0218126617500669"},{"key":"S021812661950227XBIB019","doi-asserted-by":"publisher","DOI":"10.1109\/IEMBS.2011.6090209"},{"key":"S021812661950227XBIB020","volume-title":"5th Cairo Int. Conf. Biomedical Engineering","author":"Bonny T."},{"key":"S021812661950227XBIB021","doi-asserted-by":"publisher","DOI":"10.1109\/CSCI.2014.10"},{"key":"S021812661950227XBIB022","first-page":"443453","author":"Needleman S.","year":"1970","journal-title":"J. Mol. Biol."},{"key":"S021812661950227XBIB023","doi-asserted-by":"publisher","DOI":"10.1145\/322033.322044"},{"key":"S021812661950227XBIB026","first-page":"10","author":"Schatz M. C.","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"S021812661950227XBIB027","doi-asserted-by":"publisher","DOI":"10.1109\/BIBE.2008.4696721"},{"key":"S021812661950227XBIB028","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp533"},{"key":"S021812661950227XBIB029","doi-asserted-by":"publisher","DOI":"10.1109\/PDGC.2012.6449803"},{"key":"S021812661950227XBIB030","doi-asserted-by":"publisher","DOI":"10.1109\/AISP.2012.6313796"},{"key":"S021812661950227XBIB031","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.194"}],"container-title":["Journal of Circuits, Systems and Computers"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S021812661950227X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,13]],"date-time":"2020-01-13T01:17:45Z","timestamp":1578878265000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S021812661950227X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,25]]},"references-count":26,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2019,12,15]]}},"alternative-id":["10.1142\/S021812661950227X"],"URL":"https:\/\/doi.org\/10.1142\/s021812661950227x","relation":{},"ISSN":["0218-1266","1793-6454"],"issn-type":[{"value":"0218-1266","type":"print"},{"value":"1793-6454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,25]]}}}