Using BWT for Pattern Matching

Loading...

来自 University of California San Diego 的课程

Algorithms on Strings

460 个评分

University of California San Diego

Algorithms on Strings

460 个评分

课程 4（共 6 门，Specialization 数据结构与算法）

World and internet is full of textual information. We search for information using textual queries, we read websites, books, e-mails. All those are strings from the point of view of computer science. To make sense of all that information and make search efficient, search engines use many string algorithms. Moreover, the emerging field of personalized medicine uses many search algorithms to find disease-causing mutations in the human genome.

从本节课中

Burrows-Wheeler Transform and Suffix Arrays

Although EXACT pattern matching with suffix trees is fast, it is not clear how to use suffix trees for APPROXIMATE pattern matching. In 1994, Michael Burrows and David Wheeler invented an ingenious algorithm for text compression that is now known as Burrows-Wheeler Transform. They knew nothing about genomics, and they could not have imagined that 15 years later their algorithm will become the workhorse of biologists searching for genomic mutations. But what text compression has to do with pattern matching??? In this lesson you will learn that the fate of an algorithm is often hard to predict – its applications may appear in a field that has nothing to do with the original plan of its inventors.

Burrows-Wheeler Transform4:36

Inverting Burrows-Wheeler Transform7:02

Using BWT for Pattern Matching6:29

与讲师见面

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Pavel Pevzner
Professor
Department of Computer Science and Engineering
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

Okay, let's learn how to do pattern matching with Burrows-Wheeler Transform.

Let me first summarize what we learned about pattern matching with

the suffix tree.

The runtime is equal to O(length of the text + total length of all patterns).

Memory is, in the best implementation, known today is 20 * length of the text,

or which is high for live strengths like human genome.

So it would be in nuclear diclonk.

So the question we will try to address in this lesson is,

can we use Burrows-Wheeler Transform to design a more memory efficient

linear-time algorithm for multiple pattern matching?

So let's see how we can do this.

Let's search for ana in panamabananas.

Well, we'll definitely start by noticing that

there are six rows that start from letter a.

But when we look, and please notice also that we are currently matching

the last symbol in ana as in the first one.

This will be important.

So there are six rows starting from a, but

only three of them are ending in n.

What we need, because we are looking for

matching the last two symbols now of ana, which is na.

So the mental attention to these three symbols, and

using the first last property, we can figure out

where these three n's hide in the first column of our

Burrows-Wheeler matrix, here, here, and here.

After they found where they appear in the first column, we know where na appears.

In the string can be actually found, three matches of na.

This is the last two symbol in ana.

Let's now try to match the first symbol in ana, and

we know where to look for this first symbol.

We'll look for them correspondingly in the last columns of these three strings.

And after we found a in these three rows,

then using again the first last property,

we find where these three occurrences of ana

appears in the beginning of our cyclic rotation.

As a result, we found three matches of ana.

Let me specify some details of the algorithm that we just discussed.

We will use two pointers, top and bottom, that specify the range of

positions in the Burrow-Wheelers matrix that we are interested in.

In the beginning, top will go to 0 and bottom equal to 13,

to cover all positions in the text.

In the next iteration, the range of position we are interested in is narrowed

to all position where a appears in the first column.

Then, what do you do afterwards?

We are looking for the next symbol, which is n in ana,

and we are looking for the first occurrence of this symbol in

the last column among positions from top to bottom, among rows from top to bottom.

And likewise, afterwards, we are looking for the last occurrence of the symbol.

As soon as we found the first and last occurrence of this symbol in this case,

and the first last property will tell us where this n and

all n's in between are hiding in the first column.

As a result, the pointers top and bottom equal to 1 and

6 are changing into 9 and 11, they narrow the search.

And then we continue further, and

that's how we find the positions of ana in the text.

The algorithm that I just described translate in the following

BWMatching pseudocode.

And you can see lines in green describe

what we have been doing with these top and bottom pointers.

Note that we are using last to first array and

given a symbol at position index in lastColumn,

LastToFirst index defines the position of the symbol in the first column.

So it's implement first to last property.

It looks like now, finally, we are done.

We have a very first pattern matching algorithm based on

Burrows-Wheeler Transform, and it has good memory footprint.

The only problem, though, is that BWMatching is very slow.

It analyzes every symbol from top to bottom in the last column in each step.

What should we do?

The trick here is to introduce the count array.

And the count array describes the number of appearances of a given symbol

in the first i positions of the last quote.

This slide shows the count array, and ardent is the count array.

We can design a better version of BWMatching by substituting

four green lines that we discussed before

by two green lines that are using the count array.

And as you can see, we don't need anymore to explore every symbol

between top and bottom indices in the last column.

If you are wondering about the details of transformation

from the previous four lines into two

lines using the count array, check our Coursera course or

get details from our books that describes this transformation.

So it looks like finally, after all these complications, we are done.

But there is still one question we found quanza.

Where are the matches that they found?

Where do they appear in the text?

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2018 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取