FPGA Based Acceleration of Biological Sequence Alignment Algorithms Based on a Dynamic Programming Approach: A Survey

International Journal of Electronics and Communication Engineering

© 2025 by SSRG - IJECE Journal

Volume 12 Issue 8

Year of Publication : 2025

Authors : Anita Wagh, Prachi Mukherji, Seema Rajput

10.14445/23488549/IJECE-V12I8P105

How to Cite?

Anita Wagh, Prachi Mukherji, Seema Rajput, "FPGA Based Acceleration of Biological Sequence Alignment Algorithms Based on a Dynamic Programming Approach: A Survey," SSRG International Journal of Electronics and Communication Engineering, vol. 12,  no. 8, pp. 51-60, 2025. Crossref, https://doi.org/10.14445/23488549/IJECE-V12I8P105

Abstract:

The rapid growth of biological sequence data necessitates efficient computational methods for sequence alignment, a fundamental task in bioinformatics. In this study, we provide a thorough overview of the literature on the topic of employing Dynamic Programming (DP) to speed up methods for biological sequence alignment using Field-Programmable Gate Arrays (FPGAs). Needleman-Wunsch and Smith-Waterman are two examples of DP algorithms that ensure optimum alignment; nonetheless, they are computationally demanding. FPGAs offer a promising platform for accelerating these algorithms by exploiting parallelism and hardware customization. This survey reviews existing research and methodologies employed to implement sequence alignment algorithms on FPGAs, comparing their performance, scalability, and energy efficiency against traditional CPU-based approaches. We also discuss the challenges and opportunities associated with FPGA-based acceleration, including data dependencies, reconfigurability, and optimization techniques. Hardware-software co-design and advancements in FPGA architectures can further enhance performance and scalability in biological sequence alignment tasks. Alignment accuracy may be improved by using Machine Learning (ML) models like Convolutional Neural Networks (CNNs) to extract features from raw sequence data. In order to facilitate future developments in this dynamic area, the study seeks to enlighten scholars and practitioners on the cutting-edge acceleration methods for biological sequence alignment that are based on FPGAs.

Keywords:

Dynamic Programming, FPGA accelerator, Needleman-Wunsch Algorithm, Sequence alignment, Smith-Waterman Algorithm.

References:

[1] T.F. Smith, and M.S. Waterman, “Identification of Common Molecular Subsequences,” Journal of Molecular Biology, vol. 147, no. 1, pp. 195-197, 1981.
[CrossRef] [Google Scholar] [Publisher Link]
[2] Saul B. Needleman, and Christian D. Wunsch, “A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins,” Journal of Molecular Biology, vol. 48, no. 3, pp. 443-453, 1970.
[CrossRef] [Google Scholar] [Publisher Link]
[3] Robert Giegerich, “A Systematic Approach to Dynamic Programming in Bioinformatics,” Bioinformatics, vol. 16, no. 8, pp. 665-677, 2000.
[CrossRef] [Google Scholar] [Publisher Link]
[4] Stephen F. Altschul et al., “Basic Local Alignment Search Tool,” Journal of Molecular Biology, vol. 215, no. 3, pp. 403-410, 1990.
[CrossRef] [Google Scholar] [Publisher Link]
[5] Licheng Guo et al., “Hardware Acceleration of Long Read Pairwise Overlapping in Genome Sequencing: A Race between FPGA and GPU,” 2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), San Diego, CA, USA, pp. 127-135, 2019.
[CrossRef] [Google Scholar] [Publisher Link]
[6] Laiq Hasan, and Zaid Al-Ars, “An Overview of Hardware-Based Acceleration of Biological Sequence Alignment,” Computational Biology and Applied Bioinformatics, pp. 187-202, 2011.
[CrossRef] [Google Scholar] [Publisher Link]
[7] Jason Chiang et al., “Hardware Accelerator for Genomic Sequence Alignment,” 2006 International Conference of the IEEE Engineering in Medicine and Biology Society, New York, NY, USA, pp. 5787-5789, 2006.
[CrossRef] [Google Scholar] [Publisher Link]
[8] Yoshiki Yamaguchi et al., “High Speed Homology Search using Run-Time Reconfiguration,” Field-Programmable Logic and Applications: Reconfigurable Computing Is Going Mainstream, pp. 281-291, 2002.
[CrossRef] [Google Scholar] [Publisher Link]
[9] S. Margerms, “Reconfigurable Computing in Real-World Applications,” FPGA Structures and ASIC Journal, vol. 10, no. 5, pp. 1-8, 2006.
[Google Scholar]
[10] S. Bojanic et al., “High Speed Circuits for Genetics Applications,” 2004 24th International Conference on Microelectronics, Nis, Serbia, vol. 2, pp. 517-524, 2004.
[CrossRef] [Google Scholar] [Publisher Link]
[11] C.W. Yu et al., “A Smith-Waterman Systolic Cell,” Proceedings of the 13th International Conference on Field Programmable Logic and Applications (FPL), Lisbon, Portugal, pp. 375-384, 2003.
[CrossRef] [Google Scholar] [Publisher Link]
[12] Ardhendu Sarkar, and Som Banerjee, “FPGA Implementation of DNA Sequence Alignment with Traceback,” 2020 4th International Conference on Electronics, Communication and Aerospace Technology (ICECA), Coimbatore, India, pp. 47-52, 2020.
[CrossRef] [Google Scholar] [Publisher Link]
[13] Yu-Cheng Li, and Yi-Chang Lu, “BLASTP-ACC: Parallel Architecture and Hardware Accelerator Design for BLAST-based Protein Sequence Alignment,” IEEE Transactions on Biomedical Circuits and Systems, vol. 13, no. 6, pp. 1771-1782, 2019.
[CrossRef] [Google Scholar] [Publisher Link]
[14] Chirag Kyal, Rishav Kumar, and Adil Zamal, “Performance-based Analogising of Needleman-Wunsch Algorithm to Align DNA Sequences using GPU and FPGA,” 2020 IEEE 17th India Council International Conference (INDICON), New Delhi, India, pp. 1-5, 2020.
[CrossRef] [Google Scholar] [Publisher Link]
[15] Anna Hakim et al., “Performance Analysis of DNA Sequencing Using Smith-Waterman Algorithm on FPGA,” Journal of VLSI Design Tools & Technology, vol. 9, no. 2, pp. 9-15, 2019.
[Google Scholar] [Publisher Link]
[16] Luyi Li, Jun Lin, and Zhongfeng Wang, “PipeBSW: A Two-Stage Pipeline Structure for Banded Smith-Waterman Algorithm on FPGA,” 2021 IEEE Computer Society Annual Symposium on VLSI (ISVLSI), Tampa, FL, USA, pp. 182-187, 2021. [CrossRef] [Google Scholar] [Publisher Link]
[17] Muhammad Irfan, Kizheppatt Vipin, and Rizwan Qureshi, “Accelerating DNA Sequence Analysis using Content-Addressable Memory in FPGAs,” 2023 IEEE 8th International Conference on Smart Cloud (SmartCloud), Tokyo, Japan, pp. 69-72, 2023.
[CrossRef] [Google Scholar] [Publisher Link]
[18] Behnam Khaleghi et al., “SALIENT: Ultra-Fast FPGA-based Short Read Alignment,” 2022 International Conference on Field-Programmable Technology (ICFPT), Hong Kong, pp. 1-10, 2022.
[CrossRef] [Google Scholar] [Publisher Link]
[19] Yi-Lun Liao et al., “Adaptively Banded Smith-Waterman Algorithm for Long Reads and its Hardware Accelerator,” 2018 IEEE 29th International Conference on Application-Specific Systems, Architectures and Processors (ASAP), Milan, Italy, pp. 1-9, 2018.
[CrossRef] [Google Scholar] [Publisher Link]
[20] Amr Ezz El-Din Rashed et al., “Sequence Alignment using Machine Learning-based Needleman–Wunsch Algorithm,” IEEE Access, vol. 9, pp. 109522-109535, 2021.
[CrossRef] [Google Scholar] [Publisher Link]
[21] Amr Ezz El-Din Rashed, Marwa Obaya, and Hossam El~Din Moustafa, “Accelerating DNA Pairwise Sequence Alignment using FPGA and a Customized Convolutional Neural Network,” Computers & Electrical Engineering, vol. 92, 2021.
[CrossRef] [Google Scholar] [Publisher Link]
[22] Osamu Gotoh, “An Improved Algorithm for Matching Biological Sequences,” Journal of Molecular Biology, vol. 162, no. 3, pp. 705-708, 1982.
[CrossRef] [Google Scholar] [Publisher Link]
[23] Stephen F. Altschul, and Bruce W. Erickson, “Optimal Sequence Alignment using Affine Gap Costs,” Bulletin of Mathematical Biology, vol. 48, pp. 603-616, 1986.
[CrossRef] [Google Scholar] [Publisher Link]
[24] T.K. Attwood, and D.J. Parry-Smith, Introduction to Bioinformatics, Pearson PLC, 2003.
[Google Scholar] [Publisher Link]
[25] Peng Chen et al., “Accelerating the Next Generation Long Read Mapping with the FPGA-based System,” IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 11, no. 5, pp. 840-852, 2014.
[CrossRef] [Google Scholar] [Publisher Link]
[26] Jeff Allred et al., “Smith-Waterman Implementation on a FSB-FPGA Module Using the Intel Accelerator Abstraction Layer,” 2009 IEEE International Symposium on Parallel & Distributed Processing, Rome, Italy, pp. 1-4, 2009.
[CrossRef] [Google Scholar] [Publisher Link]
[27] Enzo Rucci et al., “Accelerating Smith-Waterman Alignment of Long DNA Sequences with OpenCL on FPGA,” Proceedings of the 5th International Work-Conference on Bioinformatics and Biomedical Engineering (IWBBIO), Granada, Spain, pp. 500-511, 2017.
[CrossRef] [Google Scholar] [Publisher Link]
[28] Hasitha Muthumala Waidyasooriya, Masanori Hariyama, and Michitaka Kameyama, “FPGA-Accelerator for DNA Sequence Alignment based on an Efficient Data-Dependent Memory Access Scheme,” Highly-Efficient Accelerators and Reconfigurable Technologies, pp. 127-130, 2014.
[Google Scholar] [Publisher Link]
[29] Mostafa Morshedi, and Hamid Noori, “FPGA Implementation of a Short Read Mapping Accelerator,” Proceedings of the 13th International Symposium on Applied Reconfigurable Computing (ARC), Delft, The Netherlands, pp. 289-296, 2017.
[CrossRef] [Google Scholar] [Publisher Link]
[30] Simone Casale-Brunet, Endri Bezati, and Marco Mattavelli, “Design Space Exploration of Dataflow-Based Smith-Waterman FPGA Implementations,” 2017 IEEE International Workshop on Signal Processing Systems (SiPS), Lorient, France, pp. 1-6, 2017.
[CrossRef] [Google Scholar] [Publisher Link]