Video 3-3: General alignment scores

0:04 As I mentioned already, the algorithm is very flexible in terms of how you score different things and that's indeed something for the biological application that is is very interesting to um have a closer look at. Uh first of all, whenever in the algorithm we're recording a mismatch, we know exactly what character is mismatched. So we could easily say there's a special mismatch cost for replacing any character by some other character depending on those two specific characters.

0:40 And this is essentially what at the very beginning what happened in this amino acid alignment. There's some amino acids that are closer to each other. So you want to keep the cost of replacing one of these with one of a similar group lower. that's uh giving some small positive score, not as much as a match, but still something. Whereas uh if you replace it with something that's very different, you might want to penalize that.

1:10 Um in full generality, we can what the algorithm can support is any kind of score that gives every column in an alignment some value. So that the total score is the sum of the column um column values and by column here I mean the two characters on top of each other not the columns in the matrix. Um just to pick uh names for that we can have uh a matrix that tells us if I'm replacing a certain character by a certain other character what is the score for that? Um, I'm insisting here that it's symmetric so that the whole alignment is symmetric to replacing A and B, swapping A and B. Uh, that tends to be what what biologists use. I guess it's probably just a user interface confusion if it makes a difference which order to put the strings in. Um, from an evolutionary perspective, I could imagine it might might make sense to say that one direction is more likely than the other.

2:16 I think this is actually known that there are some cases like this. Uh but here for general alignment scores um the assumption is that it's symmetric. Uh so you have the case where you're either have a match or you have a mismatch and then you have one other parameter for a gap again because it's it wants to be symmetric. It treats insertions and deletions the same. So these are both valued with G uh usually negative and the others are valued with whatever the matrix says. Okay, as before the total score of an alignment is the sum over all individual columns. We've always used this implicitly that the overall score is the sum of things. It used to be the number of operations that the sum of ones and so on. Uh so that's it's all the same. It's all staying the same. um just phrasing it explicitly because we want to be as general as the algorithm easily allows.

3:16 Okay, let's see some um some concrete example of what this looks like for proteins. And what people worked out is there's there's groups of proteins that are functionally similar. And here the matrix is sorted so that so that these are forming nice submatrices. And you see here they actually get a a positive score. So the largest numbers tend to be on the diagonal, but there's also some off diagonal entries within these uh within these groups that are still considered a match or a positive score contribution. Uh whereas then for the others um you tend to have uh penalty effects, but they're not all the same. So uh the way this matrix comes about is from studying proteins that we know look it's the same kind of protein in different species and you compare them also across time and you see how often one amino acid mutated into another and essentially the numbers that you see here are log odd scores. So you somehow uh compare how often do you see uh these amino acids in general without being paired and how often do you see one turned into the other and from on a logarithmic scale uh you get these numbers uh I guess they're then rounded because certainly not all integers this is I'm just mentioning this as one example blossom matrices there's a specific methodology of how to get these numbers from data and that was what was used in the alignment I showed initially um that's uh producing this hemoglobin alignment if you use these numbers.

5:14 Uh the last bit that we want to generalize from the biological motivation is it doesn't really make sense that insertions and deletions are treated individually. Uh this is a bit depending on the exact process of of evolution or mutations that you're looking at. Uh but there's several places where it's more likely that you have consecutive insertion of of a number of characters in one spot. So in a way if you're you're already cracking the thing open and insert something having a few extra insertions doesn't increase the cost in the same amount as having this first opening.

5:57 So at the moment we're treating a stretch of k characters consecutive insertion the same as some isolated single character insertions scattered through the string. And that's biologically not accurate. A simple way to fix that that seems good enough uh even though it's a crude approximation I'm sure is to say we have a fine cost. So instead of just K * G for a gap of size K we have some offset and you should think of this one being much bigger. That's the kind of penalty to open an insertion round or open a gap and then extending the gap is a much smaller uh uh marginal cost.

6:50 There's a cute way that uh we came up with and I haven't seen it somewhere formulated but it's just a cute way to um write this down and in the alignments with columns. We had insertions like this before. Now if you have a contiguous round of insertions, you could have the convention that the first one is marked as opening a gap and the others as continuing a gap. then you can assign scores just based on on these two characters and that automatically gives you a fine cost functions. That's just a hint that really dealing with these generalized fine gap costs is not a big deal because all you need is one extra type of gap symbol. So you'll have one extra case in the dynamic programming table but apart from that um not much uh not much uh happens to the algorithm and uh you'll have a look at this in the exercises in a bit more detail.