Approximate Pattern Matching

Loading...

來自 University of California San Diego 的課程

Algorithms on Strings

517 個評分

University of California San Diego

Algorithms on Strings

517 個評分

課程 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.

Approximate Pattern Matching6:43

與講師見面

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

So far, we were focusing on exact measures,

which will help us to answer the question,

where is the positions on my journal and in the reference journal identical?

But we, of course, are most interested in approximate pattern matching, because we

want to find positions in my journal that are different from the reference journal.

And approximate pattern matching problem is given a string Pattern, a string Text,

and an integer d, try to find all positions in text where the string

Pattern appears as a substring with at most d mismatches.

I'm sure you can come up with a fast algorithm for solving this problem, but

I'm really interested in a more difficult problem.

Multiple approximate pattern matching, a set of strings Patterns,

a string Text, and an integer d is an input.

And we want to find all positions in Text where a string from Patterns

appears as a substring with at most d mismatches.

Let's try to use the Burrows-Wheeler Transform again to find approximate

matches of ana in panamabananas, and we will allow up to one mutation in ana.

We will start again with finding all rows in the Burrows-Wheeler

matrix that start with all a, here they are.

And amongst them,

we want to find rows that contains na.

And among six rows that start with a,

only three of them actually end with n.

Here are these rows, and we are interested in them.

They form exact matching of the last two symbols of ana to our text.

But that's not the only thing we are interested in.

In the past, it was the only thing, but now,

they're actually interested in all six rows starting starting from a,

because we are interested in approximate matches as well.

And to find approximate matches, we need to retain all the six rows.

And specify the number of mismatches for each of these rows, here they are.

After we found all rows we're interested in,

we use again the first last property to find where the symbol in the last

elements of these rows appears in the first column.

And they will be appearing here.

Once again, we check which of these six appearances

will match ana with, at most, one notation.

And it turn out that one of them actually doesn't satisfy this property,

because there is a match, but it's a match with two mutations,

which is beyond our maximum allowable number of mutation.

And that's why we are not interested in this row anymore.

And then by applying last to first property again, we find all

occurrences of ana, where there is up to one mutations in text.

How do we find where all these five approximate occurrences

appear in the text?

Well, you can use suffix array, or more precisely, the partial suffix array.

And you can figure out how to use the partial suffix array to find

approximate occurrences as well.

I tried to hide some details of approximate pattern matching

with Burrows-Wheeler Transform, to make it a little bit easier for

you to understand how it works.

In reality, it is a bit more complex.

If you wanted to learn about the details of approximate pattern matching

with Burrows-Wheeler Transform, you can find those details in our

Bioinformatics Algorithm course on Coursera or in our book.

Sam Berns had a very rare genetic disease.

In fact, there are less that 1,000 people on earth with this progeria.

However, there are over 7,000 of such rare genetic diseases.

And as a result, about 10% of human population have a rare genetic disease.

We now learn how pattern matching will help the doctors of the future

to learn about mutations in our genome and

will allow them to diagnose many of these mutations.

However, even if a child is diagnosed with a disease causing mutation,

in the case of progeria, there is no cure.

And, this is the next challenge for personalized genomics,

moving from diagnostic to new drugs aimed at specific diseases.

And to finish this lecture, I will tell you just about one case

of a very successful drug that biologists developed based on exact

knowledge of specific mutation implicated in a disease.

I will talk about more complex type of mutations.

So far, we've talked about a point mutation when

one nucleotide is changing into another nucleotide.

But there are more complex mutations that work as an earthquake

operating on the genome.

In this particular case, I'm talking about so-called Philadelphia chromosome

that is formed from two normal human chromosomes.

Pieces of these two normal chromosomes exchange position.

As a result, two Chimera chromosomes are formed as shown here.

Biologists figured out how to detect this event, and

it turns out that it is a biomarker for chronic myeloid leukemia.

And based on exact knowledge of biological maheners, admittedly, it's more complex

as the mutations restarted, but it's once again, a mutation in the human genome.

Biologists were able to develop a miracle drug called

Gleevec that is very efficient for chronic myeloid leukemia.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2019 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取