FPGA BASED DESIGN OF SMITH-WATERMAN ALGORITHM

Pairwise sequence alignment is often used to reveal similarities between sequences, locate patterns of conservation, study gene regulation, and infer evolutionary relationships [1]. Although the Smith-Waterman (SW) algorithm is the only optimal local sequence alignment algorithm, it is also the slowest one as it costs 0(mn) for computation space. Also the volume of biological data is doubling about every six months so the total cost is 0(kmn) where k is the size of the database [2, 3]. By using High Performance Computing (HPC) accurate results can be achieved in reasonable time. In this paper we present a design of FPGA based linear systolic array for smith-waterman algorithm which calculates the highest alignment score during calculation of the similarity matrix cells which repeals the requirement of storing the whole matrix to traverse it to find the optimal alignment score. Our FPGA based design of smith-waterman algorithm shows speedup of up to 200x as compared to a C++ implementation on general purpose processor (GPP)