Lecture: Boyer-Moore: putting it all together

Loading...

Do curso por Johns Hopkins University

Algoritmos para Sequenciamento de DNA

304 ratings

Johns Hopkins University

Algoritmos para Sequenciamento de DNA

304 ratings

Curso 4 de 8 em 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.

Na lição

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

Conheça os instrutores

Ben Langmead, PhD
Assistant Professor
Computer Science
Jacob Pritt

Department of Computer Science

So we're studying Boyer-Moore and we have our bad character rule and

we have our good suffix rule.

And so far we've used them separately.

But in practice, we're going to use both of them together.

So basically, whenever we have a mismatch, we're going to try both rules.

And each rule will tell us some amount that we can shift the pattern P.

In other words, some number of alignments that we can skip.

And we're simply going to take the maximum of the two.

So let's use them both in an example.

So let's say that this here is our first alignment of P to T.

The very first character comparison is going to result in a mismatch.

This G in the pattern mismatches this T in the text.

So since no characters matched, the good suffix rule is not applicable here.

There's no matching characters so we can't use the good suffix rule.

We have to use the bad character rule.

So what does the bad character rule say?

Well it says that we should shift until this highlighted T here,

is underneath this T here.

So this skips six alignments.

So it shifts P over by seven positions or it skips six alignments.

And the good suffix rule doesn't skip at all, because it's not applicable.

So we're going to use the bad character rule in this case, and

we're going to skip over six alignments.

Okay. So let's do that.

Here's our next alignment.

We've skipped over six.

So here we get some matches, so we have our mismatched character here, and we have

our small T, the stretch of characters that we matched within the text.

And so, if we use our bad character rule,

it's going to tell us that we can't skip any alignments.

Because as soon as we shift P over by one,

the C down here that's highlighted in purple comes underneath this C right here.

So the bad character rule doesn't skip any alignments.

The good suffix rule does skip some alignments, so this is GCG.

This is the string of characters that we matched within T.

There's another occurrence of GCG right here, so

the good suffix rule is going to let us skip two alignments.

We're going to shift P over by three characters.

So we take the maximum, and

we shift P over by three characters, skipping two alignments.

And we get this.

So in the next alignment, the bad character rule will skip two

alignments where the good suffix rule will skip seven alignments.

So we're going to take the good suffix rule, and that gets us to this point here.

So we just solve three steps where we used the bad character rule and the good suffix

rules together, and we'll implement this is the upcoming practical session.

So you might wonder,

how much of an improvement is Boyer-Moore over naive exact matching.

So in this example, we went through a few steps of Boyer-Moore and

we skipped a total of 15 alignments.

So furthermore, there were several characters in the text,

these characters highlighted up here, that we completely ignore.

They were never involved in any character comparisons that we did.

This explains Boyer-Moore's advantage over naive exact matching.

Even in the best case,

naive exact matching is never going to skip an alignment, and

there is never going to be a character of the text T that it fails to examine.

So in practice, we do expect Boyer-Moore to be substantially faster.

And this is generally true.

And we'll explore this a little bit in the homework in this module.

We have to address now one last detail, which is that in order to use our rules,

the bad character rule and the good suffix rule, we need to be able to look up

how far the rules tell us to skip.

So the example's we've worked through so

far, we've been figuring out how far we can skip sort of by eye.

By looking at the pattern P and by thinking about matched or

the mismatched characters in the text T.

In reality, what Boyer-Moore implementations do is they build

some lookup tables beforehand, so that every time we want to apply a rule,

either rule, the number of skips can simply be looked up in a table.

So, the only information that we need in order to build these tables is

the pattern P.

The text T is not needed to build these tables.

So for example, I'm showing you a table here.

This table will help us apply the bad character rule for a particular pattern P.

So here the pattern is TCGC,

which you can see is labeling the columns of this matrix here.

And so how do we use this table, this Matrix?

Well let's look at an example.

Here's an alignment over here on the right.

And we've done two character comparisons.

There was a match, C matching C, and then a mismatch, G mismatching T.

So the G, at offset 2 in the pattern, that's what mismatched.

And the character that it mismatched in the text was a T.

So this offset 2, in the pattern P, corresponds to this column of the matrix.

And this mismatched character from the text

T corresponds to this row of the matrix.

So we're going to look in this column, and

this row, and we'll find a number there.

And that number is the number of alignments that we can skip

according to the bad character rule.

So in this case, we can skip one alignment, which is to say,

we can shift P over by 2 according to the bad character rule.

So before Boyer-Moore starts to examine any alignments,

first we have to build lookup tables for both the bad character rule,

like the table that we can see here, and for the good suffix rule.

We won't describe exactly how to build those tables here.

But just keep in mind that those are a couple of tables that we have to build

beforehand.

And the only thing that we need in order to build those tables is the pattern P.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play