Why does randomized motif search work?

Question

I'm looking for intuition for why a randomized motif search works. My current thinking is as follows:

We are selecting many random kmers from our DNA sequences. The chosen kmers will bias the profile matrix to selecting kmers like them.

Given any particular k-mer chosen, there are two possibilities:

1. We've selected a meaningless kmer, so the profile will bias selecting random (ie high entropy) kmers and the score will stop improving soon.
2. We've captured a portion of the true motif. Since the motif isn't random (ie doesn't have high entropy) subsequent iterations using this profile matrix will pick motifs closer to the real motif and the score will keep improving.

Since we give this algorithm many tries and at some point it will eventually arrive at possibility 2 and come to a good conclusion.

Is this a correct understanding of why randomized motif search works? Is there a more rigorous way to prove this?

Answer 1

Update

With regard to comment, the proof of effectiveness of Monte Carlo algorithms like this is a little thorny- if you look at the wikipedia page, you will see that a proof of statistical consistency for any Monte Carlo algorithms took a long time:

From 1950 to 1996, all the publications on Sequential Monte Carlo methodologies, including the pruning and resample Monte Carlo methods introduced in computational physics and molecular chemistry, present natural and heuristic-like algorithms applied to different situations without a single proof of their consistency, nor a discussion on the bias of the estimates and on genealogical and ancestral tree based algorithms. The mathematical foundations and the first rigorous analysis of these particle algorithms were written by Pierre Del Moral in 1996.

Here is a possibly more general reference by Del Moral in 1998. The paper is somewhat dense and I am not an expert in the field so I don't think I'll do it justice, but I think that we could probably figure out a similar mathematical proof for random motif search given time and the right problem formulation.

I sense that your concern might be with Monte Carlo algorithms generally rather than random motif search specifically, so hopefully that gets close to your question.

It does look like people have done heuristic analysis of similar algorithms, but they are not formal proofs.

Original answer

I believe that you are more or less correct.

For example, this presentation's walkthrough of the algorithm (slides 35-36) specifically refers to Greedy randomized profile motif searches. By making the greediness of the algorithm explicit, we can see that there is no claim of finding an optimal solution in any particular iteration, thus the need for multiple retries to get somewhere close to approximate solution.

One additional point made in that presentation is that this algorithm works best when coupled to approaches such as Gibbs sampling for targeting the sampled k-mer chain in regions with higher scores (less entropic k-mers).

A different learning resource with similar content (and a little more intuition) is available here.