Lecture: Variations on k-mer indexes

Loading...

En provenance du cours de Johns Hopkins University

Algorithms for DNA Sequencing

392 notes

Johns Hopkins University

Algorithms for DNA Sequencing

392 notes

Cours 4 sur 8 dans Specialization Genomic Data Science

We will learn computational methods -- algorithms and data structures -- for analyzing DNA sequencing data. We will learn a little about DNA, genomics, and how DNA sequencing is used. We will use Python to implement key algorithms and data structures and to analyze real genomes and DNA sequencing datasets.

À partir de la leçon

Preprocessing, indexing and approximate matching

In this module, we learn useful and flexible new algorithms for solving the exact and approximate matching problems. We'll start by learning Boyer-Moore, a fast and very widely used algorithm for exact matching

Week 2 Introduction 1:34

Lecture: Boyer-Moore basics8:50

Lecture: Boyer-Moore: putting it all together6:15

Lecture: Diversion: Repetitive elements5:02

Practical: Implementing Boyer-Moore 10:01

Lecture: Preprocessing7:02

Lecture: Indexing and the k-mer index10:43

Lecture: Ordered structures for indexing8:06

Lecture: Hash tables for indexing7:13

Practical: Implementing a k-mer index 7:23

Lecture: Variations on k-mer indexes9:25

Lecture: Genome indexes used in research9:34

Lecture: Approximate matching, Hamming and edit distance6:53

Lecture: Pigeonhole principle6:37

Practical: Implementing the pigeonhole principle 9:30

Rencontrer les enseignants

Ben Langmead, PhD
Assistant Professor
Computer Science
Jacob Pritt

Department of Computer Science

We discussed the kMer index, as well as two different multimap data

structures that we can use to implement the kMer index, and

now we'll see two variations on the theme of a kMer index.

So, before when we built our kMer index,

we built it from all of the kMers from the text T.

Every kMer offset pair appears in this index, for example.

And it starts with the fivemer at offset 0 and

goes all the way to the fivemer at offset 6.

So, but what if we didn't take every kMer?

What if, instead, we took every other kMer?

So, for example, what if we took just the kMer that are at even offsets,

with respect to the text T, and

we got rid of the kMer that were at odd offsets with respect to the text?

So, for example, starting with the index you see here,

we can remove, as you see indicated by these red slashes,

we can remove the kMers that start at the odd offsets.

And so, once we remove them,

we're left only with the kMer that start at even offsets.

So, why might we do this?

An advantage is that the index is now smaller.

Alright. The index takes up less memory, and

it's also a little faster to query.

So, for example, if we were using Binary search to query this index,

we've now cut the size of the index in half,

which is going to save us about one bisection when we do Binary search.

So it's going to be a little bit quicker to query.

On the other hand, the fact that there are fewer kMers

in the index now might be a little bit concerning.

So you might wonder if that'll cause us to miss some of the matches that

we might otherwise have been able to find, if we had kept all the kMers in our index.

So for example, say we are trying to match this pattern P, that you see here.

And we take the first fiber from P, and we query the index.

But we don't get a hit.

This particular fiber does not appear in the index, and

yet this pattern P does occur in the text T you can see it occurs

right here G-C-G-T-C-T-T.

So that's concerning but

you might also notice if we had just taken instead of the first 5 mir.

We had taken the second 5 mir from P and

used it to query the index we actually would have found two hits.

And these correspond to these two different offsets with respect to T.

And if we do verification that these two offset we will

find that in the case of the second offset there was in fact a match.

So we'll find the match.

If we use just the first kMer we would have missed the match.

But if we tried both the first and

the second kMer then we would have found the match.

So let's think about the scenario again but

using a slightly different picture here.

So here we represent the text T here up the top and

the kMer that we add to the index are shown here below.

Then here's our pattern P and

then the kMers that we take from P in order to query the index are shown here.

So again our strategy is to build the index with every other kMer from the text.

Every even offset kMer, so here's the kMer in offset 0,

the kMer in offset 2, offset 4, offset 6, ecetera.

And then we query the index using the first kMer from P

here recording all the index hits that we find.

And then we query it again using the kMer the second offset with respect to P here.

And again we would query all the index hits that we find.

And we verify all those hits.

So actually there's nothing all that special about using the first and second.

kMers from P.

So the important thing is that the two queries have to come from even and

odd offsets with respect to P.

So in the example we just saw, we use the kMers at offsets 0 and 1 with

respect to P, but in another scenario, we might've used different kMers.

So here are the kMers at offsets 4 and 3 with respect to P.

That's fine.

As long as one of them comes from an even offset,

and the other one comes from an odd offset, with respect to P.

And in fact, it's not too hard to generalize this scheme so

that we index not every other kMer from the text T, but say, every third kMer.

Or every fourth kMer or every nth kMer where we can choose that n.

So for example say that our index is built not over every other kMer but

over every third kMer.

So maybe that looks a little bit like this.

Now given so here we are we've extracted the zeroth and

the third and the sixth, the kMers at all the different offsets.

At multiples of three, and then we query it three times now, instead of twice.

We query it with the first three kMers with respect to P.

It's a similar thing but we're doing it in three,

taking every third instead of every other.

And then again, there's nothing special about taking the first three kMers

with respect to the pattern P and using those to query the index.

We could have just picked any three,

as long as they are at different offsets, modulo three.

You know, using modular arithmetic,

where some offset modulo three is just the remainder after dividing by three.

At any rate, it's easy to generalize this scheme, so

that instead of taking every other gamer, we take every n-th gamer.

So moving on to another variation on the theme of the kMer index.

Instead of building the index over sub strings, taken from the textee,

we can also build the index over subsequences, taken from the textee.

So what's a subsequence?

How's that different from a sub string?

Well, subsequence of a string S is a string consisting of characters that also

occur in S, in the same order, but not necessarily all in a row,

not necessarily consecutively, which was a requirement of a substring.

So, for example, here's a string, this string called seq here.

And here is a subsequence of that string.

And the way we got this subsequence is that it consists of the character

at offset 0, concatenated with the character at offset 1, concatenated with

the character at offset 5, offset 7 and it makes this subsequence here.

So, AAGT, is a subsequence of the string, but it is not a substring.

We can look for it using dot find and we get the return value -1

which just basically means that that does not occur as a substring.

So, that string does not occur as a substring, but it is a subsequence.

So substrings are always also subsequences,

but subsequences are not necessarily substrings.

In order to be a substring, there has to be some place where

those characters occur consecutively, in a row, in a string.

So let's look at an example of this.

So here, instead of taking the first fivemur of T and putting into the index.

We're going to take the first subsequence of a particular shape.

So the shape of the subsequence is indicated by the blue underscores here.

So we're going to take two characters, and then skip one, and then take

one character, and then skip one, and then take two more characters after that.

So we're going to take all these characters and

concatenate them together and then insert them into the index and here we go,

we got this subsequence extracted from offset 0 and

then we can do the same thing and offset 1.

Again we take a subsequence, it’s of the same shape, so

we'll take two characters and then skip one, then take one character, and

then skip one, and then take two.

And then well insert the corresponding entry into our index.

And we do the same for offset two and we do the same for all the other offsets.

And here is the index we would get if we did things this way.

So now we have an index built from subsequences of T and if we have a pattern

P and we would like to now query this index, then the first thing we would do is

we would extract the same shaped subsequence from the string P.

So in this case, again, we'll take the first two characters GC and then skip one

and take the next character and then skip one and then take the next two and those

concatenated together are going to be our key that we can go look up in the index.

And in this case we'll look in the index and get a hit at offset 3.

So, why should we do this?

And what sort of advantages and disadvantages would it have?

Well, the short answer is that it tends to increase the specificity of the filter,

provided by the index.

In other words,

when we get an index hit, it's going to lead to a successful verification

more of the time than if we had taken those characters to be consecutive.

To be a substring of T.

And we'll elaborate on what this means a little bit later in a homework assignment.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play