Performance Analysis of DNA Sequencing Using Smith-Waterman Algorithm on FPGA

Anna Hakim, Anam Kashtwari, Rajinder Tiwari, Jamini Sharma

Abstract


The Smith-Waterman algorithm is the most accurate and optimal alignment algorithm for DNA sequencing. It is utilized to locate the ideal local alignment between two sequences. While looking sequence databases that may contain billions of sequences, this algorithm turns out to be computationally costly and tedious. Smith-Waterman algorithm needs additional memory space and this constrains the extent of a sequence to be aligned. In this study we will implement the S-W algorithm on a FPGA board which will speed up the performance execution of the program with less utilization and more efficiency.


Keywords: Bioinformatics, sequence alignment, dynamic programming, Smith-Waterman algorithm, FPGA

Cite this Article
Anna Hakim, Anam Kashtwari, Rajinder Tiwari, Jamini Sharma. Performance Analysis of DNA Sequencing Using Smith-Waterman Algorithm on FPGA. Journal of VLSI Design Tools & Technology. 2019; 9(2): 9–13p.


Full Text:

PDF

References


Xin Chang, Fernando A. Escobar, Carlos Valderrama, and Vincent Robert,“Exploring Sequence Alignment Algorithms on FPGA-based Heterogeneous Architectures,” Proceedings IWBBIO 2014. Granada 7-9 April, 2014.

Deepa B. C, Nagaveni. V Gene Sequencing Parallelization Using Smith-Waterman Algorithm

T. F. Smith, M. S. Waterman, “Identification of Common Molecular Subsequences,” Journal of MolecularBiology, 147(1): pp: 195~197, 1981.

Laiq Hassan,Yahya M.Khawaja A Systolic Architecture for the Smith-Waterman Algorithm with high performance cell design.

Xilinx-Adaptable Intelligent-devices FPGA and 3D ICs http://www.xilinx.com

Field Programmable Gate Array http://en.m.wikipedia.org

Rahul P. Maddimsetty , Jeremy Buhler , Roger D. Chamberlain , Mark A. Franklin , Brandon Harris, Accelerator design for protein sequence HMM search, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia

Y. Sun, P. Li, G. Gu, Y. Wen, Y. Liu, and D. Liu. Accelerating HMMer on FPGAs Using Systolic Array Based Architecture, in proceedings of IEEE International Symposium on Parallel and Distributed Processing (IPDPS), 2009.

K. Benkrid, P. Velentzas, and S. Kasap, "A High Performance Reconfigurable Core for Motif Searching Using Profile HMM, " presented at Adaptive Hardware and Systems, 2008. AHS '08. NASA/ESA Conference on, 2008.

Morales Snchez, Jos Luis, Hardware Design of Algorithm for the Classification of rna sequences, Diss. burgerlijkingenieurcomputerwetenschappen, 2006

John Paul Walters, XiandongMeng, Vipin Chaudhary, Tim Oliver, LeowYuan Yeow, Bertil Schmidt, Darran Nathan, Joseph Landman, MPI-HMMER-Boost:Distributed FPGA Acceleration, The Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology, 2007, Volume 48, Number 3, Page 223

Peiheng Zhang, Guangming Tan, and Guang R. Gao, “Implementation of the Smith Waterman Algorithm on a Reconfigurable Supercomputing Platform,” Proceeding of HPRCTA 07, 1st International workshop on High-performance reconfigurable computing technology and applications, pp 39-48

Ying Liu; Benkrid, K.; Benkrid, A.; Kasap, S., “An FPGA-Based Web Server forHigh Performance Biological Sequence Alignment,” AHS 2009. NASA/ESA Conference on Adaptive Hardware and Systems, 2009, pp.361-368, July 29 2009-Aug. 1 2009

Nathaniel McVicar,Walter L. Ruzzo, and Scott Hauck, “Accelerating ncRNA Homology Search with FPGAs,” Proceedings of the ACM/SIGDA international symposium on Field programmable gate arrays, 2013, pp 43-52

Ouano, M.O.L.,Jongco, G.F.V.M.G.C.D.,and Escabarte, E.B., “FPGA Based AGREP for DNA Microarray Sequence Searching,” Proceedings of International Conference on Computer Engineering and Applications, 2009, pp 217-221

Xiaoqiang Li, Wenting Han, Gu Liu, Hong An, Mu Xu, Wei Zhou, and Qi Li, “ASpeculative HMMER Search Implementation on GPU,” IEEE 26th International Parallel and Distributed Processing Symposium Workshops and PhD Forum, CHINA, 2012.




DOI: https://doi.org/10.37591/jovdtt.v9i2.2287

Refbacks

  • There are currently no refbacks.


Copyright (c) 2019 Journal of VLSI Design Tools & Technology



eISSN: 2249–474X