From edit distance to alignment scores
Last updated
Last updated
Up until now, we discussed a fairly simple way of computing the score of the alignment in terms of the number of edits that need to be made to convert one string into the other. Nature, however, is not a typewriter, thus we may want to define alignment scores in a way that better captures the biological relationships between sequences. If we somehow define such a score, could we still compute the alignments using the algorithm we just defined?
As we'll show below, the dynamic programming algorithm we created still works for a number of scoring systems that can incorporate biological knowledge. Note, however, that it is not necessarily obvious that this algorithm should work, and there are some scoring systems for alignments for which we do not have a good way of computing the optimal alignment. One example is the situation in which we allow an additional edit — the transposition of two neighboring letters (i.e., changing from ABCD to ACBD in one single edit by swapping the order of letters B and C). Optimizing such a scoring system is an NP-hard problem, unlike our simple model that only accounts for insertions, deletions, and substitutions.
Assume we are given a biologically-informed function , that can provide us with a score for any pair of aligned characters (including '-' to indicate in indel). Mathematically, , where represents the alphabet from which the strings are constructed (i.e., for DNA). We can now rewrite the recurrence equations as:
Note that the diagonal case (the first equation) automatically accounts for the situation in which the two characters being aligned are either the same or different. You can also see that in the edit distance case earlier, we could have simply defined the function as:
f(a, b) = (a==b ? 0 : 1)
In the graph formulation, the function will assign the weights of the edges (which are fixed throughout the algorithm since they only depend on the corresponding characters), thus you can easily see that we should still be able to compute a shortest path through the graph, even if the weights on the edges are arbitrary. Thus, I hope you agree that our initial algorithm will work for more complex scoring functions.
What is perhaps a bit less clear, is that we could choose a function that rewards matches rather than penalize edits as we've done so far. If we do so, the best alignment would be the one that maximizes the score, thus we have to change the recurrence equation to be:
The algorithm would stay the same as before, but we'll select the maximum among the three possible "edits" at each location in the matrix instead of the minimum as we've done so far.
At this point, we will not go into a lot of detail about how one defines a biologically-relevant scoring function. At a very high level, such functions are defined by statistically analyzing alignments that we know have some biological meaning (e.g., by aligning proteins that have the same function but have different sequences). In the case of DNA, one can think of a number of factors that we could account for — for example, when discussing , we mentioned deamination — the fact that a C could easily mutate into a T . Thus, a biologically-informed scoring function could assign a higher score (or lower penalty) to C-T alignments than to other pairings of letters. Also, such a function could prioritize alignments that match a purine with a purine, or pyrimidine to a pyrimidine and increase the penalty (or decrease the score) of purine-pyrimidine alignments.
Scoring functions, are, however, more commonly used to guide alignments of protein sequences. There the alphabet has 20 letters (for the 20 amino acids) and there are many possible pairings, some of which are more likely than others. A commonly used substitution matrix is the BLOSUM-62 matrix shown below:
(source )
Note that this matrix is symmetric () and has been normalized to only contain integers. The gap character is indicated by a '*' symbol here (rather than the '-' symbol we used earlier).