0:22

How do they work?

We have now learned how to construct Profile given

Motifs, but can we construct Motifs given Profile?

We can, because given an arbitrary Profile and a set of sequences Dna,

we can construct the set Motifs(Profile,DNA) by simply finding

Profile-most probable k-mers in each sequence from Dna.

0:54

And therefore, we can further iterate this process by finding profile of motifs,

motifs of profiles, profile of motifs, until our motifs keep improving.

So this is the key idea of the algorithm called RandomizedMotifSearch.

We simply iterate and see whether the score of motif continues

to improve. And stop when it doesn't improve anymore.

1:38

If the motifs are completely random,

and if they're taken from random sequences,

then presumably. expected probability of every element

in the profile matrix is 1/4.

There is absolutely no information in such a motif.

How possibly it can lead us to the correct motif in the sequence?

Let's just keep our fingers crossed and see how this approach works on an example.

Here's my example.

These are very short DNA strings and I implanted

4-nucleotide long motifs (one motif on each string). They're shown in blue, so

2:30

First, it will randomly select motifs shown in bold here.

And, of course, it has missed most of the motifs.

They are randomly selected.

2:53

Using Profile(Motifs) it will calculate the probability

of every k-mer in the set of strings,

shown here, and will simply select the most probable k-mers in every string.

The results are in this matrix, and I should probably start iterating.

3:15

But if you look carefully at this matrix, I don't have to iterate.

It already found all blue inserted motifs right there.

It almost sounds like a magic

trick, because we started from something completely random

and, in a single iteration, found our implanted motifs!

Well, what happened?

4:09

Where does this statistical bias point to? If it points

in the direction of the implanted motif, then there is no miracle

that we start from something random (which is not really random),

and, applying iterative procedure, arrived to a hidden part.

So, let's see how it actually works.

I return back to the case that we considered before.

You saw that when we randomly selected

motifs, in the first sequence, we missed the motif (the correct, the blue one).

In the second sequence, we also missed it.

In the third sequnce, we missed it.

In the fourth sequence, we missed it.

But in the fifth one, simply by pure chance, we actually found it.

It's not a big deal.

There is always a probability that we simply by chance

select one of the implanted motifs.

But it results in a biased profile.

If you look at the profiles that

resulted from this implantation, then you see that the largest elements

in this profile actually correspond to A, C, G and T

of our implanted pattern ACGT. Therefore, even

a single correctly found k-mer in

the set of Dna strings creates a bias in the profile, and this bias

leads us to the correct sequence. Of course, it doesn't always happen.

It depends on how we have chosen initial

set of randomly selected k-mers in the sequence.

But if we try this algorithm, a thousand or

a million times, there is a good chance that

eventually one of these attempts will bring us to

the correct motif. Even if this procedure sounds ridiculous.

6:06

We now move to the next topic: "How do bacteria hibernate?"

Our goal is to apply our motifs finding algorithm to real biological problems.

To figure out how our algorithms work on

real biological data, we will start by analyzing tuberculosis.

Tuberculosis is a deadly disease that

killed quarter of population of Europe in the 19th century.

Unfortunately, humanity is not done with tuberculosis yet since

tuberculosis strains that resist to all antibiotics are now emerging.

Tuberculosis is caused by

Mycobacterium tuberculosis also called MTB.

An interesting thing about MTB

is that it can persist in for decades in humans

and one third of the world population is affected by MTB.

Of course, it usually doesn't lead to tuberculosis

nut, in some cases. bacteria switches from its latent

state to the active state and it's when the tuberculosis begins.

The question that we will be asking is how

MTB switches from the latent to the active state and how

does it survive during latency? MTB has an ability

to form dormant spores where metabolism is shut down.

In such sporulated form it can survive in

very tough conditions, for example, in conditions of food shortage or

oxygen shortage. And oxygen shortage, called hypoxia, is

associated with these latent forms of tuberculosis.

So, how can we figure out what makes

MTB switch into the latent state and return back to

the active states?

Biologists have performed a DNA array experiment and identified

roughly 25 genes that are activated in the hypoxic condition.

So when bacteria is deprived from

oxygen, these gene dramatically change their expression.

And our goal today is to discover what regulatory

motif controls these genes when they're activated or repressed.

8:44

We now have quite an arsenal of algorithms for finding motifs.

Let's try them.

But the first problem is that we have no clue of what size of motif to try.

Should we try k equal to 8 or k equal to 20? Let's try all of them

using median string problem and randomized motif search.

And you will see that, for different k, we are getting quite different results.

It is not clear which one to choose.

9:16

for median string, we actually will have

difficulties going beyond k=12 because

it is an exponential algorithm whose running time grows as four to the power k.

But for randomized motif search we can search

for very long motif and, for k=20,

we actually find this rather long motif.

You can see that there are similarities

Between the 12-mer found by the Median String.

the 12-mer found by the RandomizedMotifSearch,

and the 20-mer found by the RandomizedMotifSearch. Which one is correct?

To answer this

question, we need to introduce the notion of the motif entropy.

9:59

And entropy of motif is defined in the following way.

First, we construct the profile matrix.

Every column of the profile matrix correspond to a biased four-sided dice.

Or, in other words, to a probability distribution, (p1, p2, ...p_n).

Sum of p_i is equal

to 1, of course. And entropy is simply defined as

- p_i * log (p_i)

and summed up over all indices i. For example, we can compute the entropy of

the first column, and it will be 1.147.

10:40

We can compare it with the minimal

possible entropy, which corresponds to the extremely conserved motif

(where all symbols in the column are the same),

and with the maximal entropy

(where symbola in the column are equally likely).

So the entropy of a motif is defined as the sum of the entropies of its columns.

And now, the moment of truth.

Let's see how the algorithms that we developed

11:15

find out whether the motifs that we find are close to the biological one.

Here is the motif logo of the dormancy survival regulator site.

The motif logo is constructed in such a way that the total length of four

nucleotides in the motif logo correspond to two minus entropy.

So for completely conserved column, like nucleotide G

in this motif, we will have height two.

It is the most conserved columns of the motif.

The relative sizes of four nucleotide in

each position correspond to frequencies of these nucleotides in the column.

12:10

You can see that our randomized motif

search has actually captured a good portion of the motif.

But you can also see that we missed in some places.

We need to work harder and to figure

out what to do to develop better regulatory motif finding algorithms.

We move next to another randomized algorithm called Gibbs sampler.