Refine your search
Collections
Co-Authors
Year
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z All
Boateng, Kwame O.
- A Smith-Waterman Algorithm Accelerator Based on Residue Number System
Abstract Views :289 |
PDF Views:0
Authors
Affiliations
1 Kwame Nkrumah University of Science and Technology, Kumasi,, GH
2 University of Development Studies, Navrongo,, GH
1 Kwame Nkrumah University of Science and Technology, Kumasi,, GH
2 University of Development Studies, Navrongo,, GH
Source
International Journal of Electronics and Communication Engineering, Vol 5, No 1 (2012), Pagination: 99-112Abstract
One of the biggest challenges confronting the bioinformatics community 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, SWA is not used in real life applications due to the computational cost associated with the software implementation. Heuristics methods such as BLAST and FASTA are used, though they do not guarantee accurate sequence alignments. In this paper, we proposed a novel accelerator for addressing the challenge using Residue Number System (RNS). RNS is an integer system with properties that support parallel computation, carry-free addition, borrow-free subtraction, and singlestep multiplication (without partial product). Based on some of these properties, the design of a hardware accelerator for SWA is presented on the assumption that two long strings of DNA can be compared in a divide-andconquer manner. Simulation of a sample design indicates modest hardware consumption and much improved overall speed of the SWA.
References
- Soderstrand, M. A., Jenkins, W. K., Jullien, G.A., and Taylor, F. J., 1986, Residue Number System Arithmetic: Modern Applications in Digital Signal Processing, New York: IEEE Press.
- Conway, R., and Nelson, J., 2004, “Improved RNS FIR Filter Architectures. IEEE Trans. on Circuits and System – II,” Express briefs, Vol. 51, No. 1, pp. 26 – 28.
- Jenkins, W.K., and Leon, B. J., 1977, ”The use of Residue Number Systems in the design of finite Impulse Response Digital Filters, IEEE Trans. on Circuit and Systems, vol. 24: pp 191 – 200.
- Fernandez, P. G., Garcia, A., Ramirez, J., and, Lloris, A., 2000, “Fast RNS – based 2D – DCT computation on Field _ Programmable devices,” Proceedings of IEEE Signal Processing Systems Workshop, pp. 365 – 373, LA, USA.
- Fernandez, P. G., Garcia, A., Ramirez, J., and, Lloris, A., 2000, “A RNS – based Matrix – vector – multiply FCT Architecture for DCT computation,” Proceedings of 43rd IEEE Midwest symposium on Circuits and Systems, pp. 350 – 353, Lansing, MI.
- Diauro, G., Impedovo, S., and Pirlos, G., 1993, “A new technique for fast comparison in Residue Number System,” IEEE Trans., on Computers, Vol. 42, No. 5, pp. 608 – 612.
- Parhami, B., 2000, Computer Arithmetic and Hardware designs, New York, Oxford University press.
- Baraiecka, A. Z., and Jullien, G. A., 1980, “Residue Number System Implementation of number theoretic transform in complex residue rings,”. IEEE Trans. Acoustics, Speech, Signal Processing, Vol. ASSP – 28, pp. 285 – 291.
- Taylor, F.J., 1984, “Residue Arithmetic: A Tutorial with examples,” IEEE comp. magazine, vol. 17, No. 5, pp. 50 – 62.
- Bi, S., and Gross, W. J., 2008, “The Mixed – Radix Chinese Remainder Theorem and its applications to residue comparison,” IEEE Trans. on computers, Vol. 57, No. 12, pp. 1624 – 1632.
- Al – radadi, E., and Siy, P., 2001, “A new technique for fast number comparison in the residue number system based on Chinese Remainder Theorem II,” Proceedings of the MUG 18th International Conference, Denver.
- Tenkins, W. J., 1978, “Techniques for residue – to – analog conversion for residue – encoded digital filters,” IEEE Trans. on Circuits and Syst. Vol. CAS – 25, pp. 555 – 562.
- Jullien, G. A., 1978, “Residue Number Scaling and other operation using ROM arrays,” IEEE Trans. Computers, Vol. C. 27, pp. 325 – 336, April, 1978.
- Huang, C. H., and Taylor, F. J., 1980, “High speed DFTs using Residue Numbers,” In Proceedings IEEE 1980 conference Acoust., speech, signal processing, Denver, Co, pp. 238 – 241.
- Taylor, F. J., 1990, “An RNS Discrete Fourier Transform Implementation,” IEEE Trans. Acoust. Speech, Signal Process, Vol. 38, No. 8. Pp. 1386 – 1394.
- Madhukumar, A. S., and Chin, F., 2002, “Performance of a Residue Number system based CDMA system over wireless personal communication”, Springer. Netherlands, Vol. 22, No. 1, pp. 89 – 102.
- Madhukumar, A. S., Chin, F., and Premkumar, A. B., 2000, “Residue Number System based multicarrier CDMA for broadband mobile communication systems,” Proceedings of 43rd IEEE Midwest symposium on circuits and systems. pp. 536 – 539, Lansing, MI.
- Merill, R.D., 1964, “Improving digital Computer performance using Residue Number Theory. Trans. on Electronic Computers”. Vol. 13, Issues 2, pp. 93 – 101.
- Taylor, F. J., and Huang, C. H., 1982, “A comparison of DFT algorithms using a Residue Arithmetic Architecture. International Journal of Computer and Electronic Engineering.
- Smith, T.F., and Waterman, M. S., 1981, “Identification of common molecular subsequences,” In journal of molecular biology, vol. 147, pp 195 – 197.
- Miki, Y., et al., 1994, “A Strong Candidate for the Breast Cancer and Ovarian Cancer Susceptibility Gene, BRCA1,” Science, 266:6-71.
- Altschul, S. F., et al., 1990, “A Basic Local Alignment Search Tools,” In Journal of Molecular Biology, vol 215, pp. 403 – 410.
- Pearson, W. R., and Lipman, D.J., 1985, “Rapid and Sensitive Protein Similarity Searches,” In Science, vol 227, pp 1435 – 1441.
- Hasan, L, et al, September 2 – 5, 2007, “Hardware Acceleration of sequence alignment algorithms – an overview,” Proceedings of International conference on Design and Technology of Integrated Systems in Nano cell Era (DTIS’07), pp 96 – 101, Rabat, Morocco.
- Hasan, L., and Al-Ars, Z., November 29 – 30, 2007, “Performance Improvement of the Smith–Waterman algorithm,” Annual workshop on circuits, systems and signal processing (ProRISC). Veldhoven, The Netherlands.
- Yu, C. W., Kwong, K. H., Lee, K. H., and Leong, P. H. W., 2003, “A Smith- Waterman systolic cell,” In Proceedings of the 13th International Workshop on Field Programmable Logic and Applications.