Video 3-1: Sequence alignment and edit distance

0:02 In the next unit, we'll look at some algorithms to compare sequences. This is in hidden versions. We've looked at this before, but let's do a a more strate more more systematic study of what can and cannot be easily done there and become also let's get a bit more uh quantitative and precise what what really we mean by comparing sequences or similar sequences and all that. Um and the chapter is a lot more algorithmic in a way uh with clean and kind of basic algorithms where you can say something something about um the tentative outline has a lot of topics I'd love to say a little bit about um they start from extremely basic and go to much more uh sophisticated so maybe uh the level of coverage will have to be uh adapted to that a Let's start with the basic motivation first. As always in this module, there's some biology behind it. Um I shown I've shown this picture at the very beginning as one example of a protein that uh fulfills an important function. That's hemoglobin or the human hemoglobin to be precise.

1:21 And you see it consists of these four colored things. Now, each of the colored strands is one protein chain that folds into this specific three-dimensional shape. And uh there's actually two um that are always equal. The blue ones, they're separate, but they're identical copies of the same protein. Same for the red one. And they have these names, the human hemoglobin subunit, either the alpha version or the beta version. uh the green bits that are sticking in there, which in in this picture maybe is a bit less easy to see. Uh conceptually, there's these four blobs that connect and each of them has a little uh this green part, a heem group, which is a a nonproine molecule with one iron in the middle. So there's one iron. So each of these hemoglobin complexes can capture four oxygen molecules, one in each of these pockets. They attach to the iron and then well can release again um depending on the chemistry of the environment.

2:34 So this is really really small. You have lots of those molecules in your blood cells. And well what you can maybe guess from from the schematic drawing and uh if you rotate this thing uh in the right way also see in the three-dimensional structure is that the red and the blue proteins are very similar. They're essentially fulfilling the same same kind of function. And in particular, they have these parts that hold the green parts in place which are highly conserved. And if you modify them, then they don't work anymore. And usually people don't survive that. So uh all living beings that have um blood cells of of some sort will have very similar uh proteins here. And let's take this as an example. Now, um it seems evolutionarily why we have the alpha and beta version. As always in biology, there's more varieties and then there's uh specific diseases that also express slightly different proteins.

3:39 It might just be an evolutionary coincidence that these two um they certainly come from a common ancestor. Then at some point there was a mutation and they branched off. And then by forming this this structure where the opposite ones are the same, maybe they even evolved to be a little more stable that way. Uh but from my from my understanding of the biology, it's not clear what that you would need these four these two separate copies. You could have maybe left with four identical versions of the of the protein, but that's what it is now. At least the claim is these alpha and beta globin versions should be very similar. Now you can click on those links. That's a database with um all the proteins that are known and you can look up the amino acid sequence of these two proteins. That's the red one and the blue one. They're not exactly the same length.

4:37 That's the first nuisance. And I know it's fairly small and I had to squeeze it together to fit them uh on the in one line. Maybe you uh at least visually agree that they don't actually look all that similar and um that they fulfill the essentially identical role is no longer visible. There's two reasons for that. Um, one is one that if you stare at it for long enough, um, you may see that there's some parts like there's KKV, KKV, but then also it's not, uh, it's not like there's nothing to be found that is similar, but it's shifted. There's a second reason which is more annoying because I didn't give you a chance to see it. There's some amino acids that are replaced from one to the other but their chemical function and structure is very similar so that in fact they can fulfill the same role but as a letter they are different and so uh our abstraction to represent them by some uh arbitrary letters in the alphabet is is not so helpful here. But the second part, this this first part that there seems to be similarity, but it is it is not in the same places means you have to at least work a little harder to find it. And that's what this unit is about. Uh these don't look so similar. Uh but there's tools that specifically also know that these are proteins. Um and they form what's called an alignment. So you uh strategically stretch either of the strands by inserting these gap symbols. So you just make room for the other strand to catch up.

6:25 And you see this vertical line in all the places where there's a matching character in top and bottom. And in in addition, there's these these colons, which means there's not the same character, but they're at least chemically similar. So if you add those two up, there's there's 65 of these exact correspondences and 25 more where the amino acids are at least similar. The two are indeed 60% the same and 60% the same same structure or function. Then there's a few uh places where there's been stretches or deletions and there's a few places where amino acids have been replaced. My uh my hypothesis would be that if you look in the if you trace this to where the structure is that they may be just not part of this relevant bit in the middle that keep the the he uh group in place but they are in a in a position where it doesn't matter and that teaches you two things like number one uh you can definitely use this to find highly similar things 60% the same that's for for biological sequences that's like identical. This is amazingly good match. Um and then the second thing is by forming this alignment you learn a lot about the different parts. You learn the highly conserved parts. Uh probably that there's these four identical matches separated by one and something more.

7:56 Maybe this is the central part around the green thing. So you can identify the highly conserved regions locally. Um, and you might also have a hint. Maybe this one, this long stretch that got inserted, you can locate and try to find or uh combine combine knowledge from from different pieces um of evidence that you have. And this is another piece of evidence tells you which which strands may be less important because they're more variable. That's the kind of backdrop. Now we'll look at how to compute those and uh how to modify the the basic algorithms to various needs that are slightly similar to this one but have some other features.

8:51 From computer science perspective, we're essentially talking about string distances. So we have uh strings that are not the same but also not completely random and we want to measure how close they are in some uh well- definfined way. In bioinformatics this always comes from mutations but uh we'll abstract from that most of the for most of this unit. Uh we'll look at various options. Um but the the good thing is that they are algorithmically somewhat similar. So we often can do a unified framework for solving them. Uh but there's a few uh also algorithmic tweaks that you can apply to these kind of algorithms that maybe uh are not so obvious or are say uh adequate for a mast's level module. The last statement we'll only come back to at the very end. Uh the general problem if you're looking for these alignments is a hard problem when the number of sequences grows for two sequences you'll see uh life is fairly easy and we have efficient algorithms that find best possible alignments in the sense we we will define if you add more sequences then this becomes much harder and this is unfortunate because often times what biologists would like to do is take the same protein they know the same they know the gene in the DNA then compare that gene across different species that are more or less closely related or have diverged from a common ancestor more or less recently and uh compare which parts are uh conserved which are variable all these things and then you want to do this with a whole lot of sequences dozens or hundreds and this is still not solved however this is the underlying problem is np hard so it's it's going to be tricky uh but I think this is still actively worked on on how to best deal with it.

10:48 Okay, we've already seen string distances the Hamming distance uh but uh it has a a major shortcoming. Um I mean Hamming distance was just defined as the number of mismatches and uh it was only defined for strings of the same length. So there was no question of shifting things around. Um so you can't even use it if the strings are not the same length as in our protein example. But more more critically if you have strings like these two which are largely identical if only you were able to not if I noticed the small shift uh Hamming distance would still say they're maximally different. That's not useful in our context. So clearly Hamming distance is not the one. The good thing about Hamming distance, it's trivial to compute. You just scan the strings and that's it. There's no no optimization process behind it. Okay. Uh what can we do that's a little better. The I guess most natural definition um ignoring all of biology for now is edit distance where you ask yourself the question assume I start with one string and I'm allowed certain small operations that modify individual characters. How can I get from that first string to the second with the the smallest number of operations? And as a concrete example for these two strings, I mean I claimed these should be very similar because they have a large uh shared substring.

12:26 So we could take the first string. I guess uh that should be a the way I called it above. Um I'm deleting the first character.

12:39 So that one's gone. And then I'm inserting an S at the end. And then the claim is I arrive at B. And you can verify in this case. So here the edit distance is two. It's at most two from this edit script which proves I can do it with two operations. Now you would also have to to prove for the equality that you cannot do it with one. But since there are two positions um that differ uh I think this is it's kind of evident by just trying all possible operations a single one will not fix both places which also means that this edit script is is an optimal edit script because has the fewest operations among all that work for A and B. The general algorithmic problem then is given two strings and we'll always have a of length m and b of length n. So try to keep that in mind. Um I'll try to repeat it on the slides wherever it's needed.

13:46 In general there are over some alphabets uh most of the time it will be for biological sequences either four letters or or 20 letters. Uh so in particular the alphabet most of the time is is is fixed and is not growing makes some of the algorithms easier.

14:08 Okay, we'll focus on in the algorithms on computing the distance itself as a number as opposed to outputting the edit script as uh as kind of procedure to get from one string to the other. We'll come back to also producing the script. The point here is all the algorithms we'll look at. Um all the algorithms I'll present in detail will it's very easy to augment them from just computing the distance to also producing the edit script. So it's it's not a hard step but it makes the formulation a bit more concise.

14:57 Okay. Um let's see another small example algorithm logarithm. Uh here's a concrete edit script. Um, similar to the previous example, uh, I want to connect this explicitly to the biological motivation where I didn't talk about edit scripts al although I guess I could have, uh, but for, uh, this quick visual um, information about the two sequences, this alignment, this writing of the two strings on top of each other with some annotation in in between potentially, that's that's more convenient. And the two are really ident. That's um what I'm what I'm trying to convince you of here. Whenever you have uh a deletion, then you'll have a character where there's a gap symbol in the corresponding uh second string. Whenever you have an insertion, like here in that position, you have a gap symbol in the top string and the letter in the in the lower one. And the other option is a replacement of a character.

15:58 I'm taking O and turning into an A. then these are just put on top of each other and I'll have to kind of count this as a mismatch. Whereas if you had for the other characters where they're put on top of each other, I'm counting them as a match. So you can easily go from edit scripts to this alignment notation and back. Uh it's it's kind of equivalent ways to represent the information. The edit script has the benefit that its size is bounded in terms of the the edit distance and the string alignment because you have to read the strings you could produce it in the same time. Um sometimes it's more convenient to think in in terms of one sometimes more in the other. So uh should uh not not get confused by um language switching back and forth.

16:59 uh for the algorithms it's sometimes convenient to represent the alignments a bit more uh formally. So I'll just write them as these pairs of characters. The middle line is not represented because that's implicit. I can have a match column. So that's the the same character in top and bottom. Or I can have uh a deletion or an insertion. That's one where I have a gap in one of the strings. and I can have a replacement. And so the alignment formally for us is a string over this alphabet of pairs. Okay. Uh we'll we'll write it in this more intuitive way. But if you have to uh properly define things, then it's a string over this pairs of characters. The only reason I wrote this in this more complicated way is we don't allow gap gap as a pair. Right? This would not make sense. No. Um, no edit no optimal edit script will ever contain this.

17:57 Uh, so let's not even include it. Okay. If you have an alignment written like this, then obviously counting the red things is giving you the edit distance. I'm I'm saying this is uh all very very basic stuff. Uh, but I don't want to rush it over. In case you've not seen edit distance, I don't know if it's uh a lot of a lot of details to take in. If you've seen it before, I'm probably boring you a bit. Um I want to point out a connection to another well-known problem, the longest common subsequence problem. And in a way, if you look at this example or also the previous one, they should they have something uh in in common. uh there's a relation between the two. A good alignment tends to have a long common uh subsequence, namely this this matching part. Um so in a in a V sense, the optimal edit script gives you somehow the longest match, but it's not identical.

19:02 Uh it would be So here's a an example showing um two strings. Okay, I've I've left out the gap symbols to make it stand out clearer. Um if you put the optimal alignment here, the edit distance would be the number of positions where you don't have this gap. So um we have one here for this mismatch. Then here's a mismatch. Um and here's another gap. So edit distance would be eight. But if you uh if you look at the longest in the longest common subsequence, it's actually a six A's. But here the optimal alignment only puts five of these A's in correspondence. And if you look at the example for for for a minute, you see the the problem is that we charge a replacement as cost one, same as insertion and deletion. Whereas finding the longest common subsequence treats a replacement of a character as an an insertion followed by a deletion or the other way around.

20:17 And so the costs uh kind of don't match exactly. If you were to only allow insert delete, then they're exactly the same. In the original edit distance where we allow replacing a symbol by another at the same cost as an insertion and deletion, you cannot directly reduce it to longest common subsequence. Although in spirit the two problems certainly are are related.