CFP last date
20 June 2024
Reseach Article

Shared Memory and Hardware Utilizations for the Parallelization of Local Sequences Alignment using SW Algorithm: A Review

by Manhal Elfadil Eltayeeb, Muhammad S. Abd Latiff, Ismail Fuzi Isnin
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 115 - Number 4
Year of Publication: 2015
Authors: Manhal Elfadil Eltayeeb, Muhammad S. Abd Latiff, Ismail Fuzi Isnin

Manhal Elfadil Eltayeeb, Muhammad S. Abd Latiff, Ismail Fuzi Isnin . Shared Memory and Hardware Utilizations for the Parallelization of Local Sequences Alignment using SW Algorithm: A Review. International Journal of Computer Applications. 115, 4 ( April 2015), 28-34. DOI=10.5120/20141-2257

@article{ 10.5120/20141-2257,
author = { Manhal Elfadil Eltayeeb, Muhammad S. Abd Latiff, Ismail Fuzi Isnin },
title = { Shared Memory and Hardware Utilizations for the Parallelization of Local Sequences Alignment using SW Algorithm: A Review },
journal = { International Journal of Computer Applications },
issue_date = { April 2015 },
volume = { 115 },
number = { 4 },
month = { April },
year = { 2015 },
issn = { 0975-8887 },
pages = { 28-34 },
numpages = {9},
url = { },
doi = { 10.5120/20141-2257 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
%0 Journal Article
%1 2024-02-06T22:53:52.403054+05:30
%A Manhal Elfadil Eltayeeb
%A Muhammad S. Abd Latiff
%A Ismail Fuzi Isnin
%T Shared Memory and Hardware Utilizations for the Parallelization of Local Sequences Alignment using SW Algorithm: A Review
%J International Journal of Computer Applications
%@ 0975-8887
%V 115
%N 4
%P 28-34
%D 2015
%I Foundation of Computer Science (FCS), NY, USA

It is becoming increasingly difficult to ignore the importance of aligning DNA and Protein sequences to infer properties of new sequences from well-known reference sequences established and sorted in genetics databanks. Many studies in recent years have focused on different implementations of Sequences Alignment Problems (SAP). However, researcher confused with the ambiguous classification of the SAP. This paper is set out mainly to review, investigate, and analysis current trends in shared memory and hardware implementation of local SAP using Smith-Waterman algorithm. The literatures are addressing and evaluating in order to highlight their advantages and disadvantages.

  1. K. Raman, "Construction and analysis of protein-protein interaction networks," Autom Exp, vol. 2, p. 2, 2010.
  2. D. Darriba, G. L. Taboada, R. Doallo, and D. Posada, "ProtTest 3: fast selection of best-fit models of protein evolution," Bioinformatics, vol. 27, p. 1164, 2011.
  3. A. L. Beberg, D. L. Ensign, G. Jayachandran, S. Khaliq, and V. S. Pande, "Folding@home: Lessons From Eight Years of Volunteer Distributed Computing," 2009 Ieee International Symposium on Parallel & Distributed Processing, Vols 1-5, pp. 1624-1631, 2009.
  4. M. Axelson-Fisk, "Sequence Alignment," in Comparative Gene Finding, ed: Springer London, 2010, pp. 89-155.
  5. M. Imelfort, "Sequence comparison tools," Bioinformatics. , pp. 13-37, 2009.
  6. S. Brenner, "Optimal Pairwise Alignment," in Introduction to computational biology: an evolutionary approach, B. Haubold and T. Wiehe, Eds. , ed: Springer, 2006, pp. 11-42.
  7. D. Díaz, F. J. Esteban, P. Hernández, J. A. Caballero, G. Dorado, and S. Gálvez, "Parallelizing and optimizing a bioinformatics pairwise sequence alignment algorithm for many-core architecture," Parallel Computing, vol. 37, pp. 244-259, 2011.
  8. T. Smith and M. Waterman, "Identification of common molecular subsequences," J. Mol. Bwl, vol. 147, pp. 195-197, 1981.
  9. S. B. Needleman and C. D. Wunsch, "A general method applicable to the search for similarities in the amino acid sequence of two proteins," Journal of molecular biology, vol. 48, pp. 443-453, 1970.
  10. S. Henikoff and J. G. Henikoff, "Amino acid substitution matrices from protein blocks," Proc Natl Acad Sci U S A, vol. 89, pp. 10915-9, Nov 15 1992.
  11. R. B. Batista, A. Boukerche, and A. C. M. A. de Melo, "A parallel strategy for biological sequence alignment in restricted memory space," Journal of Parallel and Distributed Computing, vol. 68, pp. 548-561, 2008.
  12. G. M. Amdahl, "Validity of the single processor approach to achieving large scale computing capabilities," in Proceedings of the April 18-20, 1967, spring joint computer conference, 1967, pp. 483-485.
  13. J. T. Dudley and A. J. Butte, "A quick guide for developing effective bioinformatics programming skills," PLoS Comput Biol, vol. 5, p. e1000589, Dec 2009.
  14. S. Hosangadi and S. Kak, "An Alignment Algorithm for Sequences," arXiv preprint arXiv:1210. 8398, 2012.
  15. T. Rauber and G. Rünger, Parallel programming: For multicore and cluster systems: Springer Science & Business, 2013.
  16. S. Bandyopadhyay and R. Mitra, "A parallel pairwise local sequence alignment algorithm," NanoBioscience, IEEE Transactions on, vol. 8, pp. 139-146, 2009.
  17. G. Delgado and C. Aporntewan, "Data dependency reduction in Dynamic Programming matrix," in Computer Science and Software Engineering (JCSSE), 2011 Eighth International Joint Conference on, 2011, pp. 234-236.
  18. N. Sebastião, G. Encarnação, and N. Roma, "Implementation and performance analysis of efficient index structures for DNA search algorithms in parallel?platforms," Concurrency and Computation: Practice and Experience, pp. n/a-n/a, 2012.
  19. P. Borovska, V. Gancheva, G. Dimitrov, and K. Chintov, "Parallel performance evaluation of multithreaded local sequence alignment," in Proceedings of the 12th International Conference on Computer Systems and Technologies, 2011, pp. 247-252.
  20. T. Rognes, "Faster Smith-Waterman database searches with inter-sequence SIMD parallelisation," BMC bioinformatics, vol. 12, p. 221, 2011.
  21. G. Ivan, D. Banky, and V. Grolmusz, "Fast and Exact Sequence Alignment with the Smith-Waterman Algorithm: The SwissAlign Webserver," arXiv preprint arXiv:1309. 1895, 2013.
  22. F. M. Mendonca and A. C. M. A. d. Melo, "Biological Sequence Comparison on Hybrid Platforms with Dynamic Workload Adjustment," in Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2013 IEEE 27th International, 2013, pp. 501-509.
  23. N. Neves, N. Sebastiao, A. Patricio, D. Matos, P. Tomás, P. Flores, et al. , "BioBlaze: Multi-core SIMD ASIP for DNA sequence alignment," in Application-Specific Systems, Architectures and Processors (ASAP), 2013 IEEE 24th International Conference on, 2013, pp. 241-244.
  24. D. Satyanvesh, K. Balleda, A. Padyana, and P. Baruah, "GenCodex-A Novel Algorithm for Compressing DNA sequences on Multi-cores and GPUs," in 19th IEEE International conference on High Performance Computing. , December 2012. , 2012.
  25. D. Satyanvesh, K. Balleda, and P. Baruah, "Genalign—A high performance implementation for aligning the compressed DNA sequences," in Advanced Computing Technologies (ICACT), 2013 15th International Conference on, 2013, pp. 1-6.
  26. N. Alachiotis, S. Berger, T. Flouri, S. P. Pissis, and A. Stamatakis, "libgapmis: extending short-read alignments," BMC Bioinformatics, vol. 14, p. S4, 2013.
  27. H. Martínez, J. Tárraga, I. Medina, S. Barrachina, M. Castillo, J. Dopazo, et al. , "Concurrent and Accurate RNA Sequencing on Multicore Platforms," arXiv preprint arXiv:1304. 0681, 2013.
  28. M. Noorian, H. Pooshfam, Z. Noorian, and R. Abdullah, "Performance enhancement of smith-waterman algorithm using hybrid model: comparing the MPI and hybrid programming paradigm on SMP clusters," in Systems, Man and Cybernetics, 2009. SMC 2009. IEEE International Conference on, 2009, pp. 492-497.
  29. M. J. Chorley and D. W. Walker, "Performance analysis of a hybrid MPI/OpenMP application on multi-core clusters," Journal of Computational Science, vol. 1, pp. 168-174, Aug 2010.
  30. M. Farrar, "Striped Smith–Waterman speeds database searches six times over other SIMD implementations," Bioinformatics, vol. 23, pp. 156-161, 2007.
  31. H. Q. Jin, D. Jespersen, P. Mehrotra, R. Biswas, L. Huang, and B. Chapman, "High performance computing using MPI and OpenMP on multi-core parallel systems," Parallel Computing, vol. 37, pp. 562-575, Sep 2011.
  32. G. Hager, G. Jost, and R. Rabenseifner, "Communication characteristics and hybrid MPI/OpenMP parallel programming on clusters of multi-core SMP nodes," in Proceedings of Cray User Group Conference, 2009, p. 5455.
  33. K. R. Luecke, "Software Development for Parallel and Multi-Core Processing," in Embedded Systems - High Performance Systems, Applications and Projects, ed: InTech. , 2012, pp. 35-58.
  34. S. Aluru and N. Jammula, "A Review of Hardware Acceleration for Computational Genomics," 2013.
  35. P. K. Lala, "A Digital Hardware-based Approach for Molecular Sequence Comparison," in Information Engineering, 2013.
  36. T. Majumder, P. P. Pande, and A. Kalyanaraman, "Hardware Accelerators in Computational Biology: Application, Potential and Challenges," 2013.
  37. B. Vibishna, K. S. Beenamole, and A. K. Singh, "Understanding single-event effects in FPGA for Avionic system design," Iete Technical Review, vol. 30, pp. 497-505, Nov-Dec 2013.
  38. A. Surendar, M. Arun, and C. Bagavathi, "EVOLUTION OF RECONFIGURABLE BASED ALGORITHMS FOR BIOINFORMATICS APPLICATIONS: AN INVESTIGATION," International journal of life sciences, Biotechnology and Pharma Research, vol. 2, 2013.
  39. X. Meng and V. Chaudhary, "Boosting data throughput for sequence database similarity searches on FPGAs using an adaptive buffering scheme," Parallel Computing, vol. 35, pp. 1-11, Jan 2009.
  40. J. Allred, J. Coyne, W. Lynch, V. Natoli, J. Grecco, and J. Morrissette, "Smith-Waterman implementation on a FSB-FPGA module using the Intel Accelerator Abstraction Layer," in Parallel & Distributed Processing, 2009. IPDPS 2009. IEEE International Symposium on, 2009, pp. 1-4.
  41. C. YILMAZ and M. GÖK, "System designs to perform bioinformatics sequence alignment," Turkish Journal of Electrical Engineering & Computer Sciences, vol. 21, pp. 246-262, 2013.
  42. Y. Zhang, S. Misra, D. Honbo, A. Agrawal, W. Liao, and A. Choudhary, "Efficient pairwise statistical significance estimation for local sequence alignment using GPU," in Computational Advances in Bio and Medical Sciences (ICCABS), 2011 IEEE 1st International Conference on, 2011, pp. 226-231.
  43. P. Borovska and M. Lazarova, "Parallel models for sequence alignment on CPU and GPU," in Proceedings of the 12th International Conference on Computer Systems and Technologies, 2011, pp. 210-215.
  44. A. Papadopoulos, I. Kirmitzoglou, V. J. Promponas, and T. Theocharides, "GPU technology as a platform for accelerating local complexity analysis of protein sequences," in Engineering in Medicine and Biology Society (EMBC), 2013 35th Annual International Conference of the IEEE, 2013, pp. 2684-2687.
  45. S. Manavski and G. Valle, "CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment," BMC bioinformatics, vol. 9, p. S10, 2008.
  46. X. Feng, H. Jin, R. Zheng, L. Zhu, and W. Dai, "Accelerating Smith-Waterman Alignment of Species-Based Protein Sequences on GPU," International Journal of Parallel Programming, pp. 1-22, 2013.
  47. S. Sarkar, G. R. Kulkarni, P. P. Pande, and A. Kalyanaraman, "Network-on-chip hardware accelerators for biological sequence alignment," Computers, IEEE Transactions on, vol. 59, pp. 29-41, 2010.
  48. S. Kaur, "On-chip Networks!," Iete Technical Review, vol. 30, pp. 168-172, May-Jun 2013.
Index Terms

Computer Science
Information Sciences


DNA Protein Sequences Alignment Shared Memory Smith-Waterman Parallel Computing.