Accelaration of the Smith-Waterman Algorithm with traceback on the FPGA

Abstract

The main contribution of this paper is to propose an FPGA implementation of Smith-Waterman algorithm with the traceback. A homology search for genes in the bioinformatics is a fundamental problem to understand these functions. Smith Waterman algorithm is a technique for finding local alignments of a DNA sequence (string) which match a pattern string. We have implemented the Smith-Waterman module with 1024 pattern length in a Xilinx Virtex-7 FPGA XC7VX485T-2FFG1761. The implementation runs in approximately 154MHz clock frequency. In the case of the pattern length is 1024 and the input length is 256k, the computing time of our FPGA implementation is 1822 times faster than the CPU implementation.