This page: Here we show a method of Sellers, which provides an algorithm to choose among the possible alignments and to calculate the distance of two sequences.

For example, consider these two sequences:

 

Site	1.	2.	3.	4.	5.	6.	7.	8.	9.	10.
Seq. 1	A	T	G	C	G	T	C	G	T	T
Seq. 2	A	T	C	C	G	C	G	T	C
mism.			*			*	*	*	*	-
.............	........	........	........	........	........	........	........	........	........	........

Sequence 1 and 2 differ in 5 sites in bases, and Seq. 1 is one base longer than Seq. 2. There are two types of events during evolution which could result in such differences. Firstly, fixed point mutations change bases in one or both sequences, secondly, bases might get lost or inserted in any of the two sequences. It is impossible to tell by comparing two sequencies, whether the difference for example in Site 3 is caused by a base change or by insertion/deletion in any of the two sequences.

Here we show a method of Sellers, which provides an algorithm to choose among the possible alignments and to calculate the distance of two sequences. The distance is measured here as

D = kg + lm,

where k is the number of gaps in the alignment, g is the gap penalty, l is the number of mismatches and m is the mismatch penalty.

Consider these two sequences:

ATCCGCGTC

Let us calculate the matrix element D_i,j as:
 
 

What does that mean? Each element of the matrix is an end of the possible alignments and the score (D_i,j) belonging to this alignment has to be written into the cell. If we want to align the i-th base of the first sequence (A_i) and the j-th base of the second sequence (B_j), there can be three cases:

.................................. B_i    -

2. A_i was optimally aligned with B_j-1, thus we need one more gap to align A_j to this alignment, and the alignment score will be D_i,j-1 + 1 gap penalty:

.................................. A_i    -

.................................. B_j-1 B_j

3. A_i-1 was optimally aligned with B_j-1, so the A_i and B_j elements get into the same position and we have to align them; if A_i and B_j are the same bases, the alignment score D_i,j will be the same as the score D_i-1,j-1, and if they differ, the alignment will contain one more mismatch, thus the score will be D_i-1,j-1 + 1 mismatch penalty:

...................................... A_i

...................................... B_j

Let's see our example:

• Let the gap penalty g = 2, and the mismatch penalty m = 1 !
• First we fill in the first row and the first column of the matrix. The scores are unambiguous because in the first row we can calculate D_i,1 only from the element D_i-1,1 (so D_i,1 will be D_i-1,1 + 2) and in the first column D_1,j only from the element D_1,j-1 (so D_1,j = D_1,j-1 + 2):

• Now we can proceed row by row; for example we must calculate the matrix element D_8,8

1. D_7,8 = 4 => D_8,8 = D_7,8 + g = 4 + 2 = 6

2. D_8,7 = 3 => D_8,8 = D_8,7 + g = 3 + 2 = 5

3. D_7,7 = 2 , A₇ is C and B₇ is G => D_8,8 = D_7,7 + m = 2 + 1 = 3

So the optimal alignment score of the first 7 bases of sequence A and the first 7 bases of sequence B will be 3 and this score has to be written into the cell D_8,8: (pay attention to the colours!)

 

• If we reach the right-bottom corner of the matrix we will get the best alignment score of the whole sequences. Back-tracking means that we start from the right -bottom corner and go along those elements from which the next alignment score was computed until we reach the left-upper corner, and the path will assign the best alignment (see the blue numbers):

The best alignment is:

A T G C G T C G T T

A T C C G - C G T C

Notes:
This method can be expanded to three or more sequences,  but the running time of the algorithm grows exponentially with the number of sequences. There are some methods by which the algorithm can be accelerated;  that of Spouge reduces the running time by computing only a fraction of the matrix: before the alignment procedure we must determine a test value (t), which might be the maximum expected alignment score of the sequences, and than only those matrix elements are calculated which satisfy D_i,j + |(n-i) - (m-j)|*g =< t (the meaning of the signs see above), and if in a row we reach this t-value, we needn't calculate the rest elements of the row.
Note that if the distance of the two sequences is more than t, the algorithm doesn't calculate the alignment score.
Note also that with this procedure a z-length gap has z-times more weight than a 1-length gap, and this has no biological relevance. (For example the deletion of three bases has usually larger probability than the deletion of one or two bases, because in the former case a there will not be frame-shift.) There are methods which attempt to correct this problem.