The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).
Optimal Substructure
Loading...
Del curso dictado por Stanford University
Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
559 calificaciones
De la lección
Week 4
Advanced dynamic programming: the knapsack problem, sequence alignment, and optimal binary search trees.
Conoce a los instructores
Tim RoughgardenProfessor
Computer Science
At the beginning of the course, we talked about the sequence alignment problem,
a problem which is fundamental to modern computational genomics.
And we talked about the need for an efficient algorithm for solving that
problem, for finding the best alignment of two strings.
I'm pleased to report that at this point we're well prepared to give such an
algorithm. Indeed, such an efficient solution will
readily fall out of the dynamic programming recipe that we now have quite
a bit of practice with. So let me briefly jog your memory about
the sequence alignment problem. So the goal here is to compute a
similarity measure between strings, a similarity measure defined as the total
penalty of the best alignment, also known as the Needleman-Wunsch score.
So for example. if you've given as input the strings A G,
G, G C T at A G, G C A, a natural candidate alignment would be to stack
them on top of the other, inserting a gap in the shortest string after the two Gs,
that some sense represent the missing G. This is a pretty good alignment that
suffers from merely two flaws. So first of all, we did resort to adding
a gap in the second string. Second of all, there is a mismatch in the
final column. The A and the T get mismatched.
In general we evaluate the alignment by summing up the penalties of all the flaws
and the sum penalty per gap and the sum penalty per mismatch.
So, a bit more precisely, as input in this computational problem, we're given
two strings. I'm going to call them capital X and
capital Y. I'm going to use little x and little y to
denote the individual characters of these strings.
Let's say the first string capital X has linked M and the second string Y has
linked N. In addition to the two input strings we
assume we're given as input the values for the various types of penalties.
So that we know exactly how much it costs each time we insert a gap.
And for each possible mismatch, we need to know exactly what's the cost of that
mismatch. In principle you could be given a penalty
for matching a letter with itself, but typically that's going to be a penalty of
zero. The space of feasible solutions are just
the ways of inserting gaps into the two strings so that the results have equal
length. I should emphasize that you're allowed to
insert gaps into both of the strings. In the example, we only inserted into one
of the two strings, but in general, you might have an input
where one string is seven characters longer than the other,
and it might turn out that in the optimal alignment, the best thing to do is insert
three gaps at various places in the longer string,
and ten gaps at various places into the shorter string.
And the goal, of course is just to compute amongst all of the exponentially
many alignments, the one that minimizes the total penalty, where total penalty is
just the sum of individual penalties for the inserted gaps and the various
mismatches. So let's not be unduly intimidated by how
fundamental this problem is, and let's just apply the dynamic recipe,
the programing recipe that we have been using all along.
Now remember, the really key insight in any dynamic programing solution is
figuring out what's the right collection of sub problems.
And if you're feeling like your up to the black belt level in dynamic programing,
you might just want to try to guess what are the right collection of sub problems
for sequence alignment? But I don't expect you to be able to do
that at this point. And so, as usual we're going to derive
the correct collection of sub-problems. And we're going to do it by reasoning
about the structure of an optimal solution,
narrowing it down to a small number of candidates composed in various ways from
solutions to smaller sub-problems. Once we've figured out the small number
of possibilities for what the optimal solution could look like in terms of
solutions to smaller sub problems, we'll be able to drive a recurrence which in
effect just does brute force search through the small number of candidates.
And from the recurrence we'll be able to back out.
We'll be able to reverse engineer what are the various sub problems that we
actually care about and that we have to solve.
So let's do a thought experiment. What does the optimal solution have to
look like? And again, remember, this is exactly what
it is that we're trying to compute but that's not going to stop us from
reasoning about it. If someone handed to us on a silver
platter the optimal solution, what would it have to look like?
So consider any old pair of strings, capital X and capital Y, and an optimal
alignment of them. Let's visualize this optimal alignment as
follows. Let's write down the string X plus
whatever gaps get inserted into it on top, and right beneath it we'll write
down the string Y, with whatever gaps are inserted into it.
These two things have exactly the same length.
So to figure out the various cases of the structure for this optimal solution,
let's reason by analogy with the problems we've already solved.
So back when we were looking at independent sets of line graphs, our case
analysis was well, either the final vertex, the rightmost vertex of the path,
is in the optimal solution or it's not. In the knapsack problem, we said well
either the last item is in the optimal solution or it's not.
So we always looked at sort of the last part of the optimal solution, in some
sense the rightmost position. And happily, staring at this alignment,
we see we can once again focus just on the action in the right most, in the
final position. So now I have a question for you.
So in the independent set problem, there were two cases.
The last vertex was either in the optimal solution or it's not.
In the knapsack problem, there were also two cases, the final item was either in
the optimal solution or it's not. So my question for you is, in the
sequence alignment problem: when we focus on what's going on in the final position
of the optimal alignment, how many relevant cases do we have to study?
So the answer I'm looking for is B, three relevant possiblities for the contents of
the final position. Let me explain my reasoning, let's start
with the upper parts of the final position.
observe that if that's a character of the string capital X, it can only be the very
last character. It can only be little X sub N.
That's because that's where this string ends.
Now we don't know that little X sub N is in the final position, there might be a
gap. Similarly, in the bottom part of this
final position, there's two possibilities.
There's a gap, or, if it's a character of y, it has to
be the final character, little y, sub n. So that one seems to suggest four
possibilities, two options for the top,
two options for the bottom. But the hint of talking about relevant
possibilities is that it's totally pointless to have two, a gap in both the
top and the bottom. Why?
Well the penalty for gaps is non-negative, so if we just deleted both
of those gaps we'd get an even better alignment of X and Y.
And in studying an optimal solution, we can therefore assume we never have two
gaps in a common position. So that leaves exactly three cases.
It could be there's no gaps at all, that in fact this alignment matches the
character, little x of m, with little y sub n.
Or it could match the final character of capital X, with a gap.
Or it could match the final character of capital Y with a gap.
So the hope behind this case analysis is that we're going to be able to boil down
the possibilities for the optimal solution to merely three candidates,
one candidate for each of the three possibilities for the contents of the
final position. That would be analogous to what we did in
both the independent set and knapsack problems, where we boiled the optimal
solution down to just one of two candidates, corresponding to whether
either the final vertex or the final item, as the case may be, was in the
optimal solution. Another way of thinking about this is
we'd like to make precise the idea that if we just knew what was going on in the
final position, if only a little birdy would tell us which of the three cases
that we're in, then we'd be done by just solving the some smaller sub-problem
recursively. So let's now state for each of the three
possible scenarios for the final position,
what is the corresponding candidate for the optimal solution, the way in which,
it must necessary be composed with an optimal solution to a smaller sub
problem. So who are going to be the protagonists
in our smaller sub-problem? Well, the smaller sub-problem's going to
involve everything except the stuff in the final position.
So it's going to involve the string's X and Y, possibly with one character
remaining. So let's let x prime be x, with its final
character peeled off. Y prime's going to be y, with its final
character peeled off. So let me just remind you of how I
numbered the three cases. So case one is when the final position
contains the final characters of both of the two strings, that is, when there's no
gaps. Case two is when x, little x of n gets
matched with the gap and case three is when little y of n gets matched with the
gap. Alright, so let's suppose that case one
holds. This means that the contents of the final
position, includes both of the characters little x sub m and little y sub n.
So now what we're going to do is we want to look at a smaller sub problem.
And we want to look at the sub problem induced by the contents of all of the
rest of the positions. We're going to call that the induced
alignment. Since we started with an alignment, two
things that had to equal length, and we peeled off the final position of both, we
have another thing that has equal link so we're justified in calling it an
alignment. Now what is it an alignment of?
Well if we're in case one, that means what's missing from the induced alignment
are the final characters. little X of M and little Y's of N,
which means the induced alignment is a bona fide alignment of X prime and Y
prime. And certainly, what we're hoping is true,
is that the induced alignment is in fact, an optimal alignment of these smaller
strings x prime and y prime. This would say that when we're in case
one, the optimal solution to the original problem is built up in a simple way from
an optimal solution to a smaller sub problem.
We're of course hoping that something analogous happens in cases two and three.
The only change is going to be that the protagonists of the sub-problem will be a
little bit different. In case two, the thing which is missing
from the induced alignment is the final character of x.
So, it's going to be the induced alignment of x prime and y.
Similarly, in case three, the induced alignment is going to be an alignment of
x and y prime. So, this is an insertion, this is a
claim, it's not completely obvious, though the proof isn't hard, as I will
show you on the next slide. But assuming for the moment that this
assertion is true, it fulfills the hope we had earlier.
It says that indeed, the optimal solution can only be one of three candidates, that
one for each of the possibilities for the contents of the final position.
Alternatively it says, that if we only knew which of the three cases we were in,
we'd be done, we can recurse, we could look up a solution to a smaller sub
problem and we could extend it in an easy way to a optimal solution for the
original problem. So lets now move onto the proof of this
assertion. Why is it true that an optimal solution
must be built up from an optimal solution to the relevant smaller sub-problem?
Well all of the cases are pretty much the same argument so I'm just going to do
case one, the other cases are basically the same.
I invite you to fill in the details. So it's going to be the same type of
simple proof by contradiction that we used earlier, when reasoning about the
structure of optimal solutions for the independent set in knapsack problems.
We're going to assume the contrary, we're going to assume that the induced solution
to the smaller subproblem is not optimal, and from the fact that there is a better
solution for the subproblem, we will extract a better solution for the
original problem, contradicting the purported optimality of the solution that
we started with. So when we're dealing with case one, the
induced alignment is of the strings X prime and Y prime, X and Y with the final
character peeled off. And so for the contradiction, let's
assume that this induced alignment, it has some penalty, say capital P. Let's
assume it's not actually an optimal alignment of X prime and Y prime.
That is, suppose if we started from scratch we'd come up with some superior
alignment of X prime and Y prime, with total penalty P star, strictly smaller
than P. But if that were the case, it would be a
simple matter to lift this purportedly better alignment of x prime and y prime
to an alignment of the original strings x and y.
Namely we just reuse the exact same alignment of x prime and y prime, and
then in the final position, we just match x m with y n.
So what is the total penalty of this extended alignment of all of x and y?
Well, it's just the penalty incurred in everything but the final position, and
that's just the old penalty p star, plus the new penalty incurred in the final
position. And that's just the penalty corresponding
to the match of the characters x m and y n.
P star being less than p, of course p star plus alpha x m y n is
less than p plus alpha x m y n. But this second term is simply the total
penalty incurred by our original alignment of X and Y, right?
That alignment incurred penalty capital P, just in the induced alignment of X
prime Y prime, and it's total penalty was just that plus the penalty in the final
position, which is this alpha xn, yn. But that furnishes the contradiction that
we suppose that we started with an optimal alignment of X and Y,
yet here is a better one. So with that contradiction, it completes
the proof of the optimal substructure claim.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
