Ideal Gap Penalty

Recall from previous lecture we can find the alignment between two DNA sequences by either performing global alignment using Needleman-Wunsch algorithm or local alignment using Smith-Waterman algorithm. The method the two algorithms used to handle gaps is of particular interest. Thus far the strategy is to add a fixed gap penalty when a gap occurs regardless what the alignment was for the previous nucleotide residue (see Figure 1). Below is the algorithm for calculating the alignment score based on linear gap penalty. This algorithm has both running time and space usage that is linear O(nm).),,()1,1(max(), ( ji BAsjiMjiM +−−