Hardware implementation of efficient path reconstruction for the Smith-Waterman algorithm

Abstract

This paper presents the hardware implementation of a differential coded Smith-Waterman algorithm on a field programmable gate array (FPGA). A novel path reconstruction algorithm is proposed to overcome the need of a dedicated memory for the storage of the similarity matrix, thus limiting the on-chip hardware utilization. In addition, this algorithm is also efficient in terms of computational speed since the path reconstruction is carried out during the computation of the similarity score, rather then afterwards, as in the case of the original algorithm. The implementation was done on the Xilinx Spartan-6 XC6LX16-CS324 FPGA using VHDL, consisting of 1,024 processing elements and exhibits a throughput of 204.8 BCUPS at a data rate of 600 Mbps.