Improvisation of Global Pairwise Sequence Alignment Algorithm Using Dynamic Programming

Authors(3) :-Jyoti Lakhani, Ajay Khunteta, Dharmesh Harwani

The global pairwise sequence alignment algorithms based on dynamic programming match each base pair step by step in the sequence under observation from start to end. This approach increases the time complexity which increases further many folds when large sequences are used. Needleman-Wunsch, Smith-Waterman, ALIGN, FASTA, BLAST and many other pair-wise sequence alignment algorithms are based on dynamic programming approach. The present communication is an attempt to provide a method for improvisation in dynamic programming used for pair-wise sequence alignment. The proposed technique is based on look-ahead method which decides whether it is required to continue or stop the processing of alignment steps for the sequence pair under observation from the current point if significant match score is not achieved. A threshold to be set by a user a-priori, indicating minimum percent match per base error to be accepted in sequence alignment process. The present improvisation method of dynamic programming can reduce bulky computational steps and hence save a reasonable amount of time in pairwise sequence alignment process.

Authors and Affiliations

Jyoti Lakhani
Poornima University, Jaipur & Maharaja Ganga Singh University, Bikaner, Rajasthan, India
Ajay Khunteta
Poornima University, Jaipur, Rajasthan, India
Dharmesh Harwani
Maharaja Ganga Singh University, Bikaner, Rajasthan, India

Improvisation, Pairwise Sequence Alignment, Dynamic Programming, Time Complexity

  1. R. Durbin, S. Eddy, A. Krogh, and G. Mitchison. "Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids”, Cambridge: Cambridge University Press (1998). DOI:10.1017/CBO9780511790492
  2. A.J. Gibbs and G.A. McIntyre. "The diagram, a method for comparing sequences: Its use with amino acid and nuceotide sequences.” European Journal of Biochemistry (1970). 16, 1-11.
  3. B. Needleman, Saul & D. Wunsch, Christian. "A General Method Applicable to Search for Similarities in Amino Acid Sequence of 2 Proteins” Journal of molecular biology(1970) 48. 443-53. DOI: 10.1016/0022-2836(70)90057-4.
  4. W. R. Pearson and D. J. Lipman. "Improved tools for biological sequence comparison". Proceedings of the National Academy of Sciences of the United States of America(1988) 85 (8): 2444-2448. doi:10.1073/pnas.85.8.2444. PMC 280013. PMID 3162770
  5. W.R. Pearson. "Rapid and sensitive sequence comparison with Fastp and Fasta”. Methods Enzymol (1990), 183: 63-98.
  6. W.R. Pearson. "Effective protein sequence comparison”. Meth Enzymol. (1996) 266: 227-258.
  7. S.F. Altschul,  W. Gish,  W. Miller,  E.W. Myers, and  D. J. Lipman.(1990) J. Mol. Biol., vol. 215, pg. 403-410.
  8. S. F. Altschul, T.L.Madden, A. A. Schaffer, et al., "Gapped BLAST and PSI- BLAST: A new generation of protein database search programs”. (1997) Nucleic Acids Res., Vol. 25, pp. 3389-3402.
  9. T. F. Smith and M.S. Waterman. "Comparison of biosequences”. (1981a) Advances in Applied Mathematics Volume 2, Issue 4, December 1981, Pages 482-489. DOI: https://doi.org/10.1016/0196-8858(81)90046-4
  10. T. F. Smith and M.S.Waterman. "Identification of common molecular subsequences". (1981b)Journal of Molecular Biology, Volume 147, Issue 1, 25 March 1981, Pages 195-197. DOI: https://doi.org/10.1016/0022-2836(81)90087-5

Publication Details

Published in : Volume 2 | Issue 6 | November-December 2017
Date of Publication : 2017-12-31
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 909-914
Manuscript Number : CSEIT1726243
Publisher : Technoscience Academy

ISSN : 2456-3307

Cite This Article :

Jyoti Lakhani, Ajay Khunteta, Dharmesh Harwani, "Improvisation of Global Pairwise Sequence Alignment Algorithm Using Dynamic Programming ", International Journal of Scientific Research in Computer Science, Engineering and Information Technology (IJSRCSEIT), ISSN : 2456-3307, Volume 2, Issue 6, pp.909-914, November-December-2017. |          | BibTeX | RIS | CSV

Article Preview