Abstract

We present a novel implementation of the pairwise DNA sequence alignment problem other than the Dynamic programming solution presented by Smith Waterman Algorithm. The proposed implementation uses CUDA; the parallel computing platform and programming model invented by NVIDIA. The main idea of the proposed implementation is assigning different nucleotide weights then merging the sub-sequences of match using the GPU Architecture according to predefined rules to get the optimum local alignment. We parallelize the whole solution for the pairwise DNA sequence alignment using CUDA and compare the results against a similar semi-parallelized solution and a traditional Smith-Waterman implementation on traditional processors; Experimental results demonstrate a considerable reduction in the running time.

References

• Michael Schatz, Cole Trapnell, Arthur Delcher, Amitabh Varshney, 2007. High-throughput sequence alignment using Graphics Processing Units, BMC Bioinformatics, Vol. 8, No. 1.
• J. Setubal and J. Meidanis, 1997. Introduction to Computational Molecular Biology, PWS Publishing Company.
• Terence Hwa and Michael Lässig, 1995. Similarity Detection and Localization, Physical Review Letters Volume: 76, Issue: 2.
• Jun Sung Yoon and Won-Hyong Chung, 2011. A GPU-accelerated bioinformatics application for large-scale protein interaction networks, Asia Pacific Bioinformatics Conference.
• Rafia Inam, 2011. An Introduction to GPGPU Programming - CUDA Architecture, Mälardalen University, Mälardalen Real-Time Research Centre.
• NVIDIA CORPORATION, CUDA Programming Guide, http://developer. nvidia. com/category/zone/cuda-zone
• Svetlin A Manavski and Giorgio Valle1, "CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment," BMC Bioinformatics 2008.
• Pearson, W. R. 1991. Searching protein sequence libraries: comparison of the sensitivity and selectivity of the Smith and Waterman and FASTA algorithms, Genomics 11, 635–650.
• Altschul, S. F. , Gish, W. , Miller, W. , Myers, E. W. , Lipman, D. J. , 1990. Basic local alignment search tool," J. Mol. Biol. 215, 403–410.
• S. Needleman and C. Wunsch, 1970 . A general method applicable to the search for similarities in the amino acid sequence of two proteins, J. Mol. Bio. , (48):443–453.
• T. Smith and M. Waterman, 1981. Identification of common molecular subsequences, J. Mol. Bio. , (147):195–197.
• W. Liu, B. Schmidt, G. Voss, A. Schroder and W. Muller-Wittig, 2006. Bio-Sequence Database Scanning on GPU, In proceeding of 20th IEEE International parallel & distributed processing symposium, HICOMB workshop Rhode Island, Greece.
• Cheng Ling, Khaled Benkrid and Tsuyoshi Hamada, 2009. A Parameterisable and Scalable Smith-Waterman Algorithm Implementation on CUDA-compatible GPUs IEEE 7th Symposium on Application Specific Processors (SASP).
• Bo Chen, Yun Xu, Jiaoyun Yang, and Haitao Jiang, 2010. A New Parallel Method of Smith-Waterman Algorithm on a Heterogeneous Platform, Lecture Notes in Computer Science Volume 6081, pp 79-90, Springer-Verlag Berlin Heidelberg.
• Heba Khaled , Hossam M Faheem , Tayseer Hasan , Saeed Ghoneimy,"Design of a Hybrid System for DNA Sequence Alignment, Proceedings of The International MultiConference of Engineers and Computer Scientists 2008 , pp162-167.
• H. Khaled, R. El Gohary, N. L. Badr and H. M. Faheem, 2013. Hybrid Framework for pairwise DNA Sequence Alignment Using the CUDA compatible GPU, Proceeding of the BIOCOMP'13.