Parallel Implementation of Smith-Waterman Algorithm on FPGA
Oliveira, F. O. F. d.; Dias, L. A.; Fernandes, M.
Show 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).
Matching journals
The top 3 journals account for 50% of the predicted probability mass.
Similar papers in this journal
- GPU Accelerated Adaptive Banded Event Alignment for Rapid Comparative Nanopore Signal Analysis 94%
- An FPGA-based hardware accelerator supporting sensitivesequence homology filtering with profile hidden Markovmodels 94%
- CUDASW++4.0: Ultra-fast GPU-based Smith-Waterman Protein Sequence Database Search 94%
Similar papers in this journal
- A Convolution Based Computational Approach Towards DNA N6-methyladenine Site Identification and Motif Extraction in Rice Genome 93%
- A Robust Spike Sorting Method based on the Joint Optimization of Linear Discrimination Analysis and Density Peaks 92%
- Reconstruction Algorithms for DNA-Storage Systems 92%
"Similar papers" are the closest papers from that journal in the model's embedding space. They show what the match is built on, but the ranking comes mostly from a classifier over the whole training set, not from these examples alone.