Lecture 6: Protein Sequence Alignment and Dynamic Programming

Recording. Download the text transcript.

Automatic transcript; technical terms and equations may contain recognition errors.

00:00:00 Howdy. So we lost one lecture last Thursday. So luckily this time the snowstorm is not as bad as last year. I hope there's nothing but the frozen pipes, I guess. So let's get started. So this lecture is about the classical formulation of protein structure prediction. Remember, we're looking at different scenarios.

00:00:27 Let's start with the safe zone. And we started introducing optimization. And today we'll talk about sequence alignment and how it's formulated and solved by dynamic programming.

00:00:43 So previously we talked about the insights for protein structure prediction. We're asking how could this problem be solved computationally?

00:00:53 And what is the principle and what is the data? So I asked you what questions would you ask me if I'm a domain scientist for protein structure prediction?

00:01:06 And I got very good questions from all of you. So as an incomplete summary, I'd look like what is the principle and what is the data or knowledge?

00:01:15 So we talked about the protein structure prediction. So we talked about the protein structure prediction problem in various scenarios.

00:01:24 But remember, this is a classical formulation because the pattern back then from the limited data was very limited as well.

00:01:34 And then we used an introduction to optimization so that we can start talking about the safe zone.

00:01:40 So let's talk about where we are. We are talking about protein structure prediction now. We're looking at optimization perspective.

00:01:54 And we talked about mathematical optimization in general.

00:02:01 There are three elements of mathematical optimization, the decision variable, the constraints, and the objective function.

00:02:11 So depending on whether the objective function is a convex function in X and the feasible set defined by the constraints is convex for this feasible solutions,

00:02:27 So the easiest is we can classify the problems into convex versus non-convex.

00:02:33 So the easiness or not, where do you separate the two, lies in whether the problem is convex or non-convex.

00:02:44 Of course, among convex optimization, the easiest is linear programming that we're going to briefly talk about and continue today.

00:02:55 And we also learned about the other kind of types of optimization depending on the decision variable and depend on the constraints.

00:03:09 And you can rewrite a constraint optimization problem into unconstrained using the Lagrangian function.

00:03:17 So I should show this slide as a reminder.

00:03:24 Linear programming, by definition, has objective function that's linear in the decision variable.

00:03:34 And the constraints are also linear. Inequalities.

00:03:41 Linear programming, by definition, is linear in the decision variable.

00:03:46 So we're going to look at the feasible set.

00:03:48 And what about the feasible set?

00:03:52 We're going to look at each constraint.

00:03:54 Each constraint is written as A transpose X time less than or equal to B, where A and B are column vectors.

00:04:01 So in that case, each row is, sorry, A is a column vector and BI is a scalar.

00:04:14 So in this case, each constraint is defining a half space because equality is defining a hyperplane, right, in the n-dimensional space.

00:04:25 So if you have inequality, then that is a half space, right?

00:04:29 Then you have the intersection of many half spaces, which defines the feasible set as a polyhedron, okay?

00:04:38 So last time we said, if you remember,

00:04:45 what, let's see whether we have this one node saved somewhere.

00:04:52 If you remember, yeah, this was our illustration back then, if you remember.

00:05:02 So each constraint is defining a half space and intersection of them defines a polyhedron, which is your feasible set, right?

00:05:10 And then you have a linear objective function, right?

00:05:15 So if this C transpose X equal to a constant, then that defines a hyperplane, isn't it?

00:05:22 So if you move up or down, right, toward the direction of C or opposite to the direction of C,

00:05:30 essentially you are making this value, this equality value to be bigger or smaller, right?

00:05:35 So if you are minimizing this objective function, of course, you want to keep moving this one until it leaves,

00:05:43 starts to leave the feasible set, right?

00:05:46 Right?

00:05:47 So that is your global minimum in this case, right?

00:05:56 So we said that the extreme points are important, right?

00:06:00 Because most likely your global optimum candidates are in the extreme points, right?

00:06:06 Of course, there are some other possibilities.

00:06:09 For instance, this C transpose, right, X, where this C vector, right, or this hyperplane perpendicular to the C vector,

00:06:17 is parallel to one of these plane or side or facet of the polyhedron.

00:06:26 So it's possible that there is an entire edge or even the facet being the global optimum.

00:06:34 Is that right?

00:06:35 But in that case, the extreme points is still one of the global optimums.

00:06:39 So we are not violating anything.

00:06:42 So intuitively, one of the approach to solve linear optimization is to go through the extreme points, right,

00:06:56 following some order so that you don't have to keep repeating, right?

00:07:03 So in the worst case, you traverse all the extreme points and you are guaranteed to find the global optimum, right?

00:07:12 So what's the problem of that?

00:07:17 The problem is that there are too many extreme points.

00:07:20 If you have n dimension for the X and you have m constraints, how many extreme points do you have?

00:07:28 I'll leave this question for your after lecture exercise.

00:07:45 And then I'll give you the conclusion is, you know, in the end, you will find that

00:07:49 the number of extreme points is exponential in the input, the size of the problem, input problem.

00:07:58 So in other words,

00:08:03 you know, the so-called simplex algorithm, which goes through the extreme points following some,

00:08:11 you know, lexicography or order, right, is not a polynomial time algorithm.

00:08:17 It's actually exponential in the size of the problem.

00:08:21 So that is a bad thing, right?

00:08:23 So instead, you know, if you can follow some other algorithms like interior point algorithms,

00:08:30 as the name suggests, actually starts from the, you know, core or the interior of the feasible set

00:08:38 and then try to find the global optimum toward the extreme.

00:08:42 Those methods are actually polynomial.

00:08:44 Okay, so this is very friendly.

00:08:46 Okay, for large scale optimization especially.

00:08:49 And there are a lot of softwares that can help you solve this kind of linear programming problems.

00:08:53 Okay?

00:08:56 And last time we left a example, right?

00:09:00 We are asking about the diet problem, whether you can formulate it as an optimization problem.

00:09:07 And of course, it's a linear in this case.

00:09:09 So anyone want to share your answer?

00:09:15 Anyone?

00:09:22 Anyone did this exercise?

00:09:26 Okay, let's look at it together then.

00:09:28 So we have M, F, so let me write it again here.

00:09:36 So we have M, so this is the diet problem.

00:09:40 So we have M foods, F, where I goes from 1 to M.

00:09:53 Okay?

00:09:55 And we, each of them supplies, and they supply different nutrients, right?

00:10:01 So M, N, nutrients, food, nutrient.

00:10:08 So M1, and J, J goes from 1 to N.

00:10:14 Okay?

00:10:14 So M, N, and B is the minimum daily requirement of nutrient, and J, okay?

00:10:25 So,

00:10:29 mean requirement

00:10:35 of nutrient, J is B sub J.

00:10:40 So, okay.

00:10:42 And C, I is the price per unit for food, I.

00:10:47 So,

00:11:09 so an A, I, J is amount of nutrient, N, J contained in one unit of food, I.

00:11:15 So, A, I, J is the amount of nutrient,

00:11:27 J contained in one unit of food, I.

00:11:45 So, okay.

00:11:46 Okay?

00:11:46 So this is our definition.

00:11:50 So how to supply the required nutrients at minimum food cost?

00:11:55 So that's, that's your goal.

00:11:58 So what's the decision variable here?

00:12:05 What's the decision variable here?

00:12:07 What's the question asking you?

00:12:09 How to supply the required nutrients at minimum food cost?

00:12:13 What's the decision variable?

00:12:14 We need to minimize C with respect to each summation of C.

00:12:20 Are you excited?

00:12:21 We haven't defined it X yet.

00:12:23 Like X at the amount of different foods.

00:12:25 So the amount of

00:12:30 each kind of food we buy per day, right?

00:12:33 Right?

00:12:34 Right?

00:12:35 So the units of food we buy every day.

00:12:37 So, let's start.

00:12:40 So, the formulation.

00:12:44 So the decision variable,

00:12:50 as Ryan said, is X, what?

00:12:55 C, I, X, I, sum it to C, I, X.

00:12:57 No, let's start with X yet.

00:12:59 So, it's just X, I, right?

00:13:02 So, amount,

00:13:06 daily,

00:13:08 amount of F, I.

00:13:13 Is that right?

00:13:14 So that's our decision variable.

00:13:16 Okay.

00:13:17 So what's the objective function?

00:13:23 Right?

00:13:24 So, and we can rewrite

00:13:29 X as a vector, which is X1,

00:13:33 XI, XN.

00:13:36 Because there are N foods, right?

00:13:37 So what's our objective function?

00:13:41 So, right?

00:13:43 So, C transpose X.

00:13:45 In other words, the sum of

00:13:48 CI, XI.

00:13:50 Right?

00:13:56 I goes from 1 to N.

00:13:58 Right?

00:13:59 And we are trying to minimize

00:14:02 the cost.

00:14:03 Is it?

00:14:05 Pardon me?

00:14:07 Yeah, let's see.

00:14:08 How many?

00:14:09 We have M foods.

00:14:10 Yeah, thank you, Ryan.

00:14:11 And N nutrients.

00:14:12 So, be careful of that.

00:14:15 So, we have,

00:14:17 so here it should be M as well.

00:14:19 Wait a second.

00:14:19 Amount of food I.

00:14:22 Food, we have M.

00:14:23 Yeah.

00:14:24 So, should be M.

00:14:28 Okay?

00:14:28 So this should be M as well.

00:14:30 So I probably should swap the notation,

00:14:34 because usually we say that the X is in dimension N,

00:14:37 and there are M constraints.

00:14:38 Apparently here, we're a little bit different here.

00:14:41 Okay?

00:14:41 So what are the constraints?

00:14:47 So we have a daily requirement of each nutrient J.

00:14:52 Is that right?

00:14:52 So for any J from 1 to N.

00:14:56 Is that right?

00:14:58 Because there are N nutrients.

00:15:01 Right?

00:15:02 So for each nutrient, we have a daily minimum to satisfy.

00:15:08 Right?

00:15:09 Okay.

00:15:09 So this is our daily minimum.

00:15:12 Right?

00:15:13 But the actual intake every day is from all the foods.

00:15:18 Is that right?

00:15:19 So for each food, right, for each food I,

00:15:24 we can get A sub IJ amount of nutrients for nutrient J.

00:15:34 Right?

00:15:34 So that's exactly the nutrient J.

00:15:36 But remember, we take them from different food.

00:15:41 Food I and nutrient J.

00:15:48 So apparently the nutrient is not just coming from a single food.

00:15:52 It comes from a lot of food.

00:15:53 So we have to sum them together.

00:15:55 But what is the amount of food I got?

00:16:00 That exactly is in your XI.

00:16:03 All right?

00:16:04 Right?

00:16:05 So maybe I should write it.

00:16:10 Just to change the order.

00:16:11 It doesn't really matter here.

00:16:17 And I have I from 1 to how many foods?

00:16:23 Do I have?

00:16:23 M.

00:16:24 M?

00:16:26 Yes.

00:16:30 Right?

00:16:30 So in this case, the decision variable is in the M dimensional space.

00:16:35 And there are N constraints.

00:16:37 Is that right?

00:16:38 Because this is for any J.

00:16:39 Is that right?

00:16:40 So and I can rewrite this in the linear algebra way.

00:16:45 Right?

00:16:47 Like I can define a capital A.

00:16:49 Right?

00:16:53 Right?

00:16:53 Where A's elements are A sub ij.

00:16:57 And B is just a stacked vector of all the Bj's.

00:17:01 All right?

00:17:03 So this is a standard definition or example for linear programming.

00:17:10 Is that right?

00:17:11 Okay.

00:17:12 Okay.

00:17:12 So this is a very simple case.

00:17:14 But, you know, in many cases, it may not be that simple.

00:17:18 So it needs a lot of practice for formulation.

00:17:22 And also, another thing you have to be aware of is there are multiple formulations for the same problem

00:17:30 who will give you the same global optimum.

00:17:33 But some formulations are easier to solve than others.

00:17:37 So that's called strong formulations versus, you know, weaker formulations.

00:17:41 So something to keep in mind.

00:17:45 So now let's continue and start looking at one specific example that comes from the structure prediction,

00:17:55 specifically in the safe zone.

00:18:02 So I will remind you the safe zone.

00:18:05 And the, you know, the way to solve this problem is to find some protein sequences who are similar enough,

00:18:13 yet their structures are already solved.

00:18:15 So then we'll borrow those so-called homology.

00:18:18 Right?

00:18:20 So, and I think we mentioned that there are two kinds of problems that needs to be solved.

00:18:25 One is you need to figure out among a database of potential templates.

00:18:31 These database are sequences whose structures are already solved.

00:18:35 So you need to figure out among this database of, you know, 180,000 sequences, which ones are suitable templates.

00:18:44 So that's one problem we have to solve.

00:18:46 We're not solving that problem today.

00:18:48 We're solving the second problem.

00:18:50 So, once that template is found, how should I align that template sequence and the query sequence,

00:18:58 so that I know which portion of the templates should be directly borrowed,

00:19:03 and which portion needs to be modified, inserted or deleted?

00:19:07 So that's my question.

00:19:08 Okay?

00:19:08 So let's look at this problem, and then try to formulate it as an optimization problem,

00:19:15 and see how we can solve it.

00:19:16 Okay?

00:19:17 So we had a very simple diotech problem as a linear programming, right?

00:19:21 Let's look at this one.

00:19:22 Okay?

00:19:22 I put this, what you have learned before here, as a reminder of what is an optimization problem,

00:19:29 what are the elements?

00:19:30 Okay?

00:19:32 So now, let's talk about this problem.

00:19:34 Okay?

00:19:34 So you have two sequences, right?

00:19:36 So one is a template and one is a query.

00:19:40 Okay?

00:19:40 Okay?

00:19:41 And you want to, you know, sometimes you want to insert a dash or hyphen here,

00:19:48 which indicates, you know, a gap, right?

00:19:52 You could insert the gap in either of the sequences, so that at the end, the two sequences are of the

00:19:57 same length, including the gap.

00:20:01 But among all the possibilities, which I call alignments, which ones are the optimum?

00:20:08 You could define it in different ways.

00:20:09 Remember how you define things to be identical or similar among the different amino acids.

00:20:14 But let's start with the simplest one.

00:20:17 Okay?

00:20:17 Whenever we see an aligned pair of amino acids or letters being identical, we say,

00:20:25 oh, that's a great, that's a plus one.

00:20:27 Okay?

00:20:28 Whenever you see a misalignment, right, or, you know, a gap aligned to a character,

00:20:35 you say, oh, that's, you know, that's a zero.

00:20:38 Okay?

00:20:39 So in this simple form, I have one, two, three, four, five, the red ones, right?

00:20:45 And then additional stretch here and additional stretch here.

00:20:49 So the alignment score for this alignment, right, is about one, two, three, four, five, six, seven,

00:20:57 eight, nine, 10, one, two, three, four, five, six, so 19.

00:21:03 So that's objective function to some extent.

00:21:06 Okay?

00:21:06 So now let me ask you, the problem is already defined, okay?

00:21:11 We're aligning two sequences into the same length by adding gaps if necessary and maximize alignment scores.

00:21:20 So the alignment score can be defined in different ways depending on how you measure the score for each individual pair of amino acids.

00:21:29 I introduce the simplest form.

00:21:31 Whenever you see identity, that's a one, but otherwise you see a zero, okay?

00:21:37 There are other kind of alignment score as well.

00:21:40 So now let's ask, how do we formulate this?

00:21:42 And this is already close to optimization, right?

00:21:46 But how do we formulate it as optimization problem and solve it?

00:21:54 What is the decision variable?

00:21:56 What are the constraints?

00:21:57 And what is the objective function?

00:21:59 I think the objective function is a little bit clear when I say what's alignment score.

00:22:04 But how do we really think about this problem as an optimization and solve it as an optimization?

00:22:12 Any suggestions?

00:22:16 Any suggestions?

00:22:19 What is the decision variable?

00:22:31 What?

00:22:32 The number of the same.

00:22:34 The number of matches.

00:22:38 Is that more like the objective function?

00:22:44 Right?

00:22:46 So I think it's kind of, it's not like XI or XJ we just have defining the diet problem.

00:22:56 That is okay.

00:22:56 It's a little bit more abstract.

00:22:58 But right now you can think of it as like determining, you know, when you align and when you insert a gap or something like that.

00:23:08 So we'll make it more clear in the next slide, okay?

00:23:11 So the decision variables, okay?

00:23:16 So the decision variable is, you know, if you fix one character in the first, let's call it a template sequence,

00:23:27 right?

00:23:27 So if you're using a match or a gap, right?

00:23:32 Then you have a decision, right?

00:23:33 To decide whether you will have a match or a mismatch or a gap, right?

00:23:38 So this decision variable is either your, you know, for each template character, you are introducing a match or mismatch.

00:23:49 And then this mismatch, this is actually having some biological context, okay?

00:23:56 So if it's a mismatch, sometimes it's like in this black cases, right?

00:24:02 So if you have a to q, this is called a substitution, right?

00:24:08 Two letters, a substituted to q.

00:24:11 That's called substitution, right?

00:24:13 Before and after, that's a substitution.

00:24:17 So c is replacing d.

00:24:21 But sometimes you could have a insertion or you could have a deletion.

00:24:25 For instance, in this case, right?

00:24:27 If you look at these two, as I said, this could be regarded as homolog sequences across two species, right?

00:24:36 So in species one, you have ABD, but across in the course of evolution, there's a new

00:24:46 amino acid or nucleotide being inserted into that sequence, it becomes ABCD.

00:24:52 So if you were to align ABD and ABCD,

00:24:57 you would do what?

00:24:58 ABGAPD versus ABCD, isn't it?

00:25:02 So in this case, the second sequence compared to the first sequence is like inserted,

00:25:09 right, an additional amino acid.

00:25:11 But sometimes it could be deleted as well.

00:25:13 For instance, ABD, right, changed to AB in a new species, for instance, right?

00:25:20 So in this case, alignment is ABD versus ABGAP.

00:25:25 So the second sequence, ABGAP relative to the first one, ABD, at that position is

00:25:32 taking a decision variable of deletion.

00:25:35 So you're basically deciding when you do a match, when you do a mismatch, substitution or insertion or deletion.

00:25:43 At every position, you are making that choice.

00:25:45 So that's your decision variable, okay?

00:25:47 And I think there are constraints as well, right?

00:25:54 Because no matter how you align, you cannot change the order of the sequence, isn't it?

00:26:01 Right?

00:26:01 You see, in my definition of the decision variables, I either match or mismatch.

00:26:06 Or the way I mismatch, I never define something that's not allowed by evolution, right?

00:26:12 Or the definition of the problem.

00:26:16 And then there's objective function.

00:26:19 I said before that, you know, depending on whether you are aligning two sequences or multiple sequences,

00:26:26 though you have to define what's the score for a pairwise alignment and what's the score for multiple alignment, right?

00:26:35 That's one difference.

00:26:36 If we focus on the pairwise alignment, there's a local versus global.

00:26:41 In the case of local, you're fine to find some local motifs that's shared across the two sequences.

00:26:49 And you are not penalizing these red aligned to gap or gap aligned to blue that much,

00:26:55 because you are looking for local motifs shared across sequences.

00:27:00 But sometimes you are looking at the global similarity among two sequences, right?

00:27:06 For instance, two homolog proteins across different species.

00:27:10 In these cases, whenever you see alignment, you're happy about it,

00:27:13 but you do have to consider the misaligned or mismatched portion.

00:27:18 Okay?

00:27:19 And then how to construct the objective function is also something that we have to think.

00:27:28 In this case, actually, it's not that apparent what's objective function.

00:27:34 I use the one approach, a very simple approach.

00:27:37 Whenever there is a match, it's one.

00:27:39 Whenever there's a mismatch, that's zero.

00:27:42 But you have to ask yourself whether that's optimal at all, right?

00:27:48 So if you have no idea how to find the objective function,

00:27:52 you don't know what score to assign to a match versus a substitution versus insertion versus deletion,

00:27:59 what would you do?

00:28:04 It's either principle or data, right?

00:28:07 So in the early days of constructing such objective function, they actually learned from data.

00:28:14 We can talk about it as well, okay?

00:28:17 And of course, as the alignment algorithms evolve, these objective function may be changed as well,

00:28:24 because nowadays people are using neural networks to align sequences, and then correspondingly,

00:28:29 you know, whether the same objective functions are still optimal, that's not necessarily the case.

00:28:37 So now we're asking, why are we interested in finding the algorithm?

00:28:41 You told me that for problems like linear programming, I can use simplex, which is not polynomial.

00:28:47 I can have interior point algorithms, that's polynomial, I just use some softwares.

00:28:51 For more general nonlinear programming, but still convex optimization, I can still hope to find some

00:29:02 very easy local minimization algorithms, and I have the guarantee that the local minimum

00:29:07 is also the global minimum for convex optimization. So I'm also done with that, right?

00:29:13 Okay. Then there are non-convex optimization problems.

00:29:17 Similarly, I don't have any guarantee of the global optimum anyway.

00:29:21 So why do I need an algorithm in general? So what is an algorithm?

00:29:26 Algorithm is basically, you know, a set of procedures we give to computers so that they find

00:29:32 to solve some problems for us, in this case, finding the optimum, right?

00:29:36 So what do we want from the, this is actually the background knowledge,

00:29:43 finding the objective function. So I put it in the squared

00:29:46 bracket here, so if you're interested, we can look into, you can look into that.

00:29:52 So now let's talk about the optimization algorithms. So I said, why do we care about

00:29:58 the optimization algorithms? And, you know, what do we want out of the optimization algorithms, right?

00:30:04 So there are three things that we care about from an, from an algorithm, or optimization algorithm

00:30:11 specifically. So the first one is the accuracy. The second one is efficiency, and the last one is robustness.

00:30:20 In each case, there is a theoretical context, and there is a practical implication.

00:30:30 So there are both of them, okay? So I give you one example, right? Accuracy, right? So the accuracy is basically asking you whether

00:30:41 the algorithm returned solution is close to the optimum you are pursuing, right? So that's the accuracy, right?

00:30:49 And why do we care about the accuracy? Of course, you know, you care about the accuracy, but why do you want to look at some theoretical concept?

00:31:00 In this case, convergence, I'm going to talk about it when we are talking about numerical optimization, okay?

00:31:06 Why do we care about the theory, right? So in this case, there's a practical limit that we have, you know, the computing power.

00:31:15 So knowing that some algorithm converged to the global optimum, but in reality due to the limitation of computing power,

00:31:26 we cannot get there, versus having no idea about whether theoretically this algorithm converged to the optimum,

00:31:36 and also facing the limited computing power, right? Which one would you prefer?

00:31:45 So this theory are basically giving you what? Giving you a guideline and a sanity check, telling you that if,

00:31:52 you know, the convergence is basically saying that, you know, if, right, we have enough computing power,

00:31:58 if you keep running this algorithm, it will get there. If you keep running it, it will get there, okay?

00:32:05 And of course, the practical solution is limited by your computing power, right?

00:32:11 So you have to be able to do that, okay? But some other cases, if you don't have such guarantee, then you have to count on luck, isn't it?

00:32:20 Because you don't know whether it performed well or not well. It's, you know, you have to blindly try it, and this time it works, that time it doesn't work.

00:32:28 Okay.

00:32:29 And then, so this is about the accuracy. So we wanted an accurate solution. But remember,

00:32:38 we are also limited by the computing power. So you have the CPU, you have the memory requirement.

00:32:44 So we have to consider the efficiency, how much resource it needs to reach the same level of accuracy, okay?

00:32:51 So theoretically, the concept of interest is called complexity. This complexity includes time complexity and space complexity, right?

00:33:02 So, for instance, time complexity is, you know, we usually consider the worst case scenario. Remember, I was asking you,

00:33:10 in the case of enumerating all possible extreme points of linear programming problem,

00:33:17 and in the worst case, you will find the global optimum as the last point, right? So in the worst case,

00:33:25 how many solutions do you have to go through? So that's using the big O notation, right?

00:33:32 So it's in, you know, you can also roughly think of it as like in the order of, right? So this is like the big O notation, right?

00:33:39 So a more difficult case that people are studying the theoretical computer science is,

00:33:46 what's the average case complexity? That's a little bit more difficult, okay? Not just a little bit more.

00:33:54 So let's talk about the big O notation for time complexity. For instance, a polynomial time algorithm,

00:34:00 let's say the input is size n, and the worst case running time is in the order of n to the power of k for some constant k.

00:34:09 So this is a polynomial time algorithm because the time complexity is, you know, polynomial in the size of the problem, okay?

00:34:22 Compared to an exponential time algorithm, I think the polynomial time algorithm is much more favorable

00:34:29 when your input size is large, right? But of course, if your problem is very small sized,

00:34:36 you could have a polynomial time algorithm that beats some, I'm sorry, you could have some exponential

00:34:41 time algorithm beating some polynomial time algorithm if the problem is very small size, okay? But, you know,

00:34:47 if n goes to very large numbers, then, you know, quickly exponential time algorithms are not favorable anymore,

00:34:56 right? At all. And another complexity, so if you think about the, you know, time complexity,

00:35:06 is for the CPU resource, right? There are not a complexity that's a space complexity, right? That's,

00:35:13 that's like the amount of memory you need, right? So how much storage you need for your algorithm, right?

00:35:20 So we'll talk about both complexities and including the convergence and the convergence rate when we talk

00:35:29 about a numerical optimization next week, okay? And the practical measure for the theoretical time complexity

00:35:42 is the running time, okay? In reality, you know, this running time is limited by the computing

00:35:50 power. So these theories, theoretical concepts are really giving you a sanity check for your algorithm

00:35:58 before you have to run it. Do you see what I mean? Because, of course, you can try your algorithm on

00:36:04 high performance computing and run it long enough and try to figure out whether it works accurately or

00:36:10 efficiently or not. But you can only blindly, you know, try it and guess. And you don't know it's

00:36:19 limited by the resources, right? You will never know about your algorithm's performance. These theoretical

00:36:26 concepts, although not exactly equal to your practical measures, for sure, but they are giving you the

00:36:33 guidelines on the practical measures. So these are why they are very important. Besides accuracy and

00:36:40 efficiency, you may also pay attention to the robustness of the solutions of this algorithm, right? Considering a lot of the

00:36:51 algorithms have to run in a stochastic environment, right? Whether it's a starting point or other kind of

00:36:59 elements of the environment. So the robustness is also very important. So if you look at the

00:37:06 chapter one, which I shared for numerical optimization, these three elements are also mentioned in that

00:37:14 chapter one overview of optimization. So now let's look at this pairwise sequence alignment, okay? And remember,

00:37:24 we'll have to look at some of these theoretical concepts so that we can have some guidelines, okay?

00:37:31 So we know the problem already, right? The objective function, the slide I skipped, if you are interested,

00:37:41 you can look into as well. That's also defined. So now, why do we need algorithms?

00:37:50 Why can we brute-forcedly just try all the possibilities? Right? Let's say we're looking at the

00:37:57 pairwise sequence alignment, we're looking at the global alignment, we're looking at the global alignment, we just try all the

00:38:03 possibilities, okay? We have two sequences whose lengths are m and m before inserting the gaps, respectively.

00:38:13 How many global alignments are there?

00:38:15 So first of all, are we all clear about the concept of the global sequence alignment, global alignment?

00:38:32 So how many alignments do you think are there when we align two sequences of length m and n?

00:38:45 I'll give you a hint. This should be...

00:38:51 So I think we are talking about how many global optimums are there, total. So we're looking at how many alignments.

00:39:02 How many ways can you align these two sequences? One of them, or multiple of them, are global optimal,

00:39:08 right? So as a hint, this should be a little bit advanced problem if you have taken 303.

00:39:18 That is random signals and systems, right? But I'm not talking about probability. But we did talk about

00:39:29 how to enumerate, yes. How to count without counting in 303, right? So Ryan was saying combination. Yeah,

00:39:36 I think you are hitting some point.

00:39:39 So I think very often it's not that we don't know

00:39:46 about the concept or we don't have the ability

00:39:51 to learn a new problem.

00:39:52 Very often it's ability to think about the problem

00:39:57 in some computational framework, which I call modeling.

00:40:01 So in this case, it's a small modeling technique

00:40:04 we need to consider.

00:40:06 So I think we understand the problem.

00:40:09 We also have learned permutation, combination,

00:40:15 all these things we have learned,

00:40:17 how to count without counting.

00:40:18 But probably we still cannot put them together, can we?

00:40:25 You're aligning these two sequences by inserting their gaps

00:40:29 whenever needed and to make their lengths the same.

00:40:33 Right now you don't have to worry about the alignment score

00:40:37 because I'm just asking you how many ways to align them.

00:40:40 Can I say m plus 1 c1 plus m plus 1 c2 plus m plus 1 c3

00:40:45 up to m plus 1 c n minus m?

00:40:49 I see.

00:40:51 So you are saying that m plus 1 choose 1 plus m plus 1 choose 2

00:40:58 and so on up to 2.

00:40:59 All the way to m plus 1 choose m minus m.

00:41:02 m minus m assuming that m is bigger than m.

00:41:06 Good.

00:41:07 So where is m plus 1 coming from?

00:41:11 Uh-huh.

00:41:12 Uh-huh.

00:41:13 If a sequence has m letters, then we have to introduce the gaps

00:41:18 of the blanks between the letters.

00:41:19 Right.

00:41:20 So for m sequence, there are m minus 1 position in between.

00:41:24 Very good.

00:41:25 And two position at the extreme.

00:41:26 So there are m plus 1 position to introduce the gaps.

00:41:30 Good.

00:41:31 So that's a very good way to think about it.

00:41:35 OK.

00:41:36 So you are saying that I can consider this as a problem

00:41:42 of introducing gaps to the sequence whenever needed.

00:41:47 Is that right?

00:41:48 So how many positions can I introduce a gap?

00:41:53 You said it's m minus 1.

00:41:55 I think it's probably m plus 1.

00:41:57 Oh, you said m plus 1.

00:41:59 Sorry.

00:42:00 So I'm going to say that.

00:42:01 I'm going to say that.

00:42:02 So I'm going to say that.

00:42:03 Oh, you said m plus 1.

00:42:04 Sorry.

00:42:05 If I.

00:42:06 Yeah.

00:42:07 Because you also consider the two n's, right?

00:42:08 Sorry.

00:42:09 So it's m plus 1, right?

00:42:11 As you correctly pointed out.

00:42:12 So I could place one gap there.

00:42:17 Right.

00:42:18 I could place two gaps there.

00:42:21 And I could place up to m minus 1.

00:42:24 If I place one gap, that's a good one.

00:42:30 That's a good one.

00:42:31 Mm-hmm.

00:42:32 I will give you a different answer.

00:42:35 I think the way we think about it is the same.

00:42:37 And we can prove whether they are equal.

00:42:40 Whether you counted something more than what I counted or vice versa.

00:42:46 I really like the way you think about the problem.

00:42:48 And I'm going to give you a hint at the end.

00:42:51 This is a problem you have seen before when you learn combination, actually.

00:42:56 Back then you were wondering why did I have to do that.

00:42:59 Now you see this is one example.

00:43:00 I'm going to give you the hint at the end, okay?

00:43:02 Okay.

00:43:03 So how to think about the problem?

00:43:04 I really like what Ryan was saying exactly, right?

00:43:07 So, you know, this is two extremes, for instance.

00:43:15 The shortest alignment is the maximum of a length maximum among m and n, whichever is longer.

00:43:21 And the longest is m plus n, right?

00:43:25 So this is just the range of the lengths for all kinds of alignments.

00:43:29 And you can think about it as a red and a blue sequences.

00:43:37 Then you could regard them as, I really like the way Ryan was saying.

00:43:44 So because the Ryan's formulation is like this.

00:43:47 If we have m, you have all of you have learned this problem.

00:43:52 Or you have m red marbles and n blue marbles, right?

00:43:59 And you want to order them in a linear order, right?

00:44:04 And these marbles, red among red or blue among blue, are not distinguishable.

00:44:10 Then how many, you know, orders can you think of, right?

00:44:16 All of you have solved that problem before, right?

00:44:20 Back then you were wondering why did I have to count the red marbles, blue marbles, right?

00:44:25 It's exactly the same problem, actually.

00:44:27 But why in that case I can think of the red marbles are indiscri...

00:44:33 indistinguishable from each other because in my case, my red marbles here,

00:44:38 I can never change their order, right?

00:44:41 I can never change their order.

00:44:43 A, G, A, T, C, A, I can never change this order.

00:44:46 So equivalently I could say that all the red marbles are fixed in their relative position.

00:44:52 So I don't regard them as distinguishable, it's equivalent.

00:44:57 Another way of thinking about it, you know, now you can convert any alignment, right?

00:45:07 Based on, into a string.

00:45:09 For instance, in this case, A, gap, nothing.

00:45:13 G, gap, and then A, A, T, T.

00:45:16 So you see that this is what I'm following.

00:45:18 I'm converting each alignment into a one linear string, okay?

00:45:22 But there is a one-to-one correspondence, actually, between this alignment and the linear string, right?

00:45:29 Depending on when you insert the gap.

00:45:32 Okay, now tell me, based on this new hint, how many, if one alignment corresponds to one linear string?

00:45:44 Right?

00:45:45 There's a one-to-one mapping.

00:45:48 Instead of asking you how many alignments are there, can I ask you how many linear strings are there?

00:45:53 How many locations are there?

00:46:21 And you have to, if you insert, or if you place the red strings or marbles there, then the rest can be blue, right?

00:46:32 Combination of n out of n plus n.

00:46:40 N plus n what?

00:46:42 Combination of n out of n plus n.

00:46:46 Correct.

00:46:47 So as Nami said, it's m plus n choose m, or m plus n choose n, the same.

00:46:58 You are basically asking, out of maximumly m plus n positions, which positions should be reserved for red?

00:47:07 Then the rest would be for blue, right?

00:47:10 And you don't care about the red letters relative order because that order never changes.

00:47:17 So the answer is m plus n choose m, or m plus n choose n.

00:47:23 So we can try to prove whether it's the same as yours, because I think your formulation sounds correct to me.

00:47:30 Okay?

00:47:31 And I'll be interested in proving whether they are equivalent.

00:47:35 Okay?

00:47:36 Very interesting.

00:47:37 I like the way you think about it.

00:47:39 So you see that in your probability or when you learn the combination, you wondered, why did I have to learn how to place red marbles and blue marbles in a sequence or in a circle?

00:47:52 Right?

00:47:53 So a lot of problems actually can be reduced into such kind of prototype problems.

00:47:59 Okay?

00:48:00 So now, we learn that when the number of global alignments of two sequences of length n and m is m plus n choose m, or m plus n choose n.

00:48:14 Okay?

00:48:15 Well, and we know what n plus n choose n is roughly equals two, right?

00:48:20 If you let m equals to n, you have two n choose n, right?

00:48:24 Then you have what?

00:48:25 Two n factorial divided by n factorial divided by n factorial, right?

00:48:30 And then if you use a formula on the engineering plaza, have you learned about the Sterling formula?

00:48:39 How you can approximate a factorial?

00:48:44 The Sterling formula?

00:48:45 No?

00:48:46 Okay, that's another homework for you.

00:48:50 Just a quick exercise for you after the lecture.

00:48:54 So if you can approximate this, you know, two n factorial divided by n factorial divided by n factorial using the Sterling's formula, I think it's on our engineering quad, right?

00:49:06 You will find that it's almost, you know, it's approximately exponential in the size of the problem.

00:49:14 Okay?

00:49:15 Okay?

00:49:16 So the complexity of the enumeration for these two sequences of size n is exactly what I'm going to put here.

00:49:23 Okay?

00:49:24 I'm going to show you the solution next time when we meet, but I hope you do it by yourself a little bit.

00:49:29 Okay?

00:49:30 So in other words, this is a brute force algorithm.

00:49:35 It's going to work.

00:49:36 It's going to be accurate, right?

00:49:37 But the efficiency is not good, right?

00:49:40 We are talking about the time complexity being exponential you're going to find in the size of n.

00:49:46 And if we are talking about two very small proteins whose lengths are 100 or two very short DNA segments, right?

00:49:57 Right?

00:49:58 And in this case, you have 10 to 59 combinations.

00:50:03 Okay?

00:50:04 In comparison, the universe age is around 10 to 17.

00:50:09 So if you were born ever since the Big Bang, and every second you can check one alignment, you would be still checking.

00:50:16 Okay?

00:50:17 And this is just a really small one.

00:50:23 So this shows us that why we need algorithms.

00:50:27 You know, you need accuracy, you need efficiency, you need robustness.

00:50:30 Especially in this case, we need this time complexity really badly, right?

00:50:35 Because the brute force algorithm is exponential in m or n.

00:50:41 And we cannot afford doing that.

00:50:42 You can try to keep building much more powerful hardware.

00:50:48 But in this case, I'd suggest you first improve your software, right?

00:50:53 So we're going to learn that actually, you can reduce the time complexity from the big O in exponential of n to big O n squared.

00:51:04 Which is a polynomial time algorithm.

00:51:06 It's only square in n, okay?

00:51:08 Think about n equal to 100.

00:51:11 That's just 10 to 4.

00:51:13 Compare 10 to 59 versus 10 to 4.

00:51:15 That's a huge improvement, right?

00:51:18 So we're going to talk about this Needleman-Wunsch algorithm, which is for the global alignment, okay?

00:51:23 Okay, so now that we know what's the need, okay, how can we solve this problem smartly?

00:51:30 So there are a few insights that we can think of, okay?

00:51:35 First of all, the scores are additive.

00:51:40 Okay, let's look at these two examples, right?

00:51:44 So let's look at these three examples, right?

00:51:46 So let's say you decide to align these two sequences in this way, right?

00:51:51 And then let's say that I decide to split each sequence into two substrings, right?

00:52:01 So at these locations, i and j, right?

00:52:06 Okay?

00:52:07 And then let me ask, you know, let me ask, if I fix this split, right?

00:52:16 Where is the best alignment?

00:52:19 The best alignment means the s1 and s2, okay?

00:52:23 But if I split s1 and s2 at the given position, i and j, then the best alignment has to be the best alignment of these two individual substrings.

00:52:36 If I, you know, if I fix where I split.

00:52:41 In other words, acg needs to be aligned to tagtg, and the rest should be aligned to, you know, the second substrings optimally as well.

00:52:52 Because the reason is the objective function is additive, okay?

00:52:58 When you align these two substrings in this way, if neither of them or one of them is not optimized, the resulting alignment score for the whole string being the sum of these two alignments wouldn't be maximized either.

00:53:17 Okay?

00:53:18 So the score is additive.

00:53:20 So that's one thing to keep in mind that also tells you that, oh, I can actually compute the best alignment recursively, right?

00:53:32 Right?

00:53:33 Because I can consider, for instance, finding the best alignment of the first, you know, prefix, for instance, if I know this where to split, right?

00:53:41 So that's one thing to keep in mind.

00:53:45 Okay, so this is actually what motivates us to solve the problem using dynamic programming.

00:53:54 So the dynamic programming basically handles the problems that have overlapping subproblems.

00:54:00 If you don't fully understand what I mean is, you know, in this case, you could consider aligning two very long sequences, but you could also consider that it can be split into problems of, for instance, aligning these substrings, right?

00:54:17 So, and we can solve this recursively.

00:54:22 So if we know how to align these prefixes, then we can keep building this longer and longer alignment until we reach the complete strings.

00:54:33 So, in other words, we can apply this recursive strategy, okay?

00:54:38 We can find an optimum solution of each subproblem by first finding optimal solutions for its contained subproblems.

00:54:48 So you can keep, you know, you can start with the subproblem and then solve bigger and bigger problems that contain that subproblem.

00:54:56 So this is what the dynamic programming is trying to do.

00:55:01 In our case, we can do that because the score is additive.

00:55:05 It's a sum of all aligned pairs.

00:55:08 That's very important.

00:55:09 If you think about the classical dynamic programming problem, the next-packing problem, it's also because the score is additive.

00:55:17 Okay, so now let's divide and conquer, okay?

00:55:22 Let's consider, you remember, I had i and j where, you know, I split the two sequences, p and q, okay?

00:55:31 Let me call these two substrings for p position 1 to i and q from position 1 to j.

00:55:40 Let me call them two prefixes, okay?

00:55:44 Two prefixes, okay?

00:55:46 If, I'm saying if, okay, if I know what's the best way to align the two smaller prefixes, in other words, p1 through pi and q1 through qj,

00:56:00 then there are three possibilities, okay?

00:56:05 Three possibilities, okay?

00:56:08 So here, I'm boxing the assumed, already known, optimal alignment of the two smaller prefixes.

00:56:17 A to a, right?

00:56:19 That's right here, p1 through pi, right?

00:56:22 Then a, t, a, that's q1 through qj, right?

00:56:27 That's a, t, a, right?

00:56:29 So let's assume that we already know the optimal alignment.

00:56:32 That's already in the box, okay?

00:56:35 If we already know the optimal alignment, then you have to make a decision, and you have three choices for that decision, okay?

00:56:45 Either you next align a character from p and a character from q.

00:56:52 That is aligning what?

00:56:55 Pi and qj, right?

00:57:00 Right?

00:57:01 So these two prefixes, let's start from, you know, 1 through i, 1 through i minus 1, and 1 to j minus 1.

00:57:13 And then I can align this pi and qj, the last one, okay?

00:57:20 So there are three possibilities.

00:57:22 The first possibility is that the last characters of these two substrings are aligned.

00:57:28 In other words, it's a match or mismatch, okay?

00:57:32 Another possibility is that, you know, we can use the optimum alignment of p1 through pi, and q1 through qj minus 1.

00:57:44 And then the last character of sequence p is aligned to a gap of sequence i, right?

00:57:52 Why gap for sequence p?

00:57:55 Because the last character of, you know, pi is already used, right?

00:58:01 Right?

00:58:02 That's another possibility, right?

00:58:04 So in contrary to case 2, case 3 is doing something opposite, right?

00:58:09 In other words, you already had a subproblem aligned so that p1 through pi minus 1 is already aligned with q1 through qj.

00:58:21 So the last character of the prefix for q is already used.

00:58:26 And then for the next alignment, it can only give a gap aligned to the last character of pi, right?

00:58:36 So there are only these three possibilities, isn't it?

00:58:40 Right?

00:58:41 So let's try to think about it again.

00:58:45 We're asking what's the way to align p1 through pi and q1 through qj, right?

00:58:54 And let's assume that we know the optimal alignment of the smaller prefaces.

00:59:01 So then there are three kind of smaller prefix alignment you can build upon, right?

00:59:07 Right?

00:59:08 Either in this case, one through i minus 1 and one through j minus 1 is used.

00:59:13 And then in the last position, you have character to character.

00:59:17 So that's a substitution or match, right?

00:59:20 Or, you know, all of p1 through pi is used and q still has one more left.

00:59:27 So that means p1 through pi is aligned to q1 through qj minus 1.

00:59:35 Then I have to align a gap of p to qj.

00:59:42 Is that right?

00:59:43 In this case, the p1 through pi minus 1 is aligned to q1 through qj.

00:59:52 So the last character of qj is already used.

00:59:55 So I have to align a gap of q to the last character g of p, right?

01:00:02 So compared to the red or, you know, the sequence p,

01:00:08 I'm basically doing substitution, insertion, and deletion, isn't it?

01:00:16 These are the three possibilities.

01:00:18 So you have to basically decide, given the previous optimum alignment,

01:00:23 whether I do substitution, insertion, or deletion.

01:00:28 If I do insertion or deletion or substitution,

01:00:31 I'm actually assuming that the previous blocks were already optimally aligned.

01:00:38 Do you see what I mean?

01:00:39 So I can go recursively.

01:00:41 I can ask starting, you know, for instance, the complete sequence is just from p1 through pi and q1 through qj.

01:00:49 I can start with the last position.

01:00:50 I say that I have three possibilities, right?

01:00:53 And for each chance, for each scenario,

01:00:56 I'm going to have to construct the optimal alignment of their prefaces, right?

01:01:00 And the prefaces in this case is p1 through i minus 1, q1 through j minus 1, right?

01:01:07 In this case, it's p1 through pi and q1 through qj minus 1.

01:01:13 In this case, it's p1 through pi minus 1 and q1 through qj, right?

01:01:20 Okay, so that's what we figured out.

01:01:25 And now how do we make it an algorithm, right?

01:01:29 So the Niedelman-Wunsch algorithm is saying the following.

01:01:33 So given the sequence p and q, we can use a matrix M to record the optimal alignment scores of all prefaces of p and q.

01:01:46 In other words, Mij means the optimal alignment score between the prefix of p and prefix of q if the stopping point is at i and j, respectively.

01:02:01 Okay?

01:02:02 So the first i and the first j are prefaces of substrings or let's call it prefaces.

01:02:08 So that's an optimum alignment.

01:02:11 Now let's translate to what I said in words, okay, from the last slide into mathematics.

01:02:22 And let's ask what Mij equals to, okay?

01:02:26 So there are only three scenarios and Mij must be the maximum among the three scenarios, okay?

01:02:33 The three scenarios really depends on how the last alignment or, you know, the last position is aligned.

01:02:43 Either it's a substitution, it's an alignment between pi and qj, which is a single character alone, right?

01:02:50 So this score is known, right?

01:02:52 For pi and qj, which are a pair of characters, your objective function should already tell me what's s, what's the scoring, right?

01:03:00 Or we are aligning a gap from the p and the j's character of q.

01:03:07 Or we are aligning the i's position of p and the gap from q.

01:03:14 In other words, if you compare q to p, it's either substitution, insertion, and deletion, isn't it? Right?

01:03:21 And then, based on the additivity, this score of the last position's alignment should be added to the previous segment's alignment.

01:03:34 It should be the optimum alignment of the previous segment, isn't it?

01:03:39 That means the first i minus one for p aligned to the first j minus one to q, or the first i of p aligned to the first j minus one to q, right?

01:03:51 Because you have to save the last here, right?

01:03:54 Or in this case, the first i minus one of p aligned to first j of q.

01:03:59 And remember, it has to be optimum as well, right?

01:04:05 Isn't that beautiful?

01:04:07 It's divide and conquer, and so by branching off these three scenarios, I'm using divide and conquer.

01:04:16 By using this capital M here, I'm using this recursive strategy, right?

01:04:20 So in this way, you see that I can actually recursively express M i j, right?

01:04:28 So this means for this matrix, I can start with some short alignments and then gradually build it, right?

01:04:36 So we can use dynamic programming.

01:04:39 In this case, it's instantiate as a Needleman-Wunsch algorithm.

01:04:43 It is an exact algorithm, meaning that it's guaranteed accurate.

01:04:48 It's guaranteed to give you the optimal solution.

01:04:50 But it's the order of n squared.

01:04:52 It's not the fastest, okay?

01:04:55 So now let's talk about Needleman-Wunsch algorithm.

01:05:00 So I think I already gave you the hint about the algorithm, but, you know, the core is here.

01:05:05 So you probably will emphasize, get the strengthening of the concepts in the homework.

01:05:12 So the Needleman-Wunsch algorithm is very simple.

01:05:16 You start with initializing this matrix with the borders, which are very simple substrings,

01:05:23 the smallest sub-problems you can think of.

01:05:25 Then you gradually fill the matrix that gradually give you the optimal alignment of all the prefaces until the complete strings.

01:05:34 And eventually, once you figure out the optimal score, you can trace back and find the actual, the optimum alignments. Okay?

01:05:43 So next, I will use an illustration using a very simple scoring scheme.

01:05:49 Plus one for match and minus one for any mismatch, substitution, or insertion, or deletion.

01:05:57 Okay?

01:05:58 Let's start.

01:05:59 I have two matrices.

01:06:01 P is what we've seen before.

01:06:04 It's A, G, A, T, until G.

01:06:07 And let's also call it a row matrix.

01:06:10 And Q is a column sequence, is a query sequence, for instance.

01:06:14 All right?

01:06:15 It's written as A to T.

01:06:17 Notice that I put a gap at the very beginning here for every, for either sequence P or Q. Okay?

01:06:25 And what is the optimal alignment score I want in this matrix?

01:06:31 Where is the optimal alignment score for these two strings, P and Q?

01:06:36 Huh?

01:06:38 Which corner?

01:06:43 Right.

01:06:44 Right here, isn't it?

01:06:48 This is Mij, where i is maximum and j is maximum.

01:06:53 Right?

01:06:54 So that's the optimal score for the two complete strings or sequences, P and Q.

01:07:00 So I have to somehow get here.

01:07:02 And I have, I can start from the borders, which is very easy.

01:07:05 For instance, here, gap aligned to gap is zero.

01:07:08 Gap aligned to A is minus one.

01:07:10 Gap aligned to, and then you keep, you know, then you may get confused.

01:07:16 Why I'm getting minus two, minus three?

01:07:18 Because you keep, you keep using gap.

01:07:21 Because here, for instance, you know, gap aligned to gap is zero.

01:07:25 Then gap aligned to A is minus one.

01:07:28 And then the next character of Q, which is T, is again aligned to a gap.

01:07:34 It's like A gap aligned to, A gap and T gap.

01:07:38 So AT aligned to gap, gap.

01:07:40 So you have two gaps.

01:07:41 So that's minus two.

01:07:42 Then you keep going this direction.

01:07:45 You will subtract by minus one because you keep inserting gaps.

01:07:51 Is that right?

01:07:52 So in other words, you keep inserting gaps.

01:07:55 Right?

01:07:56 So in other words, Q versus P, right?

01:07:59 P is always giving a gap.

01:08:01 And Q is keep adding these characters.

01:08:04 So Q relative to P is doing what?

01:08:06 Insertion.

01:08:07 Insertion.

01:08:08 You keep inserting more and more.

01:08:10 So you just get the score of minus one, minus two, minus three, all the way until minus seven.

01:08:14 Right?

01:08:15 Because you keep having these gaps aligned to the characters.

01:08:19 And similarly here.

01:08:20 Okay?

01:08:21 The difference is that now the characters of P is aligned to the gaps of Q.

01:08:28 So Q relative to P is deletion.

01:08:31 Right?

01:08:32 Right?

01:08:33 So here you have insertion.

01:08:34 You have the deletion.

01:08:35 Right?

01:08:36 Okay.

01:08:37 In other words, if you now we need to somehow move to here.

01:08:42 Right?

01:08:43 So how do we move?

01:08:45 Exactly following what's defined here.

01:08:48 Okay?

01:08:49 What about substitution?

01:08:52 So we use the minus one for substitution and gap.

01:08:57 Yeah.

01:08:58 To simplify the illustration.

01:09:01 So now, let's see.

01:09:04 First, we need to figure out what's the value here.

01:09:09 Right?

01:09:10 [Uncertain recognition] First, we need to fill out some coal kinds of nitrogen outings of either cost or rescue including