<blockquote>
<p>...the moment you generate a profile matrix based on a list of most-probable-k-mers, that matrix will simply comb through the Dna strings and identify the same most-probable-k-mers, and <em><strong>this will perpetuate itself endlessly with your score never improving.</strong></em></p>
</blockquote>
<p>If the score doesn't improve, then the algorithm should terminate immediately, because the comparison for continuing is <code>&lt;</code> [less than] rather than <code>&lt;=</code> [less than or equal to].</p>

CC BY-SA 4.0
2024-07-06T21:43:20.790Z
2024-07-06T21:43:20.790Z
gringer
<p>I’m struggling to understand this problem in Week 2 of Cogniterra’s Bioinformatics Algorithms course. It is the Randomized Motif Search problem, which prompts the user with the following pseudocode:</p>
<pre><code>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) &lt; Score(BestMotifs)
            BestMotifs ← Motifs
        else
            return BestMotifs
</code></pre>
<p>I have spent many many hours of time over several days on this problem, but I am wrestling with the logic of the algorithm. The pseudocode seems to hint that the following steps must be done:</p>
<ol>
<li>Generate a random set of k-mers, one kmer per strand of Dna. No problem.</li>
<li>Enter a loop that uses the random k-mers to form a profile probability matrix. Again no problem.</li>
<li>Use the values in the matrix to find the most probable kmers in the Dna strings, one k-mer per string, outputting a list of k-mers (motifs) equal in number to the randomly-generated k-mer list. Also not a problem.</li>
<li>Use the profile matrix to score both the random k-mers and the matrix-selected k-mers.</li>
<li>Take the lower scoring value (list of k-mers that has more alignment — fewer differences - with the consensus string of the profile matrix) and store in ‘best_motifs’.</li>
<li>Loop the code up to the start of the while loop, meaning you will use the ‘best_motifs’ to make a new profile matrix, which will then generate a new list of most-probable-kmers.</li>
<li>Continue to take the lowest-scoring list of kmers, and continue to loop.  End up with the global best motifs in all the dna strings. In other words, the final output of motifs should compute to the same list of k-mers every time.</li>
</ol>
<p>Here’s my problem.  After the very first round of finding the most-probable-k-mers, the code seems to essentially get stuck, looping and looping and pumping out the exact same list of kmers over and over. This seems to occur because the moment you generate a profile matrix based on a list of most-probable-k-mers, that matrix will simply comb through the Dna strings and identify the same most-probable-k-mers, and this will perpetuate itself endlessly with your score never improving.</p>
<p>I tried a different algorithm that I thought would make way more sense, but so far, it has failed to produce the desired output of the debug dataset provided by the course. None-the-less, here are my thoughts.  The provided pseudocode and it’s inherent algorithm seems flawed because if you find the most-probable-k-mers based on random k-mers, then you risk forming a flawed profile matrix, that is to say, a profile matrix that produces a consensus strand that is not useful for identifying real motifs in the dna strings.</p>
<p>To solve this perceived problem, I figured that the important metric in this task was the finding the lowest score possible for a list of most-probable-k-mers generated from a profile-matrix of randomly selected k-mers.  In other words do this:  Generate random list of kmers from the Dna strings, form a profile-matrix from these, find the most-probable kmers from this matrix, then use the matrix to score the random kmers and the most-probable kmers.  Most importantly, the algorithm asks “how low is the lowest score?  Is the score lower than a benchmark score outside of the loop? If so, replace that benchmark score&quot;.  The difference between this algorithm and the course-suggested algorithm is that the generation of random kmers is <em>inside</em> the while loop, and the algorithm is interested in tracking the lowest possible score than can be generated.  It Loops 1000 times, eventually printing out the list of most-probable-mers that correspond with the lowest benchmark score. Here’s my pseudocode:</p>
<pre><code>RandomizedMotifSearch(Dna, k, t)
    lowest_score_benchmark = infinity (arbitrarily large value)
    best_motifs ← [empty list]
    loop_count ← 1000
    while loop count &gt; 0
        randoms(randomly selected k-mers) = (Motif1, …, Motift) in each string from Dna
        Profile ← Profile(randoms)
        Motifs ← Motifs(Profile, Dna) *find most probable motifs in Dna based on Profile
            if Score(Motifs) &lt; Score(randoms)
                if Score(Motifs) &lt; lowest_score_benchmark
                    best_motifs ← Motifs
                    lowest_score_benchmark ← score(Motifs)
    return best_motifs
</code></pre>
<p>This approach works in the sense that it will indeed produce k-mer lists with the lowest scores possible for the Dna string list provided. That in and of itself seems like it's a useful algorithm to solve the RandomizedMotifSearch () problem. It certainly produces motif lists with far lower scores than when I write code based on the provided pseudocode. However, the output lists change each time I run the code, suggesting that the code is converging on local minima kmers, rather than the true global minimum k-mers in the Dna list.</p>
<p>If anyone has any insight into the logic of what the course is asking, please let me know.  Thank you very much.</p>

<homework><motifs>
Randomized Motif Search - Bioinformatics Algorithms Week 2 - Cogniterra
# Randomized Motif Search - Bioinformatics Algorithms Week 2 - Cogniterra

(Asked by: username_0 on 2024-07-05)

I’m struggling to understand this problem in Week 2 of Cogniterra’s Bioinformatics Algorithms course. It is the Randomized Motif Search problem, which prompts the user with the following pseudocode:
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

I have spent many many hours of time over several days on this problem, but I am wrestling with the logic of the algorithm. The pseudocode seems to hint that the following steps must be done:

Generate a random set of k-mers, one kmer per strand of Dna. No problem.
Enter a loop that uses the random k-mers to form a profile probability matrix. Again no problem.
Use the values in the matrix to find the most probable kmers in the Dna strings, one k-mer per string, outputting a list of k-mers (motifs) equal in number to the randomly-generated k-mer list. Also not a problem.
Use the profile matrix to score both the random k-mers and the matrix-selected k-mers.
Take the lower scoring value (list of k-mers that has more alignment — fewer differences - with the consensus string of the profile matrix) and store in ‘best_motifs’.
Loop the code up to the start of the while loop, meaning you will use the ‘best_motifs’ to make a new profile matrix, which will then generate a new list of most-probable-kmers.
Continue to take the lowest-scoring list of kmers, and continue to loop.  End up with the global best motifs in all the dna strings. In other words, the final output of motifs should compute to the same list of k-mers every time.

Here’s my problem.  After the very first round of finding the most-probable-k-mers, the code seems to essentially get stuck, looping and looping and pumping out the exact same list of kmers over and over. This seems to occur because the moment you generate a profile matrix based on a list of most-probable-k-mers, that matrix will simply comb through the Dna strings and identify the same most-probable-k-mers, and this will perpetuate itself endlessly with your score never improving.
I tried a different algorithm that I thought would make way more sense, but so far, it has failed to produce the desired output of the debug dataset provided by the course. None-the-less, here are my thoughts.  The provided pseudocode and it’s inherent algorithm seems flawed because if you find the most-probable-k-mers based on random k-mers, then you risk forming a flawed profile matrix, that is to say, a profile matrix that produces a consensus strand that is not useful for identifying real motifs in the dna strings.
To solve this perceived problem, I figured that the important metric in this task was the finding the lowest score possible for a list of most-probable-k-mers generated from a profile-matrix of randomly selected k-mers.  In other words do this:  Generate random list of kmers from the Dna strings, form a profile-matrix from these, find the most-probable kmers from this matrix, then use the matrix to score the random kmers and the most-probable kmers.  Most importantly, the algorithm asks “how low is the lowest score?  Is the score lower than a benchmark score outside of the loop? If so, replace that benchmark score".  The difference between this algorithm and the course-suggested algorithm is that the generation of random kmers is inside the while loop, and the algorithm is interested in tracking the lowest possible score than can be generated.  It Loops 1000 times, eventually printing out the list of most-probable-mers that correspond with the lowest benchmark score. Here’s my pseudocode:
RandomizedMotifSearch(Dna, k, t)
    lowest_score_benchmark = infinity (arbitrarily large value)
    best_motifs ← [empty list]
    loop_count ← 1000
    while loop count > 0
        randoms(randomly selected k-mers) = (Motif1, …, Motift) in each string from Dna
        Profile ← Profile(randoms)
        Motifs ← Motifs(Profile, Dna) *find most probable motifs in Dna based on Profile
            if Score(Motifs) < Score(randoms)
                if Score(Motifs) < lowest_score_benchmark
                    best_motifs ← Motifs
                    lowest_score_benchmark ← score(Motifs)
    return best_motifs

This approach works in the sense that it will indeed produce k-mer lists with the lowest scores possible for the Dna string list provided. That in and of itself seems like it's a useful algorithm to solve the RandomizedMotifSearch () problem. It certainly produces motif lists with far lower scores than when I write code based on the provided pseudocode. However, the output lists change each time I run the code, suggesting that the code is converging on local minima kmers, rather than the true global minimum k-mers in the Dna list.
If anyone has any insight into the logic of what the course is asking, please let me know.  Thank you very much.

**Tags:** homework, motifs

---

## 1 answers

### Answer by username_1 on 2024-07-06. Score: 0

> ...the moment you generate a profile matrix based on a list of most-probable-k-mers, that matrix will simply comb through the Dna strings and identify the same most-probable-k-mers, and ***this will perpetuate itself endlessly with your score never improving.***

If the score doesn't improve, then the algorithm should terminate immediately, because the comparison for continuing is `<` [less than] rather than `<=` [less than or equal to].


---

