Lecture 4

Alignment by Dynamic Programming
January 13, 2000
Notes: Martin Tompa

4.1. Computing an Optimal Alignment by Dynamic Programming
Given strings and  , with  , our goal is to compute an optimal alignment of and  and    .Toward and   this goal, define  as the value of an optimal alignment of the strings  .
The value of an optimal alignment of and  is then !"# . The crux of dynamic programming is tosolve the more general problems of computing all values $ with %'&(&( and %)&*+&( , in orderof increasing  and  . Each of these will be relatively simple to compute, given the values already computed
for smaller  and/or  , using a “recurrence relation”. To start the process, we need a “basis” for ,-% and/or
.-% .
BASIS :)%$/%01/%01
%$>% /%043657  829: for <;=% )%$2 ?3@57"2AB  : for );C%),2The basis for /%0 says that if  characters of are to be aligned with 0 characters of  , then they mustall be matched with spaces. The basis for %$ is analogous.
R ECURRENCE : For D;=% and );C% ,/$EGF HJIKL M2  L2 N3
M2  32 3   57    B  O
57  8 2P 
57"2AB  This formula can be understood by considering an optimal alignment of the first  characters from andthe first  characters from  . In particular, consider the last aligned pair of characters in such an alignment.
This last pair must be one of the following:   , in which case the remaining alignment excluding this pair must be an optimal alignment B    ofM2and  L2(i.e., must have value M2 2  ), or 2.
 829 , in which case the remaining alignment excluding this pair must have value ,2 $ , or

1.

17

LECTURE 4. ALIGNMENT BY DYNAMIC PROGRAMMING18 

3. "2AB   , in which case the remaining alignment excluding this pair must must have value )42.

The optimal alignment chooses whichever among these three possibilities has the greatest value.

4.1.1. Example
In aligning acbcdb and cadbd, the dynamic programming algorithm fills in the following values for(As in the$ from top to bottom and left to right, simply applying the basis and recurrence formulas.
example of Section 3.3, assume that matches score 3 , and mismatches and spaces score 2 .) For instance,in the table below, the entry in row 4 and column 1 is obtained by computing F HJIK"2M3 /% 2 82<2 2 .

%%

 %
2

2 

2

2 2 %

%

22

2 
222%

 2 

222

2 



%
2 2 %222%
22



2






%

The value of the optimal alignment is !"# , and so can be read from the entry in the last row and lastcolumn. Thus, there is an alignment of acbcdb and cadbd that has value 2, so the alignment proposed
in Section 3.3 with value 1 is not optimal. But how can one determine the optimal alignment itself, and notjust its value?

4.1.2. Recovering the Alignments
The solution is to retrace the dynamic programming steps back from the !"# entry, determining which
preceding entries were responsible for the current one. For instance, in the table below, the (4,2) entry could
have followed from either the (3,1) or (3,2) entry; this is denoted by the two arrows pointing to those entries.
We can then follow any of these paths from !"# to %$/%0 , tracing out an optimal alignment:

%

%

 %

22N22%

2

2222 

2 
22%

2222%

22%

%2 

2 N%The optimal alignments corresponding to these three paths are2 2  %

22  

LECTURE 4. ALIGNMENT BY DYNAMIC PROGRAMMING

a-ccb-

caddbbd,

a-ccbac-ddbbd19, andc

Each of these has three matches, one mismatch, and three spaces, for a value of optimal alignment value.

aa

cd

M3bbc-dd

  "2   b-.
, the4.1.3. Time Analysis
Theorem 4.1: The dynamic programming algorithm computes an optimal alignment in timeK# .



Proof: This algorithm requires an #3
6 3  table to be completed. Any particular entry iscomputed with a maximum of 6 table lookups, 3 additions, and a three-way maximum, that is, in time  , a  3 P
K# . Reconstructing aconstant. Thus, the complexity of the algorithm is at most J+3
single alignment can then be done in time )3 # .
4.2. Searching for Local Similarity
Next we will discuss some variants of the dynamic programming approach to string alignment. We do
this to demonstrate the versatility of the approach, and because the variants themselves arise in biologicalapplications.
In the variant called “local similarity”, we are searching for regions of similarity between two strings,
within contexts that may be dissimilar. An example in which this arises is if we have two long DNA
sequences that each contain a given gene, or perhaps closely related genes. Certainly the “global” alignment
problem of Definitions 3.3 and 3.4 will not in general identify these genes.
We can formulate this problem as the local alignment problem: Given two strings and  , with  (and   , find substrings (i.e., contiguous subsequences)  of and  of  such that the optimal(global) alignment of  and  has the maximum value over all such substrings  and  . In other words,
the optimal alignment of  and  must have at least as great a value as the optimal alignment of any othersubstrings  of and  of  .

4.2.1. An Obvious Local Alignment Algorithm
The definition above immediately suggests an algorithm for local alignment:
for all substrings  of dofor all substrings  of  do
Find an optimal alignment of  and  by dynamic programming;
Retain  and  with maximum alignment value, and their alignment;
end ;
end ;
Output the retained  ,  , and alignment;

LECTURE 4. ALIGNMENT BY DYNAMIC PROGRAMMING

20

There are   choices of  , and   choices of  (excluding the length 0 substrings as choices).
Using Theorem 4.1, it is not difficult to show that the time taken by this algorithm is  8 . We will seein Section 5.1, however, that it is possible to compute the optimal local alignment in time K# , that is,
the same time used for the optimal global alignment.




4.2.2. Set-Up for Local Alignment by Dynamic Programming
Definition 4.2: The empty string  is the string with ,0-% .
Definition 4.3: where #   .

is a prefix ofDefinition 4.4:  is a suffix of
#   .

if and only if or For example, let  abcxdex. The prefixes ofempty string  is both a prefix and a suffix of .

 , for some   or   , for some &

if and only if 8 

include ab. The suffixes of&&  ,&6 , where

include xdex. The

Definition 4.5: Let and  be strings with  $  and  - . For %)&= &( and %'&* &( , let /$ be the maximumvalueof an optimal (global) alignment of  and  over all suffixes  of  and all suffixes  of   .
For example, suppose  abcxdex and G xxxcde. Score a match as 3
as 2 . Then    D  , with   cxd,   cd, and alignment
cc+22x-and a mismatch or space

dd+2

The dynamic programming algorithm for optimal local alignment is similar to the dynamic programmingalgorithm for optimal global alignment given in Section 4.1. It proceeds by filling in a table with the valuesof  $ , with / increasing. The value of each entry is calculated according to a new basis and recurrencefor  /$ , given in Section 5.1. Unlike the global alignment algorithm, however, the value of the optimal
local alignment can be any entry, whichever contains the maximum of all )3   3  values of   .
The reason for this is that each   entry represents an optimal pair  , of suffixes of a given pair8     B   of prefixes. Since a suffix of a prefix is just a substring, we find the optimal pairof substrings by maximizing   over all possible pairs /$ .