In this video we'll cover a second 
problem to whet your appetite for things 
to come, namely the problem of sequence 
alignment. 
So this is a fundamental problem in 
computational genomics. 
If you take a class on the subject it's 
very likely to occupy the very first 
couple of lectures. 
So in this problem you're given two 
strings over an alphabet and no prizes 
for guessing which is the alphabet we're 
most likely to care about. 
Typically, these strings represent 
portions of one or more genomes. 
And just as a toy running example you can 
just imagine that the two strings were 
given are A, G, G, G, C, T and A, 
G, G, C, A. 
Know that the two input strings do not 
necessarily need to be of the same 
length. 
And informally speaking, the goal of this 
sequence alignment problem is to figure 
out how similar the two input strings 
are. 
Obviously, I haven't told you what I mean 
by two strings being similar. 
That's something we'll develop over the 
next couple of slides. 
Why might you want to solve this problem? 
Well, there's actually a lot of reasons. 
Let me just give you two of many 
examples. 
What will be the conjecture or the 
function of regions of a genome that you 
don't understand, 
lets say the human genome, 
from similar regions that exist in 
genomes that you do understand or at 
least understand better, 
say the mouse genome. 
If you see a string that has a known 
function in the well understood genome 
and you see something similar in the 
poorly understood genome, you might 
conjecture it has the same or similar 
function. 
A totally different reason you might want 
to compare the genomes of two different 
species, is to figure out whether one 
evolved directly from the other and when. 
A second totally different reason you 
might want to compare the genomes of two 
different species is to understand their 
evolutionary relationship. 
So for example, maybe you have three 
species A, B, and C, and you're wondering 
whether B evolved from A and then C 
evolved from B, or whether B and C 
evolved independently from a common 
ancestor, A. And you might then take 
genome similarity as a measure of 
proximity in the evolutionary tree. 
So having motivated the informal version 
of the problem, let's work toward making 
it more formal. 
In particular, I owe you a discussion of 
what I mean by two strings being similar. 
So to develop intuition for this, let's 
revisit the two strings that we 
introduced on the previous slide A, G, G, 
G, C, T, and A, 
G, G, C, A. 
Now, 
if we just sort of eyeball these two 
strings, I mean clearly they're not the 
same string. 
But, we somehow feel like they're more 
similar than they are different. 
So, where does that intuition come from? 
Well, one way to make it more precise is 
to notice that these two strings can be 
nicely aligned in the following sense. 
Lets write down the longer string, A, 
G, G, G, C, T. 
And, I'm going to write the shorter 
string under it, and I'll insert a gap, a 
space to make the two strings have the 
same length. 
I'm going to put the space where there 
seems to be quote unquote a missing G. 
And then, what sense is this a nice 
alignment, well, it's clearly not 
perfect. 
We don't' get a character, by character 
match of the two strings, but there's 
only two minor flaws. 
So on the one hand, we did have to insert 
a gap and we do have to suffer one 
mismatch in the final column. 
So this institution motivates defining 
similarity between two strings with 
respect to their highest quality 
alignment, their nicest alignment. 
So we're getting closer to a formal 
problem statement, but it's still 
somewhat underdetermined. 
Specifically, we need to make precise why 
we might compare, why we might prefer one 
alignment over another. 
For example, is it better to have three 
gaps and no mismatches or is it better to 
have one gap and one mismatch? 
So if in this video, we're effectively 
going to punt on this question. We're 
going to assume this problem's already 
been solved experimentally, that it's 
known and provided this part of the input 
which is more costly, gaps and various 
types of mismatches. 
So here, then, is the formal problem 
statement. 
So, in addition to the two strings over 
A, 
C, G, T, we are provided as part of the 
input, a non-negative number indicating 
the cost we incurred in alignment for 
each gap that we insert. 
Similarly, for each possible mismatch of 
two characters, 
like, for example, mismatching an A and 
T. 
We're given as part of the input a 
corresponding penalty. 
Given this input, the responsibility of a 
sequence alignment algorithm is to output 
the alignment that minimizes the sum of 
the penalties. 
Another way to think of this output, the 
minimum penalty allignment is, we're 
trying to find in affect the minimum cost 
explanation for how one of these strings 
would've turned into the other. 
So we can think of a gap as sort of 
undoing a deletion that occurred some 
time in the past and we can think of a 
mismatch as representing a mutation. 
So this minimum possible total penalty, 
that is these values of this optimal 
alignment is famous and fundamental 
enough to have its own name namely the 
Needleman-Wunsch score. 
So this quantity is named after the two 
authors that proposed efficient algorithm 
for computing of the optimal alignment. 
that appeared way back in 1970, in the 
Journal of Molecular Biology. 
And now, at last, we have a formal 
definition of what it means for two 
strings to be similar. 
It means they have a small NW score, a 
score close to 0. 
So for example, if you have, if you have 
a database with a whole bunch of genome 
fragments, 
according to this, you're going to define 
the most similar fragments to be those 
with the smallest NW score. 
So, to bring the discussion back squarely 
into the land of algorithms, let me point 
out that this definition of genome sum, 
similarity is intrinsically algorithmic. 
This definition would be totally useless, 
unless there existed in efficient 
algorithm that given two strings and its 
penalties computes the best alignment 
between those two strings. 
If you couldn't compute the score, you 
would never use it as a measure of 
similarity. 
So this observation puts us under a lot 
of pressure to devise an efficient 
algorithm for finding the best alignment. 
So how are we going to do that? 
Well, we can always fall back to 
brute-force search, where we iterate over 
all of the conceivable alignments of the 
two strings, compute the total penalty of 
each of those alignments, and remember 
the best one. 
Clearly, correctness is not going to be 
an issue for brute-force search. 
It's correct essentially by definition. 
The issue is how long does it take? So 
let's ask a simpler question. 
Let's just think about, how many 
different alignments there are? 
How many possibilities do we have to try? 
So if [INAUDIBLE] let's imagine, I gave 
you two strings of length 500, which is a 
knot of a reasonable length. 
Which of the following english phrases 
best describes the number of 
possibilities, 
the number of alignments given to strings 
with 500 characters each? 
So I realize this is sort of a cheeky 
question, 
but I hope you can gather that what I was 
looking for was part D. 
So you know? 
So, how big are each of these quantities, 
anyways? 
Well, in a, in a typical version of this 
class, you might have about 50,000 
students enrolled or so. 
So that's somewhere between 10^44 and 
10^5.5. 
The number of people on earth is roughly 
7,000.000.000. 
So that's somewhere between 10^9 and 
10^10/10. 
The most common estimate I see for the 
number of atoms in the known universe is 
10^80. 
And believe it or not, the number of 
possible alignments of two strings of 
length 500 is even bigger than that. 
So I'll leave it for you to convince 
yourself that the number of possibilities 
is at least two raised to the 500. 
the real number is actually noticeably 
bigger than that. and because 10 is at 
most 2^4, we can lower bound this number 
by 10^125 quite a bit bigger than the 
number of atoms in the universe. 
And the point of course, is just that 
it's utterly absurd to envision 
implementing brute-force search even at a 
scale of a few hundred characters. 
And you know, forgetting about these sort 
of astronomical, if you will, comparisons 
even if you had string lengths much 
smaller, say in the you know, a dozen or 
two, you'd never ever run brute-force or 
this is not going to work. And of course, 
notice this is not the kind of problem 
that's [INAUDIBLE] This just doesn't go 
away if you wait a little while for 
Moore's law to help you. 
This is a fundamental limitation. It 
says, 
you are never going to compute alignments 
of the strings that you care about, 
unless you have a fast, 
clever algorithm. 
. 
I'm happy to report that you will indeed 
learn such a fast and clever algorithm 
later on in this course. 
Even better, it's just going to be a 
straightforward instantiation of a much 
more general algorithm design paradigm. 
That of dynamic programming.