Lecture: Boyer-Moore basics

We continue on our journey toward better algorithms for

solving the reed alignment problem.

We studied naive exact matching which was very simple.

It consisted of two nested loops, a loop that iterates over possible alignments and

then a loop that iterates over character comparisons.

Next we will look at an algorithm called Boyer-Moore.

Boyer-Moore is similar to naive exact matching, in some ways.

It's still going to try alignments, and for each alignment,

it will try character comparisons, but it's going to be clever

by skipping many alignments that it doesn't need to examine.

Boyer-Moore is a very popular algorithm.

It's been around for a long time, and

it's really the benchmark exact matching algorithm.

There have been many variants on Boyer-Moore proposed, and

it's implemented in many different systems.

Chances are very good that at some point you have done a search in a web document

or file on your hard drive, and that search was implemented using Boyer-Moore.

So, we'll start with this insight.

Here's a snapshot of one moment in the naive algorithm.

We're trying to align word,

the pattern, with these characters in the text, and eventually we hit a mismatch

where the character r in our pattern mismatches a u in the text.

So normally, if we were doing the naive exact matching algorithm, we would now,

once we reach this mismatch, we would break out of the inner loop and

we would move onto the next iteration of the outer loop,

which is going to try the next alignment to the right.

But we actually now have a hint

that tells us that the next alignment over also is not going to match.

So how do we know that?

Well, because this u that we mismatch in the text

doesn't occur anywhere in the pattern P.

So any way of lining up P opposite this u in the text is going to be fruitless.

So it can't possibly result in a match,

because the character u doesn't occur anywhere within P.

So we know that we can skip the next two alignments.

Both of those alignments will still place

P such that it overlaps the u in the text, so we don't have to try them.

We can skip them.

We know that they're not going to result in matches.

So this can be generalized into a principle that we can use in a lot of

situations, and in fact, the next algorithm that we discuss, Boyer-Moore,

uses this principle to the maximum possible extent.

The principle is that we're going to learn from the character comparisons that we do

in order to skip alignments that provably won't resolve in a match.

They won't be fruitful.

So the first thing to know about Boyer-Moore is that we're going to try

alignments in left to right order as we did with naive exact matching, but we're

going to try character comparisons in the opposite order, in right to left order.

So here's an illustration.

We'll try alignments in left to right order, but here's a given alignment.

For this given alignment we're going to do the character comparisons.

Starting from the right-hand side.

So in this case we compare a d in the pattern to a d in the text and they match.

And then we go to the left and try an r in the pattern and

it mismatches an l in the text.

The next component of Boyer-Moore is something called the bad character rule.

And this rule says that upon mismatch, if we do some character comparisons,

and then eventually we mismatch, upon mismatch,

we're going to skip alignments until one of two things happens.

Either the mismatch becomes a match, or

the pattern P moves all the way past the mismatched text character.

So here is an example.

Here is a text T and a pattern P and we're trying this alignment here which is

the very first alignment, the left most alignment.

And we're going to try character comparisons again starting from

the right-hand side.

So first we'll compare a C to a C and find a match.

And we'll compare a G to a G.

And then we'll compare a T to a T.

And then, we hit a mismatch.

We compare a T in the text,

sorry a T in the pattern to a C in the text and they mismatch.

So the question is how far do we skip before this mismatch becomes a match?

So the question is how far do we shift P over before this C

in the text is matching a corresponding C in the pattern?

Well we can tell by looking to the left within P.

So if we look to the left within P we're looking for

the next C over to the left and we find it here.

So the amount that we have to move P in order for

this mismatch to become a match is one, two, three.

We have to shift it over by three positions, or in other words,

we're skipping two alignments.

If we shift P over by three, then we're skipping two alignments.

So let's go ahead and

skip those two alignments, and now let's do this process again.

Let's use the bad character rule again.

So here's our new alignment.

We're going to start at the righthand side.

We're going to find that these Cs match and then we're going to reach a mismatch.

A G in the pattern mismatches an A in the text.

So we apply the bad character rule again, but in this case, the mismatched character

in the text, which is A, does not occur anywhere to the left within P.

There are no occurrences of A over here within the pattern P.

And that means we're going to move P all the way past the mismatched character.

If there's no As to the left, then we don't have to try any of the alignments

that have character of P opposite that A.

We are going to shift is over like this, all the way past the mismatched character.

So those are two steps of using the bad character rule,

which is one of the rules that we'll use in Boyer-Moore.

The last component of Boyer-Moore is another rule.

It's called the good suffix rule.

So this rule states that we're going to let T

equal the substring that's matched by our inner loop.

So we're going to use small t to represent this substring that's matched.

So in this example, we did the character comparison starting from the right again

and we matched a C, and then we matched an A, and then we matched a T.

And then we reached a mismatch.

A T in the pattern mismatched a C in the text.

So we're going to call this substring right here, small t.

So, we're going to skip until there

are no mismatches between the pattern P and small t.

Or until P moves all the way past small t.

So, you can see how this is related to the bad character rule.

The bad character rule said that upon mismatch,

we want to shift P such that the mismatch becomes a match.

And the good character rule is saying, essentially, that for

the characters we did match, we want to shift P such that

we don't turn any of those matches into a mismatch at the end of that shift.

So in this particular case,

when we apply the good suffix rule, how far are we going to skip?

Well, let's look for another occurrence of small t,

which is T A C, further to the left within P.

You can see one right here.

So the shortest amount that we can shift P is

such that this T A C in the pattern P comes under this T A C in the text T.

So in that case, we'll have skipped three alignments.

And once we've done that, here's our new alignment.

We've now shifted P, and here's our next alignment.

And we have several matches, so that again,

here's our small t, the portion of the text T that we matched.

And so now, how far do we shift P before there are no mismatches,

no new mismatches between P and the characters and small t?

This one's a little harder to see at first, but

you'll see that there is a prefix of P, C T T A C,

that matches a suffix of small t.

So C T T A C right here matches C T T A C right here, right?

So that's when we should stop shifting.

That's how far the good suffix rule is telling us to shift.

So, we just skipped three alignments there.

And so, that's two steps of the good suffix rule.

So, now we have two rules.

We have the bad character rule, which tries to turn a mismatch into a match,

and we have the good suffix rule, which tries to keep the matches matches and

not have them turn into mismatches.

Algoritmos Aplicado ao Sequenciamento de DNA

Habilidades que você aprenderá

Avaliações

Ministrado por

Ben Langmead, PhD

Jacob Pritt

Explore nosso catálogo

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