The week's pick
Reseach Article
Fast Dynamic Algorithm for Sequence Alignment Based On Bioinformatics
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 37 - Number 7 |
| Year of Publication: 2012 |
| Authors: Sara A.Shehab, Arabi Keshk, Hany Mahgoub |
10.5120/4624-6636
|
Sara A.Shehab, Arabi Keshk, Hany Mahgoub . Fast Dynamic Algorithm for Sequence Alignment Based On Bioinformatics. International Journal of Computer Applications. 37, 7 ( January 2012), 54-61. DOI=10.5120/4624-6636
Abstract
Sequence alignment is widely used in Bioinformatics for Genome Sequence difference identification. It is the main problem of computational biology. Any sequence of Deoxyribonucleic acid (DNA), Ribonucleic acid (RNA), and protein can be alignment by many algorithms called bioinformatics algorithms. This paper presents a new implemented algorithm for sequence alignment based on concepts from bioinformatics algorithms .The implemented algorithm is called fast dynamic algorithm for sequence alignment (FDASA). This implemented algorithm based on making a matrix of M×N (M is the length of the first sequence, N is the length of the second sequence), After that filling the three main diagonal without filling the unused data and at the same time get the optimal solution; so that the execution time is decreased, the performance is high and the memory location decreased. The implementation introduced in this paper made a comparison between the dynamic algorithms Needleman-Wunsch algorithm, Smith-Waterman and our algorithm FDASA to test the execution time. The results show that our algorithm FDASA decreased the execution time when compared with Needleman-Wunsch and Smith-Waterman algorithms.
References
- Dimitris Papamichail and Georgios Papamichail2,”Improved algorithms for approximate string matching (extended abstract)”,BMC Bioinformatics 2009
- Tahir Naveed, Imitaz Saeed Siddiqui, Shaftab Ahmed,”Parallel Needleman-Wunsch Algorithm for Grid”, Proceedings of the PAK-US International Symposium on High Capacity Optical Networks and Enabling Technologies (HONET 2005), Islamabad, Pakistan, Dec 19 - 21, 2005.
- The Science Behind the Human Genome Project (online), Oak RidgeNationalLaboratory.Available: http://www.ornl.gov/sci/techresources/Human_Genome/project/info.shtml
- Facts About Genome Sequencing (online), Oak Ridge National Laboratory.Available: http://www.ornl.gov/sci/techresources/Human_Genome/faq/seqfacts.shtml
- Source of DNA Sequences (online), National Center for BiotechnologyInformation.Available: http://www.ncbi.nlm.nih.gov/mapview
- Pairwise Sequence Comparison (online), Lab of Bioinformatics,Institute of Computing Technology (ICT), Chinese Academia of Sciences(CAS). Available: http://www.bioinfo.org.cn/lectures/index-13.html
- Introduction to Bioinformatics - Chapter 5 - Introductory SequenceAnalysis (online), Human Genome Mapping ProjectResource Centre(HGMP-RC) by UK Medical Research Council. Available:http://portal.rfcgr.mrc.ac.uk/Courses/Jemboss_3day/Chapter5.html#Global%20sequence%20alignment
- Krishna N. and Akshay L. and Dr. Rajkumar B., 2002, Alchemi v0.6.1 Documentation (online), University of Melbourne. Available: http://alchemi.net/
- BioInformatics Educational Resources Documentation (online), European Bioinformatics Institute United Kingdom. Available: http://www.ebi.ac.uk/2can/tutorials/protein/align.html
- ChittaBaral, Computational Molecular Biology, CSE 591 Arizona State University, United States of America. Available:http://www.public.asu.edu/~cbaral/cse591-03/classnotes/seq-align.pdf
- Rong X, Jan 2003, Pairwise Alignment - CS262 - Lecture 1 Notes(online), Stanford University. Available: http://ai.stanford.edu/~serafim/cs262/Spring2003/Notes/1.pdf
- Bin Wang, 2002, Implementation of a dynamic programmingalgorithm for DNA Sequence alignment on the Cell Matrix Architecture ( online), Utah State University, Logan, Utah. Available:http://www.cellmatrix.com/entryway/products/pub/wang2002.pdf
- Chand T. John, April 2004, CS273: Algorithms for Structure andMotion in Biology, Stanford University. Available:http://www.stanford.edu/class/cs273/scribing/8.pdf
- SérgioAnibal de Carvalho Junior ,”Sequence Alignment Algorithms”, thesis, 2002/2003.
- About the Human Genome Project (online), Oak Ridge NationalLaboratory.Available: http://www.ornl.gov/sci/techresources/Human_Genome/project/about.shtml
- Needleman S, Wunsch.,”A general method applicable to the search for similarities in the amino acid sequences of two proteins”, J Mol Biol. 1970, 48:443-453.
- FASTA Format Description (online), NGFN-BLAST. Available:http://ngfnblast.gbf.de/docs/fasta.html
- Smith, T. F. and M. S. Waterman, Identification of common molecular subsequences,Journal of Molecula Biology, 147:195-197, 1981.
Index Terms
Keywords