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

Authors

  • Anna Hakim Student, Department of Electronics and Communication Engineering, Model Institute of Engineering and Technology, Jammu University, Jammu, Jammu and Kashmir, India
  • Anam Kashtwari Student, Department of Electronics and Communication Engineering, Model Institute of Engineering and Technology, Jammu University, Jammu, Jammu and Kashmir, India
  • Rajinder Tiwari Assistant Professor, Department of Electronics and Communication Engineering, Model Institute of Engineering and Technology, Jammu University, Jammu, Jammu and Kashmir, India
  • Jamini Sharma Assistant Professor and HOD, Department of Electronics and Communication Engineering, Model Institute of Engineering and Technology, Jammu University, Jammu, Jammu and Kashmir, India

DOI:

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

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.

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.

Downloads

Published

2019-07-15

Issue

Vol. 9 No. 2 (2019)

Section

Articles

License

Thank you for submitting the manuscript to the Journal of VLSI Design Tools & Technology. With the online journal management system that we are using, you will be able to track its progress through the editorial process by logging in to the journal web site:

An author may request for withdrawal of his/her manuscript, within a week's
time  (w.e.f. the date of submission of the manuscript). The Author is
recommended to follow strictly the Instructions in Manuscript Withdrawal
Policy (As per URL given below)
http://stmjournals.com/pdf/manuscript%20withdrawl.pdf


If you have any questions, please contact me. Thank you for considering this
journal as a venue for your work.