Answers.Body: <h2>Update</h2>
  <p>With regard to comment, the proof of effectiveness of Monte Carlo algorithms like this is a little thorny- if you look at <a href="https://en.wikipedia.org/wiki/Monte_Carlo_method" rel="nofollow noreferrer">the wikipedia page</a>, you will see that a proof of statistical consistency for any Monte Carlo algorithms took a long time:</p>
  <blockquote>
  <p>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.</p>
  </blockquote>
  <p><a href="https://projecteuclid.org/journals/annals-of-applied-probability/volume-8/issue-2/Measure-valued-processes-and-interacting-particle-systems-Application-to-nonlinear/10.1214/aoap/1028903535.full" rel="nofollow noreferrer">Here is a possibly more general reference by Del Moral in 1998.</a> 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.</p>
  <p>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.</p>
  <p>It does look like <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC312096/pdf/nar00079-0138.pdf" rel="nofollow noreferrer">people have done heuristic analysis of similar algorithms</a>, but they are not formal proofs.</p>
  <h2>Original answer</h2>
  <p>I believe that you are more or less correct.</p>
  <p>For example, <a href="http://bix.ucsd.edu/bioalgorithms/presentations/Ch12_RandAlgs.pdf" rel="nofollow noreferrer">this presentation's</a> walkthrough of the algorithm (slides 35-36) specifically refers to <strong>Greedy</strong> 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.</p>
  <p>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).</p>
  <p>A different learning resource with similar content (and a little more intuition) is available <a href="https://www.bioinformaticsalgorithms.org/bioinformatics-chapter-2" rel="nofollow noreferrer">here</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-26T17:49:56.333Z
Answers.Text: That's actually the course I'm taking haha.
  
  I guess what I'm wondering is if we can prove this stuff rigorously. It makes intuitive sense and I'm glad I got the intuition right but I do wonder how we know our intuition is correct.
Answers.UserDisplayName: Moo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-01T20:27:08.593Z
Answers.Text: @Moo see update- I think that addresses the Monte Carlo question, but I can't tell if anyone has done a similar proof for this algo specifically.
Answers.UserDisplayName: Maximilian Press
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-03T04:08:29.513Z
Answers.Text: Thank you for the update. I think you're right that the root of my question is why Monte Carlo algorithms work.
Answers.UserDisplayName: Moo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-23T22:10:46.620Z
Answers.LastActivityDate: 2022-01-01T20:26:37.417Z
Answers.LastEditDate: 2022-01-01T20:26:37.417Z
Answers.UserDisplayName: Maximilian Press
Body: <p>I'm looking for intuition for why a randomized motif search works. My current thinking is as follows:</p>
  <p>We are selecting many random kmers from our DNA sequences. The chosen kmers will bias the profile matrix to selecting kmers like them.</p>
  <p>Given any particular k-mer chosen, there are two possibilities:</p>
  <ol>
  <li>We've selected a meaningless kmer, so the profile will bias selecting random (ie high entropy) kmers and the score will stop improving soon.</li>
  <li>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.</li>
  </ol>
  <p>Since we give this algorithm many tries and at some point it will eventually arrive at possibility 2 and come to a good conclusion.</p>
  <p>Is this a correct understanding of why randomized motif search works? Is there a more rigorous way to prove this?</p>
  
Tags: <sequence-analysis><k-mer><algorithms><motifs>
Title: Why does randomized motif search work?
ThreadText: # Why does randomized motif search work?
  
  (Asked by: username_0 on 2021-12-22)
  
  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?
  
  **Tags:** sequence-analysis, k-mer, algorithms, motifs
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-12-23. Score: 2 | Accepted answer
  
  ## 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](https://en.wikipedia.org/wiki/Monte_Carlo_method), 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.](https://projecteuclid.org/journals/annals-of-applied-probability/volume-8/issue-2/Measure-valued-processes-and-interacting-particle-systems-Application-to-nonlinear/10.1214/aoap/1028903535.full) 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](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC312096/pdf/nar00079-0138.pdf), but they are not formal proofs.
  
  ## Original answer
  
  I believe that you are more or less correct.
  
  For example, [this presentation's](http://bix.ucsd.edu/bioalgorithms/presentations/Ch12_RandAlgs.pdf) 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](https://www.bioinformaticsalgorithms.org/bioinformatics-chapter-2).
  
  > **Comments:**
  > **username_0**: That's actually the course I'm taking haha.  I guess what I'm wondering is if we can prove this stuff rigorously. It makes intuitive sense and I'm glad I got the intuition right but I do wonder how we know our intuition is correct.  
  > **username_1**: @username_0 see update- I think that addresses the Monte Carlo question, but I can't tell if anyone has done a similar proof for this algo specifically.  
  > **username_0**: Thank you for the update. I think you're right that the root of my question is why Monte Carlo algorithms work.  
  
  ---
  
  