Proposal of Smith-Waterman Algorithm on FPGA to Accelerate the Forward and Backtracking Steps

Overview

Journal PLoS One

Specialties General Medicine
Science

Date 2022 Jun 30

PMID 35772072

Authors

Fabio F de Oliveira

Leonardo A Dias

Marcelo A C Fernandes

Affiliations

Soon will be listed here.

Abstract

In bioinformatics, alignment is an essential technique for finding similarities between biological sequences. Usually, the alignment is performed with the Smith-Waterman (SW) algorithm, a well-known sequence alignment technique of high-level precision based on dynamic programming. However, given the massive data volume in biological databases and their continuous exponential increase, high-speed data processing is necessary. Therefore, this work proposes a parallel hardware design for the SW algorithm with a systolic array structure to accelerate the forward and backtracking steps. For this purpose, the architecture calculates and stores the paths in the forward stage for pre-organizing the alignment, which reduces the complexity of the backtracking stage. The backtracking starts from the maximum score position in the matrix and generates the optimal SW sequence alignment path. The architecture was validated on Field-Programmable Gate Array (FPGA), and synthesis analyses have shown that the proposed design reaches up to 79.5 Giga Cell Updates per Second (GCPUS).

Citing Articles

CUDASW++4.0: ultra-fast GPU-based Smith-Waterman protein sequence database search.

Schmidt B, Kallenborn F, Chacon A, Hundt C BMC Bioinformatics. 2024; 25(1):342.

PMID: 39488701 PMC: 11531700. DOI: 10.1186/s12859-024-05965-6.

References

Liu Y, Maskell D, Schmidt B . CUDASW++: optimizing Smith-Waterman sequence database searches for CUDA-enabled graphics processing units. BMC Res Notes. 2009; 2:73. PMC: 2694204. DOI: 10.1186/1756-0500-2-73. View

Masseroli M, Canakoglu A, Pinoli P, Kaitoua A, Gulino A, Horlova O . Processing of big heterogeneous genomic datasets for tertiary analysis of Next Generation Sequencing data. Bioinformatics. 2018; 35(5):729-736. DOI: 10.1093/bioinformatics/bty688. View

Zhou P, Shi Z . SARS-CoV-2 spillover events. Science. 2021; 371(6525):120-122. DOI: 10.1126/science.abf6097. View

Miller D, Martin M, Harel N, Tirosh O, Kustin T, Meir M . Full genome viral sequences inform patterns of SARS-CoV-2 spread into and within Israel. Nat Commun. 2020; 11(1):5518. PMC: 7606475. DOI: 10.1038/s41467-020-19248-0. View

Courneya J, Mayo A . High-performance computing service for bioinformatics and data science. J Med Libr Assoc. 2018; 106(4):494-495. PMC: 6148605. DOI: 10.5195/jmla.2018.512. View

Houtgast E, Sima V, Bertels K, Al-Ars Z . Hardware acceleration of BWA-MEM genomic short read mapping for longer read lengths. Comput Biol Chem. 2018; 75:54-64. DOI: 10.1016/j.compbiolchem.2018.03.024. View

NEEDLEMAN S, Wunsch C . A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol. 1970; 48(3):443-53. DOI: 10.1016/0022-2836(70)90057-4. View

Franke K, Crowgey E . Accelerating next generation sequencing data analysis: an evaluation of optimized best practices for Genome Analysis Toolkit algorithms. Genomics Inform. 2020; 18(1):e10. PMC: 7120354. DOI: 10.5808/GI.2020.18.1.e10. View

Rognes T . Faster Smith-Waterman database searches with inter-sequence SIMD parallelisation. BMC Bioinformatics. 2011; 12:221. PMC: 3120707. DOI: 10.1186/1471-2105-12-221. View

10.

Van Court T, Herbordt M . Families of FPGA-Based Accelerators for Approximate String Matching. Microprocess Microsyst. 2011; 31(2):135-145. PMC: 3096528. DOI: 10.1016/j.micpro.2006.04.001. View

11.

Chen P, Wang C, Li X, Zhou X . Accelerating the Next Generation Long Read Mapping with the FPGA-Based System. IEEE/ACM Trans Comput Biol Bioinform. 2015; 11(5):840-52. DOI: 10.1109/TCBB.2014.2326876. View

12.

Mazzarelli A, Giancola M, Farina A, Marchioni L, Rueca M, Gruber C . 16S rRNA gene sequencing of rectal swab in patients affected by COVID-19. PLoS One. 2021; 16(2):e0247041. PMC: 7888592. DOI: 10.1371/journal.pone.0247041. View

13.

Nobile M, Cazzaniga P, Tangherloni A, Besozzi D . Graphics processing units in bioinformatics, computational biology and systems biology. Brief Bioinform. 2016; 18(5):870-885. PMC: 5862309. DOI: 10.1093/bib/bbw058. View

14.

Dias L, Damasceno A, Gaura E, Fernandes M . A full-parallel implementation of Self-Organizing Maps on hardware. Neural Netw. 2021; 143:818-827. DOI: 10.1016/j.neunet.2021.05.021. View

15.

Barros W, Dias L, Fernandes M . Fully Parallel Implementation of Otsu Automatic Image Thresholding Algorithm on FPGA. Sensors (Basel). 2021; 21(12). PMC: 8234950. DOI: 10.3390/s21124151. View

16.

Fei X, Dan Z, Lina L, Xin M, Chunlei Z . FPGASW: Accelerating Large-Scale Smith-Waterman Sequence Alignment Application with Backtracking on FPGA Linear Systolic Array. Interdiscip Sci. 2017; 10(1):176-188. DOI: 10.1007/s12539-017-0225-8. View

17.

Lyng G, Sheils N, Kennedy C, Griffin D, Berke E . Identifying optimal COVID-19 testing strategies for schools and businesses: Balancing testing frequency, individual test technology, and cost. PLoS One. 2021; 16(3):e0248783. PMC: 7993807. DOI: 10.1371/journal.pone.0248783. View

18.

Tanjo T, Kawai Y, Tokunaga K, Ogasawara O, Nagasaki M . Practical guide for managing large-scale human genome data in research. J Hum Genet. 2020; 66(1):39-52. PMC: 7728600. DOI: 10.1038/s10038-020-00862-1. View

19.

Rucci E, Garcia C, Botella G, De Giusti A, Naiouf M, Prieto-Matias M . SWIFOLD: Smith-Waterman implementation on FPGA with OpenCL for long DNA sequences. BMC Syst Biol. 2018; 12(Suppl 5):96. PMC: 6245597. DOI: 10.1186/s12918-018-0614-6. View

20.

Smith T, Waterman M . Identification of common molecular subsequences. J Mol Biol. 1981; 147(1):195-7. DOI: 10.1016/0022-2836(81)90087-5. View