The Decoding Problem

Loading...

From the course by University of California San Diego

Finding Mutations in DNA and Proteins (Bioinformatics VI)

27 ratings

University of California San Diego

Finding Mutations in DNA and Proteins (Bioinformatics VI)

27 ratings

Course 6 of 7 in the Specialization Bioinformatics

In previous courses in the Specialization, we have discussed how to sequence and compare genomes. This course will cover advanced topics in finding mutations lurking within DNA and proteins. In the first half of the course, we would like to ask how an individual's genome differs from the "reference genome" of the species. Our goal is to take small fragments of DNA from the individual and "map" them to the reference genome. We will see that the combinatorial pattern matching algorithms solving this problem are elegant and extremely efficient, requiring a surprisingly small amount of runtime and memory. In the second half of the course, we will learn how to identify the function of a protein even if it has been bombarded by so many mutations compared to similar proteins with known functions that it has become barely recognizable. This is the case, for example, in HIV studies, since the virus often mutates so quickly that researchers can struggle to study it. The approach we will use is based on a powerful machine learning tool called a hidden Markov model. Finally, you will learn how to apply popular bioinformatics software tools applying hidden Markov models to compare a protein against a related family of proteins.

From the lesson

Week 4: Introduction to Hidden Markov Models

<p>Welcome to week 4 of class!</p> <p>This week, we will start examining the case of aligning sequences with many mutations -- such as related genes from different HIV strains -- and see that our problem formulation for sequence alignment is not adequate for highly diverged sequences.</p> <p>To improve our algorithms, we will introduce a machine-learning paradigm called a hidden Markov model and see how dynamic programming helps us answer questions about these models.</p>

Classifying HIV Phenotypes 6:35

Gambling with Yakuza 12:51

From a Crooked Casino to a Hidden Markov Model 9:22

The Decoding Problem 5:38

The Viterbi Algorithm 7:19

Meet the Instructors

Pavel Pevzner
Professor
Department of Computer Science and Engineering
Phillip Compeau
Visiting Researcher
Department of Computer Science & Engineering

We are now ready to find the most likely hidden path in an HMM and it corresponds

to the following decoding problems that ask us to find the optimal hidden path.

The input is an emitted stream, and

then HMM defined by four object alphabet, the set of state,

the matrix of transition probabilities and the matrix of emission probabilities.

And the output is a hidden path pi that maximizes the probability of x and pi.

Probability of x pi as we saw equal to the product of probability of

x given pi multiplied by probability of pi and it is a product of n term,

each term being the product of emission probability and

transition probability, as described in the slide.

To solve the decoding problem, we will try to build a Manhattan graph.

In such a way that every path in this graph will

correspond to a hidden path in HMM, and vice versa.

Every hidden paths in HMM will correspond to a path in the built Manhattan.

For the coin flipping HMM with this HMM diagram,

we will construct Manhattan consisting of two rows and

n columns, where n is the number of emitted symbol.

In this case, we will also add source and sink node to the beginning and

to the end of the resulting directed acyclic graph.

And for the HMM that omitted the strength of symbols FBBBFF,

we will construct is the following paths through the Manhattan right here.

And you see as that for every string of omitted symbols,

we can construct the paths in the correspondent pattern.

For a little bit more complex HMM consisting of three states,

our Manhattan will be built of three rows and n columns.

Generally if we have an HMM for

this k state there will be k rows in this Manhattan.

As before we will add start and end state and

note that in difference from the Alignment Manhattan,

when we had just three directions from every node,

in the Decoding Manhattan we had many directions, anything that

goes to the East works in this newly built Manhattan.

We now need to define the weight

of address means that newly built Manhattan graph for an HMM.

Let's consider an edge then starts and

go i minus y in state l and connects it to the node

corresponding to state k in the column i.

We will refer to this edge as l, k, i-1.

Now this edge correspond to transition n from

state l to state k with probability of transition lk.

And it also correspond to emitting the symbol xi from the state k.

And therefore we define the weight of this edge as weight l,

k, i minus pi and is equal to the product of

emission probability of emitting symbol x,

i from state k, multiplied by transition

probability from state l to state state k.

Let's see how would we assign edge weight for Crooked Casino.

In this case, as before, weight of the edge l, k,

i-1 = the product of the corresponding emission and transition probability.

What about this edge?

So the weight of this bold edge from state B to state B

are equal to emission probability of emitting symbol h from state

B multiplied by a transition probability of moving from B to B which is 0.75 x 0.9.

And we will continue further with the sign in,

it's probability of all edges in a similar fashion.

And afterwards we will construct a graph in which

product weight of a hidden path will be simply equal

to the product of weights of individual edges, as shown on this slide.

For example, the product weight of this path

will be simply equal to probability of x.

Therefore we constructed a graph in which product weight of every

path equal to probability of x pi, exactly what we're interested in.

And therefore the computing of probability of x pi and

finding hidden paths pi corresponding to maximizing probability x pi,

is simply finding the path with this maximum product weight.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play