Application of Residue Number System to Smith - Waterman Algorithm

Thumbnail Image
MAY, 2011
Journal Title
Journal ISSN
Volume Title
In this thesis, we propose a hardware implementation of the Smith - Waterman Algorithm using Residue Number System (RNS). One of the biggest challenges confronting the bioinformatics community as at now is fast and accurate sequence alignment. The Smith - Waterman algorithm (SWA) is one of the several algorithms used in addressing some of these challenges. Though very sensitive in doing sequence alignment, the SWA is not used in real life applications due to the computational cost involve in using this algorithm. Hence heuristics methods such as BLAST and FASTA are used though they do not guarantee accurate sequence alignments. We seek to address the computational challenge associated with the SWA by using the inherent arithmetic advantages of RNS. The RNS is such an integer system exhibiting the capabilities that support parallel computation, carry free addition, borrow-free subtraction, and single step multiplication without partial product. Base on some of these properties, a hardware implementation of the SWA is done in VHDL, a hardware description Language. In order to be able to use moduli set with a small dynamic range, matrix partitioning has been used on the fact that the comparison of two long strings of DNA can be done in a divide - and - conquer approach. A sample 4 - bit system implementation improves the overall speed of the SWA. The implementation was on FPGA device EP2S15F484C3, a Stratix II family, and it consumes 189 logic cells. The worst - case clock - to - output delay (tco) between the specified source and destination points is 6.006 ns. These outstanding results when compared with what is in literature shows that the implementation is both area and speed efficient and thereby improve the speed constraints of the SWA. When compared with the work of L. Hasan and Z. Al-lrs (2007) this implementation has improves the computational time 243%, when calcualted in terms of percentage ratio, thereby making this implementation better than the state of the art hardware implementation of the SWA. In terms of comparison with the hardware implementation done by [1], our hardware implementation is superior by 143%. Also, comparing our hardware implementation result with it’s software equivalent shows a tremendous improvement of 871029%, that is 8710.29 times faster. What these outstanding results mean is that there is hope for the bioinformatics community so far as accurate sequence alignment is concern. The total time that will be needed to alignment two strings of DNA using the RNS - SWA architecture will be improved by 8710.29 times more than it’s software equivalent implementation. These results also support the fact that RNS is a good platform to implement the SWA, since it has a high prospect of improving the overall computational cost and the hardware foot print of the algorithm.
A Thesis Submitted to the Department of Computer Engineering, Kwame Nkrumah University of Science and Technology in Partial Fulfillment of the Requirements for the Degree of MASTER OF PHILOSOPHY in COMPUTER ENGINEERING.