Chris lewis at the U of S



Email: Christopher Lewis

Affine Gap Penalties

This page aims to demonstrate the difference between affine gap penalties and regular gap penalties.

The following example is an extension to the Advanced Dynamic Programming example. They have used scores of +2 for a match, -2 for a gap, and -1 for a mismatch. I have substituted a C for the A used in the original example (position 7). This doesn't alter the score of the alignment, but it allows me to demonstrate the difference in alignments achieved using affine gap penalties.

      G A A T T C C G T T A
      |   | |   | ^ |     |
      G G A T _ C _ G _ _ A
         
      + - + + - + - + - - +
      2 1 2 2 2 2 2 2 2 2 2  = score 3

Figure 1 - Modified alignment from Advanced Dynamic Programming example.

Under their current scoring system, which uses a regular gap penalty, the alignment could also be written as in figure 2. This modification does not change the score, thus the two alignments are equivalent under this scoring system. For this new alignment, the C has been shifted one position to the right.

      G A A T T C C G T T A
      |   | |   > | |     |
      G G A T _ _ C G _ _ A
         
      + - + + - - + + - - +
      2 1 2 2 2 2 2 2 2 2 2  = score 3

Figure 2 - Modified alignment. Equivalent under regular gap penalty system.

Now let's look at these two alignments using affine gap penalties. We will use a gap open score of -2, and a gap extension score of -1. For the first alignment this results in a new score of 4 (Figure 3) as now when a gap is extended (there is more than one _ in a row) the score is only -1, whereas previously each gap received a score of -2 whether it was a new gap or an extension.

      G A A T T C C G T T A
      |   | |   |   |     |
      G G A T _ C _ G _ _ A
                        v 
      + - + + - + - + - - +
      2 1 2 2 2 2 2 2 2 1 2  = score 4

Figure 3 - Alignment from Figure 1 re-scored using affine gap penalties.

When re-scoring the second alignment using affine gap penalties, the new alignment score is 5 (Figure 4). This score is higher than the score achieved by the first alignment, and as such is the preferred alignment.

      G A A T T C C G T T A
      |   | |   > | |     |
      G G A T _ _ C G _ _ A
                v       v 
      + - + + - - + + - - +
      2 1 2 2 2 1 2 2 2 1 2  = score 5

Figure 4 - The alignment from Figure 2 re-scored using affine gap penalties.

This example demonstrates the difference using affine gap penalties rather than regular gap penalties. Affine gap penalties provide incentive for the alignment algorithm to keep sequence together where possible rather than inserting millions of small gaps. Generally this is the more desirable behavior, and so most alignment algorithms make use of affine gap penalties. One site I read (sorry, I can't remember which*) indicated that their software used a gap open penalty of 10, and a gap extension penalty of .5; so you can see how heavily they are favoring extension.

* Lisa Mullan of the EBI kindly sent me a note that the EMBOSS programs Needle and Water use penalties of 10 and 0.5. As I was just starting to use Needle and Water for a project, that is most likely the source from which I grabbed these numbers. Thanks Lisa.

A Work in Progress