Lesson 2.8
How Can a Randomized Algorithm Perform So Well?
Watch the lectureHow Rolling Dice Helps Us Find Regulatory Motifs (Part 2)
In the previous section, we began with a collection of implanted motifs that resulted in the following profile matrix.
If the strings in Dna were truly random, then we would expect that all nucleotides in the selected k-mers would be equally likely, resulting in an expected Profile in which every entry is approximately 0.25:
Such a uniform profile is essentially useless for motif finding because no string is more probable than any other according to this profile and because it does not provide any clues on what an implanted motif looks like.
At the opposite end of the spectrum, if we were incredibly lucky, we would choose the implanted k-mers Motifs from the very beginning, resulting in the first of the two profile matrices above. In practice, we are likely to obtain a profile matrix somewhere in between these two extremes, such as the following:
This profile matrix has already started to point us toward the implanted motif ACGT, i.e., ACGT is the most likely 4-mer that can be generated by this profile. Fortunately, RandomizedMotifSearch is designed so that subsequent steps have a good chance of leading us toward this implanted motif (although it is not certain).
If you still doubt the efficacy of randomized algorithms, consider the following argument. We have already noticed that if Dna were random strings, then RandomizedMotifSearch would start from a nearly uniform profile, and there would be nothing to work with. However, the key observation is that the strings in Dna are not random because they include the implanted motif! These multiple occurrences of the same motif may direct the profile matrix away from the uniform profile and toward the implanted motif. For example, consider again the original randomly selected k-mers Motifs (shown in red):
You will see that the 4-mer AGGT in the last string happened to capture the implanted motif simply by chance. In fact, the profile formed from the remaining 4-mers (taac, GTct, ccgG, and acta) is uniform. Note that only completely captured motifs (like AGGT) rather than partially captured motifs (like GTct or ccgG) contribute to the statistical bias in the profile matrix.
Exercise Break Compute the probability that ten randomly selected 15-mers from the ten 600-nucleotide long strings in the Subtle Motif Problem capture at least one implanted 15-mer. (Allowable error: 0.000001)
Although the probability that randomly selected k-mers match all implanted motifs is negligible, the probability that they capture at least one implanted motif is significant. Even in the case of difficult motif finding problems for which this probability is small, we can run RandomizedMotifSearch many times, so that it will almost certainly catch at least one implanted motif, thus creating a statistical bias pointing toward the correct motif.
Unfortunately, capturing a single implanted motif is often insufficient to steer RandomizedMotifSearch to an optimal solution. Therefore, since the number of starting positions of k-mers is huge, the strategy of randomly selecting motifs is often not as successful as in the simple example above. The chance that these randomly selected k-mers will be able to guide us to the optimal solution is relatively small.
Exercise Break Compute the probability that ten randomly selected 15-mers from ten 600-nucleotide long strings (as in the Subtle Motif Problem) capture at least two implanted 15-mers.