Improvisation of Global Pairwise Sequence Alignment Algorithm Using Dynamic Programming

Abstract

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.