Residue Number System Based Optimization of Smith-waterman Algorithm

Abstract

One of the greatest global challenges in bioinformatics is the computational time and memory utilization in biological sequence alignment (BSA). Several studies on the computation of BSA showed that the run time and its corresponding memory are on the high side. A number of algorithms that have been attempted to optimize BSA speed include fast alignment search tool algorithm (FASTA), basic local alignment search tool (BLAST), Needleman-Wunsch and Smithwaterman algorithm (SWA). Evidence has also shown that SWA is the most widely used BSA algorithm due to its accuracy which is, however, found to be relatively slower. Recently, there is a rapid exponential growth in International biological database size which necessitates the urgent optimization of SWA. In this work, the attributes of Residue Number System (RNS) such as carry free addition, borrow free subtraction, digit by digit multiplication without partial product and parallel computation are leveraged to enhance the performance of SWA. The implementation was carried out on MATLAB 2016 version RA (9.0.341360). The metrics used for evaluation are processing time and memory utilization. The results were finally compared with SWA computation. The computational time of SWA and SWA-RNS based are 23.34 and 7.53 respectively, while the memory space utilized respectively are 12.86 and 2.53. The results demonstrate the great computing power of RNS in the operation of SWA with an improvement of 51.21% and 67.12% in speed and storage requirement respectively.