Video 3-4: Local and semiglobal alignments

0:02 In this section, we'll look at at global and local and semi-local um alignments. And global is essentially what we've done so far. Um what I mean by that is we assumed that we've given exactly the regions we want to compare. Like in the initial hemoglobin example, there's these two subunits and there's a gene encoding exactly that protein and the full protein we expect to do very similar things. Uh then what we've done so far with edit distance roughly matches what we want to do. Um more often than that actually we're we're looking for similar regions but we don't know exactly where they are and we can slightly tweak our notion of edit scripts and of distances and still get the same thing. uh in particular uh as edit scripts you can include these operations that allow you to delete or insert at the end of the edit script for free. I wrote it here as ignore prefix or ignore suffix.

1:07 Um you could have also said it's a it's a free insertion or free deletion and that's what uh then call is called a local alignment. So you should think of it as you have some potentially long string, you have some potentially long other string and then there's uh a region where they really have a lot in common. You might still have some mismatches and gaps and so on, but not not too many overall. Uh but you're really um as part of the algorithm, you're zooming in on the part that is is uh most similar. Uh that's the goal anyways. Now, if you think about how we defined edit distance, uh there's a problem because edit distance uh can only get worse if you add more of the string in. The more string you add, the more opportunities for having distances or having operations that you uh need to count. So, for local alignments, you have to flip things around. Instead of uh minimizing a distance, you have to maximize some score. So you have to reward the matches explicitly.

2:21 Otherwise, you'll always get the trivial solution. Oh, just pick the empty string from both. They are very similar. [snorts] Uh that's an easy switch. It's essentially just um putting uh the opposite sign there. And maybe um while we're at it, we might as well give the matching parts uh an actual value so that we encourage the algorithm to pick the longest region that it can uh put in good alignment to the other string. So we maximize some abstract score. Uh we'll come back to that a little bit. Uh we usually here for the first part, let's just say we stick with unit costs or unit rewards. So a match contributes a plus one and the others uh mismatches and and gaps maybe are penalties of minus one.

3:13 Now the other thing we need to do in if you think about our uh dynamic programming approach is to incorporate these these special operations and uh they look like they're symmetric but from the point of view of the algorithm you handle them slightly differently. If you want to allow ignoring a prefix of the string, what that means is at any point in time in your dynamic programming matrix, you used to have these three options of where you can come from and you pick the best of those three. Now for local alignments, there's a fourth option which is just start from scratch and forget everything else. which means there's a a constant zero that you can also use as your uh your preceding state. But that that's also all that that is needed. This just means uh if I'm in a position I J and I'm choosing the zero option.

4:27 That means I'm ignoring the first I characters of the first string and the first J characters of the second string like simultaneously. So it outputs these two. Uh so we're ignoring these ignore. If you pick this uh this zero option, that's for ignoring prefixes. You could try to ignore suffixes in the same way. Uh I think con more convenient for the algorithm is just to say uh at any position in the table, I'm allowed to stop because that corresponds to the prefix up to I and J anyways. And so if I don't want to include the rest of the strings, just do nothing. Which means uh for the final step, we'll not just output the top right the bottom right corner, but the best value over the entire matrix. It's another scan of the matrix by of course you could also keep track of the the current maximum you've seen so far instead of scanning again, but that's um that's not a big difference.

5:47 So I'm uh I'm ignoring this part. So the free suffix comes from stopping here which means we're ignoring these two. Where going? I've already disabled all the scroll bars. I don't even know why this uh why this happens.

6:35 So it's it's really a very simple change and you can uh adapt the recurrence to reflect the change. the starting with zero has uh shows up uh in three places in the recurrence because we kind of split this case up previously. Uh we have these boundary cases where you could only do insertions or deletions. But this is exactly at the beginning of the alignment. So there it makes no sense to pick the better option of starting from scratch or doing a bunch of deletions or insertions at the beginning. the optimum will always be just do the zero uh and then you have this additional case in the regular interior of the matrix where opposed to uh the three choices we now have this fourth option and I've flipped the signs around for the others so this was a plus one for the distance now it's a minus one for the score because we do a mismatch and similarly here I get a plus one for a match And currently a zero for a mismatch.

7:44 Um not sure if that was my intention. You could of course patch this to say minus the same thing with equal not equal. So now it's always going to be one of the two. You can write it in different ways.

8:25 The the fear is if you pick the score wrong then zero will still be it might still be better to just do nothing. But because we uh reward the matches um I think the problem is is still sensible and the final output is not the lowest corner but you pick the maximum over all entries.

8:50 What you can also see here is it's not too hard to play with the score. We'll briefly look at this more systematically in a minute. Uh but if you wanted to somehow treat insertions and deletions differently from say mismatches, you could just put in different constants here. The algorithm couldn't care less.

9:17 Okay. Um there's a a twist on this variant uh which I know as semi-local alignments. um also has this this name fitting alignment. Um sometimes you know that one string is much longer than the other and you're just trying to find a a kind of fuzzy match of uh substring a of a as a substring in B. So you don't want to allow the um prefix and suffix ignoring operations for B, but you do include them for A.

9:57 This is much closer to finding fuzzy matches of a string in a longer string. Um so you can also try to solve it uh via methods there. But if you want the full generality of the scores then you can use uh alignment algorithms.

10:12 Um, so what changes is that only some of these zeros are allowed. I'm no longer allowed in the middle of the matrix to just restart from zero. I can only do this when I'm um at the beginning when I when I've not used characters from I. Then uh I can kind of uh insert the characters in B for free. Um I'm still going to have to optimize at the end over not the entire matrix but from the last column. So this is A, right? Um, I want to keep all of A, but I'm I'm fine to ignore any suffix of B. Sorry, the other way around. So, uh, sorry, I'm finding A and B, so I want to ignore suffixes of B.

11:31 Looks right. the I think the formula is okay. Okay. Yeah. Any of these positions ignores a suffix of B. And that's what we want to do. And the rest of the uh the rest of the dynamic programming recursion is as for the local alignments. So probably also with the tweak I've done here, I want to punish the mismatches somehow.

12:06 The other option would be this, right? No, not like this. Okay, it's the same as as for the other one. Um, we're going to modify the scores in a second anyways.

12:30 Uh you can you can further play with this and do other variations and other combinations of which ones to ignore, which ones to include. I don't think these have special names.