July 2, 2012, midnight by Rosalind Team

**Topics**:
Alignment,
Dynamic Programming

## Mind the Gap

In “Global Alignment with Scoring Matrix”, we considered a linear gap penalty, in which each inserted/deleted symbol contributes the exact same amount to the calculation of alignment score. However, as we mentioned in “Global Alignment with Constant Gap Penalty”, a single large insertion/deletion (due to a rearrangement is then punished very strictly, and so we proposed a constant gap penalty.

Yet large insertions occur far more rarely than small insertions and deletions. As a result, a more practical method of penalizing gaps is to use a hybrid of these two types of penalties in which we charge one constant penalty for

beginninga gap and another constant penalty for everyadditionalsymbol added or deleted.

An affine gap penalty is written as

We can view the gap opening penalty as charging for the first gap symbol, and the gap extension penalty as charging for each subsequent symbol added to the gap.

For example, if

Consider the strings "PRTEINS" and "PRTWPSEIN". If we use the BLOSUM62 scoring matrix
and an affine gap penalty with

PRT---EINS ||| ||| PRTWPSEIN-

Matched symbols contribute a total of 32 to the calculation of the alignment's score, and the gaps cost 13 and 11 respectively, yielding a total score of 8.

Given: Two protein strings

Return: The maximum alignment score between

- The BLOSUM62 scoring matrix.
- Gap opening penalty equal to 11.
- Gap extension penalty equal to 1.

>Rosalind_49 PRTEINS >Rosalind_47 PRTWPSEIN

8 PRT---EINS PRTWPSEIN-