Generalizing the Alignment Score
The edit alignment score in “Edit Distance Alignment” counted the total number of edit operations implied by an alignment; we could equivalently think of this scoring function as assigning a cost of 1 to each such operation. Another common scoring function awards matched symbols with 1 and penalizes substituted/inserted/deleted symbols equally by assigning each one a score of 0, so that the maximum score of an alignment becomes the length of a longest common subsequence of
$s$and $t$(see “Finding a Shared Spliced Motif”). In general, the alignment score is simply a scoring function that assigns costs to edit operations encoded by the alignment.
One natural way of adding complexity to alignment scoring functions is by changing the alignment score based on which symbols are substituted; many methods have been proposed for doing this. Another way to do so is to vary the penalty assigned to the insertion or deletion of symbols.
To penalize symbol substitutions differently depending on which two symbols are
involved in the substitution, we obtain a scoring matrix
A gap penalty is the component deducted from alignment score due to the presence of a gap.
A gap penalty may be a function of the length of the gap; for example, a
linear gap penalty is a constant
Return: The maximum alignment score between
>Rosalind_67 PLEASANTLY >Rosalind_17 MEANLY