Systolic Array Residue Number System Based Smith-Waterman Algorithm

Smith-waterman algorithm (SWA) is widely used in computational biology. It is regarded as the most accurate sequence alignment algorithm on state-of-the-art (SOA). However, the algorithm is devoid of highspeed in term of performance. Evidence showed that various platforms have been used to implement the algorithm in order to improve the poor speed of operation, such as systolic array (SA) implemented on Field Programmable Gate Array (FPGA), acceleration on CPU-GPU architecture, acceleration based on residue number system (RNS) and so on. Evidence on SOA also showed that implementation of the algorithm on FPGA platform recorded a better result than any other platform. In this paper, Systolic array is proposed on SWA taking advantages of inherent and unique properties of RNS and implemented on FPGA (Spartan-III, 64-Bit version (Xilinx family)). The metrics used for evaluation was processing time. The results were finally compared with existing SOA systems. The SA method vs RNS based implementation on FPGA gave a credible result with 372.4 Giga Cell Update Per Second (GCUPS) with 875 PE.