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.
