A Two-Phase Dynamic Programming Algorithm Tool for DNA Sequences

Oyelade Jelili, Fatumo Segun

Abstract


Sequence alignment has to do with the arrangement of DNA, RNA, and protein sequences to identify areas of similarity. Technically, it involves the arrangement of the primary sequences of DNA, RNA, or protein to identify regions of similarity that may be a consequence of functional, structural, or evolutionary relationships between the sequences. Similarity may be a consequence of functional, structural, or evolutionary relationships between the sequences. If two sequences in an alignment share a common ancestor, mismatches can be interpreted as mutations, and gaps as insertions. Such information becomes of great use in vital areas such as the study of diseases, genomics and generally in the biological sciences. Thus, sequence alignment presents not just an exciting field of study, but a field of great importance to mankind. In this light, we extensively studied about seventy (70) existing sequence alignment tools available to us. Most of these tools are not user friendly and cannot be used by biologists. The few tools that attempted both Local and Global algorithms are not ready available freely. We therefore implemented a sequence alignment tool (CU-Aligner) in an understandable, user-friendly and portable way, with click-of-a-button simplicity. This is done utilizing the Needleman-Wunsh and Smith-Waterman algorithms for global and local alignments, respectively which focuses primarily on DNA sequences. Our aligner is implemented in the Java language in both application and applet mode and has been efficient on all windows operating systems.
Keywords— sequence, global alignment, local alignment, dynamic programming and java applet.

Full Text:

PDF

References


Flaninick J, Batzoglou S. Using multiple alignments to

improve seeded local alignment algorithms. Nicleic

Acids Research, 33(14), pp. 4563-4577, 2005.

. K. Somasundaram and S. Radhakrishnan: “Nimble

Protein Sequence Alignment in Grid (NPSAG)”, Journal

of Computer Science 4 (1), pp. 36-41, 2008.

Schwartz, S., Zhang, Z., Frazer, K.A., Smit, A., Riemer, C.,

Bouck, J., Gibbs, R., Hardison, R.C., and Miller, W., “A

Web server for aligning two genomic DNA

sequences”. Genome Res. 10, pp. 577-586, 2000.

Junier, T. and Bucher, P., “A Java applet for browsing

molecular sequence data”. In Silico Biol. 1, pp. 13-20,

T. Junier, M. Pagni and P. Bucher, mmsearch, “A motif

arrangement language and the Eukaryotic Promoter

Database (EPD)”. Nucleic Acids Res, 26, 353-357, 1998.

P. Peterlongo, N. Pisanti, F. Boyer, A. P. do Lago, and M.-

F. Sagot, “Lossless filter for multiple repetitions with

Hamming distance”. Journal of Discrete Algorithms, 19,

pp. 71-87, 2008.

Smith T.F, Waterman M.S, “Identification of Common

Molecular Subsequences”. Journal of Molecular

Biology, 147, pp. 195–197, 1981.

Needleman SB, Wunsch CD, “A general method

applicable to the search for similarities in the amino

acid sequence of two proteins”. Journal of Molecular

Biology 48 (3), 443-53, 1970.

Brudno M, Malde S, Poliakov A, Do CB, Couronne O,

Dubchak I, Batzoglou S. "Glocal alignment: finding

rearrangements during alignment". Bioinformatics 19

Suppl 1: i54–6,(2003.

Schwartz S, Kent WJ, Smit A, Zhang Z, Baertsch R,

Hardison RC, Haussler D, Miller W. Human-mouse

alignments with BLASTZ. Genome Res. 2003;13:103–

Lassmann T, Sonnhammer EL. Quality assessment of

multiple alignment programs. FEBS Lett.

;529:126–130.doi:10.1016/S0014-5793(02)03189

Katoh K, Misawa K, Kuma K, Miyata T. MAFFT: a novel

method for rapid multiple sequence alignment based

on fast Fourier transform. Nucleic Acids Res.

;30:3059–3066

Rice P, Longden I, Bleasby A. EMBOSS: the European

Molecular Biology Open Software Suite. Trends Genet.

;16:276–27

Bray N, Dubchak I, Pachter L. AVID: A Global Alignment

Program. Genome Res. 2003;13:97–102

Brudno M, Do CB, Cooper GM, Kim MF, Davydov E,

Program NC, Green ED, Sidow A, Batzoglou S. LAGAN

and Multi-LAGAN: Efficient Tools for Large-Scale

Multiple Alignment of Genomic DNA. Genome Res


Refbacks

  • There are currently no refbacks.