Lesson 2.7

Randomized Motif Search

5 min read1 code challenge✓ Read

Watch the lectureHow Rolling Dice Helps Us Find Regulatory Motifs (Part 2)

Rolling dice to find motifs

We will now turn to randomized algorithms that flip coins and roll dice in order to search for motifs. Making random algorithmic decisions may sound like a disastrous idea; just imagine a chess game in which every move would be decided by rolling a die. However, an 18th Century French mathematician and naturalist, Comte de Buffon, first proved that randomized algorithms are useful by randomly dropping needles onto parallel strips of wood and using the results of this experiment to accurately approximate the constant π. For more details, see "DETOUR: Buffon's Needle" in the print companion or at Cogniterra.

Randomized algorithms may be nonintuitive because they lack the control of traditional algorithms. Some randomized algorithms are Las Vegas algorithms, which deliver solutions that are guaranteed to be exact, despite the fact that they rely on making random decisions. Yet most randomized algorithms, including the motif finding algorithms that we will consider in this chapter, are Monte Carlo algorithms. These algorithms are not guaranteed to return exact solutions, but they do quickly find approximate solutions. Because of their speed, they can be run many times, allowing us to choose the best approximation from thousands of runs.

We previously defined Profile(Motifs) as the profile matrix constructed from a collection of k-mers Motifs in Dna. Now, given a collection of strings Dna and an arbitrary 4 x k matrix Profile, we define Motifs(Profile, Dna) as the collection of k-mers formed by the Profile-most probable k-mers in each string from Dna. For example, consider the following Profile and Dna:

Taking the Profile-most probable 4-mer from each row of Dna produces the following 4-mers (shown in red):

In general, we can begin from a collection of randomly chosen k-mers Motifs in Dna, construct Profile(Motifs), and use this profile to generate a new collection of k-mers:

Motifs(Profile(Motifs), Dna).

Why would we do this? Because our hope is that Motifs(Profile(Motifs), Dna) has a better score than the original collection of k-mers Motifs. We can then form the profile matrix of these k-mers,

Profile(Motifs(Profile(Motifs), Dna))

and use it to form the most probable k-mers,

Motifs(Profile(Motifs(Profile(Motifs), Dna)), Dna).

We can continue to iterate. . .

...Profile(Motifs(Profile(Motifs(Profile(Motifs), Dna)), Dna))...

for as long as the score of the constructed motifs keeps improving, which is exactly what RandomizedMotifSearch does. To implement this algorithm, you will need to randomly select the initial collection of k-mers that form the motif matrix Motifs. To do so, you will need a random number generator (denoted RandomNumber(N)) that is equally likely to return any integer from 1 to N. You might like to think about this random number generator as an unbiased N-sided die.

RandomizedMotifSearch(Dna, k, t)
    randomly select k-mers Motifs = (Motif1, …, Motift) in each string from Dna
    BestMotifs ← Motifs
    while forever
        Profile ← Profile(Motifs)
        Motifs ← Motifs(Profile, Dna)
        if Score(Motifs) < Score(BestMotifs)
            BestMotifs ← Motifs
            else
            return BestMotifs

Since a single run of RandomizedMotifSearch may generate a rather poor set of motifs, bioinformaticians usually run this algorithm thousands of times. On each run, they begin from a new randomly selected set of k-mers, selecting the best set of k-mers found in all these runs.

Exercise BreakProve that RandomizedMotifSearch, whose pseudocode is reproduced below, will eventually terminate.

RandomizedMotifSearch(Dna, k, t)
    randomly select k-mers Motifs = (Motif1, …, Motift) in each string from Dna
    BestMotifs ← Motifs
    while forever
        Profile ← Profile(Motifs)
        Motifs ← Motifs(Profile, Dna)
        if Score(Motifs) < Score(BestMotifs)
            BestMotifs ← Motifs
            else
            return BestMotifs

Code Challenge Implement RandomizedMotifSearch. (Solve at Cogniterra or Rosalind.)Solve it with the autograderFree to start in the interactive text

• Input: Integers k and t, followed by a collection of strings Dna.
• Output: A collection BestMotifs resulting from running RandomizedMotifSearch(Dna, k, t) 1,000 times. Remember to use pseudocounts!

Why randomized motif search works

At first glance, RandomizedMotifSearch appears to be doomed. How can this algorithm, which starts from a random guess, possibly find anything useful? To explore RandomizedMotifSearch, let’s run it on five short strings with the implanted (4,1)-motif ACGT (shown in upper case letters below) and imagine that it chooses the following 4-mers Motifs (shown in red) at the first iteration. As expected, it misses the implanted motif in nearly every string.

We now construct the profile matrix Profile(Motifs) of the chosen 4-mers.

and compute the probabilities of every 4-mer in Dna based on this profile matrix. For example, the probability of the first 4-mer in the first string of Dna is Pr(ttAC|Profile) = 0.2 · 0.2 · 0.2 · 0.2 = 0.0016. The maximum probabilities in every row are shown in red below.

We select the most probable 4-mer in each row above as our new collection Motifs (shown below). Notice that this collection has captured all five implanted motifs in Dna!

STOP and Think How is it possible that randomly chosen k-mers have led us to the correct implanted k-mer? If you think we manufactured this example, select your own initial 4-mers and see what happens.

For the Subtle Motif Problem with implanted 15-mer AAAAAAAAGGGGGGG, when we run RandomizedMotifSearch for 100,000 times (each time with new randomly selected k-mers), it returns the 15-mers shown in the figure below as the lowest scoring collection Motifs across all iterations, resulting in the consensus string AAAAAAAAacaGGGG with score 43. These strings are only slightly less conserved than the collection of implanted (15, 4)-motifs with score 40 (or the motif returned by GreedyMotifSearch with pseudocounts having score 41), and it largely captures the implanted motif. Furthermore, unlike GreedyMotifSearch, RandomizedMotifSearch can be run for a larger number of iterations to discover better and better motifs.

RandomizedMotifSearch has the advantage of being able to find longer motifs. In the epilogue, we will see that this feature is important in practice.

Figure: The lowest scoring collection of strings Motifs produced by 100,000 runs of RandomizedMotifSearch, along with their consensus string and score for the Subtle Motif Problem.

STOP and Think Does your run of RandomizedMotifSearch return a similar consensus string? How many times do you need to run RandomizedMotifSearch to obtain the implanted (15, 4)-motif with distance 40?

Although the motifs returned by RandomizedMotifSearch are slightly less conserved than the motifs returned by MedianString, RandomizedMotifSearch has the advantage of being able to find longer motifs (since MedianString becomes too slow for longer motifs). In the epilogue, we will see that this feature is important in practice.