0:03
We discussed how to build and query a k-mer index, an index that's built by
taking all the k-mers of the text T and adding them to a data structure that maps
each k-mer to a list of all the offsets where it occurred in the text.
So this kind of data structure is called a multimap.
It's a map because it associates keys, k-mers,
in this case with values, offsets in the genome.
And it's a multimap because a k-mer may be associated with many different offsets
in the genome, right?
A k-mer could occur many places within the genome, within the text.
So what kind of data structures can we use to implement a multimap?
So we'll discuss two of them here.
The first one is based on ordering, like the index of a book, and
the second one is based on grouping, like the aisles of a grocery store.
So let's talk about the first data structure, which is based on ordering.
So here at the top of this slide, I have a key-value pair.
The key is a 3-mer from the text T.
It's the very first 3-mer.
And the value is the offset where that 3-mer occurs.
So we make a key-value pair for every 3-mer at every offset within T.
1:28
So now, this is our index data structure.
It's simply a list of 3-mer offset pairs ordered alphabetically by 3-mer.
So now how do we query this index?
Say we have a pattern P from which we extract a 3-mer, and
we'd like to query the index with this 3-mer.
And the way we're going to do this is with something called binary search.
1:51
So, what is binary search?
So, going back to our index analogy for
a moment, let's say we're looking up a term in this index.
We're looking up the term memory.
And, so we flip to the exact middle of the index and we look in the middle.
And we find the key term that's there, and
let's say the term directly in the middle of the index is light.
So light comes alphabetically before memory, so we know that we can completely
ignore the first half of the index, up to and including the term light.
So memory must be in the second half, so then what do we do next?
Well we do the same thing but just for the second half of the index.
So in this way we can keep going iteratively throwing away half the index
each time for each iteration.
And eventually we can hone in on exactly the term that we are looking for.
So this is called binary search.
So let's see an example using our index.
3:11
So we can ignore in the index, every entry up to and
including GTG, and we've effectively divided the problem in half.
And each time we divide the problem in half in this way,
we call this a bisection.
3:56
So that match corresponds to an index hit.
We wanted to find offsets where TGG occurs.
We've now found the first one in the index, and it occurs at offset 7.
So, the total number of bisections that we need to perform
in order to find our key in the index is approximately
equal to the logarithm base 2 of the number of keys in the index.
Why the logarithm base two?
Well, because for each of our bisections,
we're repeatedly dividing the problem in two.
So we'll implement this idea and some related ideas in Python later.
But before we move on, let me make a final point, which is that Python actually
provides a set of functions related to binary search that are useful for us here.
So these functions are all in a Python module that's called bisect.
4:46
And a Python module if you haven't encountered it before is just a collection
of related Python functions and classes.
And this module is about binary search.
So one function in this module is called bisect_left and
this function takes two parameters.
The first parameter a is a list that's already sorted.
It's already ordered in ascending order.
5:11
So if this is a list of strings then the strings should already be in
alphabetical order.
Or if this is a list of integers then they should be in ascending order.
And the second parameter x is an item and the function returns the offset where
the item x can be inserted into the list a while maintaining the order of the list.
So it's the leftmost position where x can be inserted in a such that
a is still in order after that insertion occurs.
So, bisect left is a useful function to us.
In this example we call bisect left with the parameter a,
which is this list up here.
And then the argument 2 and so bisect left is going to return the left
most index where we can insert 2 into this list such that the list is still in order.
And that's offset one, right here, so if we wanted to insert 2 into this list and
have this list still be in order we would put it right here between this 1 and
the first 3.
We would stick it right here and then we would shift all these entries over by one.
Here we're calling bisect_left with the parameters a and 4.
Bisect_left in this case returns the offset 3.
That means if we wanted to stick 4 in this list,
we would do it between here and here.
So we'd do it between the 3 and the 6.
And then in this final example we're calling bisect_left with a and
the parameter 8.
And it's telling us that if we want to insert a,
8 into this list, then the leftmost place we can insert it such that the list is
still in sorted order is at offset four.
6:52
Now we could have also inserted it here at offset five or here at offset six.
And the list would still be in sorted order, but
bisect_left is always going to return the leftmost offset where we can insert it so
that the list is still in sorted order.
7:09
So this bisect left function is exactly what we need in order to do queries of
this index data structure that we built.
So for example if we're querying with this pattern here and
we take some 3-mer from the pattern, let's say we take the threemer GTG.
We can use the bisect left function on our index and the parameter GTG.
And it will return the offset of the first position where we could insert GTG
while maintaining sorted order of the list.
And that corresponds to this entry right here,
which is the first entry that has GTG as its key.
So if we wanted to find all the places where GTG occurs,
we could use bisect_left.
It would point as here, and then we could look up this offset and then, keep going.
Find another GTG and find its offset.
And then, keep going and find another GTG and find its offset.
So we would report that GTG occurs at offsets zero, four and six.
Ben Langmead, PhDAssistant Professor
Jacob Pritt
