Lesson 5.9

Scoring Alignment

3 min read✓ Read

What is wrong with the LCS scoring model?

Recall Marahiel’s alignment of the A-domains coding for Asp and Orn, which had 19 + 10 matches:

It is not difficult to construct an alignment having even more matches at the expense of introducing more indels. Yet the more indels we add, the less biologically relevant the alignment becomes, as it diverges further and further from the biologically correct alignment found by Marahiel. Below is the alignment with the maximum number of matches, representing an LCS of length 19 + 8 + 19 = 46 (the green symbols represent new matches). This alignment is so long that we cannot fit it on a single line.

STOP and Think If Marahiel had constructed the alignment above, would he have been able to infer the eight amino acid-long signatures of the non-ribosomal code?

Below, we highlight the purple amino acids representing the non-ribosomal signatures. Although these signatures are grouped in eight conserved columns in Marahiel’s alignment from the beginning of the chapter, only five of these columns have “survived” in the LCS alignment from the previous step, making it impossible to infer the non-ribosomal signatures:

The frivolous matches hiding the real evolutionary scenario have appeared because nothing stopped us from introducing an excessive number of indels when building an LCS. Recalling our original alignment game in which we rewarded matched symbols, we need some way of penalizing indels and mismatches. First, let’s handle indels. Say that in addition to assigning matches a premium of +1, we decide to assess each indel a penalty of -4. The top-scoring alignment of the A-domains gets closer to the biologically correct alignment, with six of the columns corresponding to correctly aligned signatures.

Scoring matrices

To generalize the alignment scoring model, we still award +1 for matches, but we also penalize mismatches by some positive constant μ (the mismatch penalty) and indels by some positive constant σ (the indel penalty). As a result, the score of an alignment is equal to the following expression:

# matches − μ · # mismatches − σ · # indels

For example, with the parameters μ = 1 and σ = 2, the following alignment will be assigned a score of -4.

Biologists have further refined this cost function to allow for the fact that some mutations may be more likely than others, which calls for mismatches and indel penalties that differ depending on the specific symbols involved. We will extend the k-letter alphabet to include the space symbol and then construct a (k + 1) × (k + 1) scoring matrix score holding the score of aligning every pair of symbols. The scoring matrix for comparing DNA sequences (k = 4) when all mismatches are penalized by μ and all indels are penalized by σ is shown below.

Although scoring matrices for DNA sequence comparison are usually defined only by the parameters μ and σ, scoring matrices for protein sequence comparison weight different mutations differently and become quite involved. One example, the PAM₂₅₀ scoring matrix, is shown below (see "DETOUR: PAM Scoring Matrices" in the print companion or at Cogniterra).

Figure: The PAM₂₅₀ scoring matrix for protein alignment. Here, the indel penalty has been set to 8.