# Help Understanding the Greedy Motif Search Algorithm from Textbook

I am trying to go through this text book on Bioinformatics: https://www.bioinformaticsalgorithms.org. It has coding challenges and problems which I hadn't had too much trouble with until I got to the greedy motif search problem.

It is described in the book as such:

Our proposed greedy motif search algorithm, GreedyMotifSearch, starts by forming a motif matrix from arbitrarily selected k-mers in each string from Dna (which in our specific implementation is the first k-mer in each string). It then attempts to improve this initial motif matrix by trying each of the k-mers in Dna1 as the first motif. For a given choice of k-mer Motif1 in Dna1, it builds a profile matrix Profile for this lone k-mer, and sets Motif2 equal to the Profile-most probable k-mer in Dna2. It then iterates by updating Profile as the profile matrix formed from Motif1 and Motif2, and sets Motif3 equal to the Profile-most probable k-mer in Dna3. In general, after finding i − 1 k-mers Motifs in the first i − 1 strings of Dna, GreedyMotifSearch constructs Profile(Motifs) and selects the Profile-most probable k-mer from Dnai based on this profile matrix. After obtaining a k-mer from each string to obtain a collection Motifs, GreedyMotifSearch tests to see whether Motifs outscores the current best scoring collection of motifs and then moves Motif1 one symbol over in Dna1, beginning the entire process of generating Motifs again.

Pseudocode is also given:

GreedyMotifSearch(Dna, k, t)
BestMotifs ← motif matrix formed by first k-mers in each string from Dna
for each k-mer Motif in the first string from Dna
Motif1 ← Motif
for i = 2 to t
form Profile from motifs Motif1, …, Motifi - 1
Motifi ← Profile-most probable k-mer in the i-th string in Dna
Motifs ← (Motif1, …, Motift)
if Score(Motifs) < Score(BestMotifs)
BestMotifs ← Motifs
return BestMotifs


With this note:

Input: Integers k and t, followed by a collection of strings Dna. Output: A collection of strings BestMotifs resulting from applying GreedyMotifSearch(Dna, k, t). If at any step you find more than one Profile-most probable k-mer in a given string, use the one occurring first.

I've exhausted other resources trying to understand this at the moment. The Output description basically says "the output is the strings which are output by this function" which is less than helpful. I don't understand what the 't' parameter is for, other than what appears to be an arbitrary iteration stopping point.

"For a given choice of k-mer Motif1 in Dna1, it builds a profile matrix Profile for this lone k-mer, and sets Motif2 equal to the Profile-most probable k-mer in Dna2." is the sentence where the text completely loses me. This is equivalent section in the pseudocode.

for each k-mer Motif in the first string from Dna
Motif1 ← Motif


What is a k-mer motif? As far as I know, so far in the text, we have seen k-mers, we have seen them used to find motifs, we have seen profile-most probable k-mers, but at no point has anything been described as a k-mer motif. If someone has already gone through this book who could break down what it means in more detail it would be much appreciated.

EDIT: Just a note if anyone wants to tackle this problem and isn't already going through the textbook, the chapter in the book that I linked is free to access (as are the other 4 of the first 5 chapters in the book) and the section with this particular coding challenge is chapter 2.5: Greedy Motif Search. [ Lesson 2.5 ] (https://www.bioinformaticsalgorithms.org/bioinformatics-chapter-2)

I have been similarly stuck on the Bioinformatics textbook motif problems in Rosalind, mostly because the documentation included with the problems is sparse, useless, or nonexistent.

The mouseover for "motif" in the SIMS problem calls a motif "a nucleotide or amino acid pattern of biological significance". In other words, a sequence/pattern that is being searched for inside another sequence.

What is a k-mer motif?

The pseudo-code doesn't have any punctuation to help understand it. In the code, Motif is the name of the variable used in the loop, and k-mer describes the elements of the sequence array.

In other words, "For each k-mer, Motif, in the first string from DNA..."

Consider the example input presented in the Rosalind GreedyMotifSearch problem (which should look familiar):

3 5 # kmer size of 3; 5 strings within the set of strings called "DNA"
GGCGTTCAGGCA
AAGAATCAGTCA
CAAGGAGTTCGC
CACGTCAATCAC
CAATAATATTCG


So in the first string from DNA, GGCGTTCAGGCA, the set of k-mers that represents possible motifs is [GGC, GCG, CGT, GTT, TTC, TCA, CAG, AGG, GGC, GCA]. These are processed as the variable Motif in the loops of the GreedyMotifSearch pseudo-code.

I figured this out after rereading the chapter a few times. I am going to try my best to describe the solution here for anyone else who runs into this issue, since I don't think this was meant to be as difficult for the reader as it is, or at least as it was for me, especially since the function is described as "simple" in this video by the authors: Author's video on this section of the book. The part on GreedyMotifSearch is right at the end and lasts roughly a minute. Firstly, to clear up the input and output information:

Input: Integers k and t, followed by a collection of strings Dna. Output: A collection of strings BestMotifs resulting from applying GreedyMotifSearch(Dna, k, t). If at any step you find more than one Profile-most probable k-mer in a given string, use the one occurring first.

In defense of the writers of this, it had been a while since I had completed chapter 1 of this textbook, so maybe I just forgot the formatting that they had been using already. Regardless, I think the output explanation is still mostly void of helpful context.

Input:

• dna: a list of dna strings to find motifs in
• k: the character size of the motifs to be found in each string in dna
• t: the number of strings that will be passed into the function. Maybe this is an easy way to do things in other coding languages, but I am using python. For me, it was more readable to remove this parameter and just reference the length of the dna parameter when I needed it using len(dna)

Output:

• This is a list of motifs, one for each string passed in. The idea is to minimize the score of a list of kmers from each string in dna, and return the kmers that resulted in that minimum score. For me, Gringer's comment above helped a lot to clarify this.

Here is my version of the pseudocode:

GreedyMotifSeach(dna, k)
best_motifs <- arbitrarily set to the first kmer in each string in dna
for each 'kmer' in the first string in dna
potential_better_motifs <- one item list containing 'kmer'
potential_better_motifs_profile <- generate_profile_matrix(potentially_better_motifs)
for string in len(dna) #  except for the first string. This is where the original pseudocode uses the t parameter.
potential_better_motifs <- append the result of find_most_probable_kmer(dna[i], k, potentially_better_motifs_profile)
potential_better_motifs_profile <- generate_profile_matrix(potential_better_motifs)
if generate_score(potential_better_motifs) < generate_score(best_motifs)
best_motifs <- potential_better_motifs
return best_motifs


So the part that I got lost at from my initial post:

"For a given choice of k-mer Motif1 in Dna1, it builds a profile matrix Profile for this lone k-mer, and sets Motif2 equal to the Profile-most probable k-mer in Dna2." is the sentence where the text completely loses me. This is equivalent section in the pseudocode.

Described the setting up of the potential_better_motifs and potential_better_motifs_profile variables which are changed throughout the internal loop, which goes through all of the strings in dna except for the first one.

For each kmer in the first string, a profile is built, so we always start with a profile matrix of 1s and 0s, since there is only one kmer that the profile is calculated from. Based on that profile a kmer is pulled from the second string. Then a profile is built from the those two kmers and from that a kmer is pulled from the third string. Rinse and repeat this process until you have a set of kmers, or motifs, from all strings in dna. This is greedy in the sense that the algorithm is only looking one move ahead, with only one kmer from string 1 being used to form a profile that finds the best kmer in string 2, only 2 strings being used to form a profile that finds the best kmer in string 3, etc.

With a new list of potentially_better_motifs, you need a way to compare your motifs to the best_motifs. To do this, generate a consensus string from the potentially_better_motif_profile, then count how many times that each string in your potentially_better_motifs differ from that consensus string. That count is your score for your potentially_better_motifs. Repeat this scoring process for your best_motifs, then compare the two scores. If the new motif set has a score that is lower (since this is a minimization problem, lower score == better consensus match to the profile), then you have a new set of best_motifs.

Repeat this whole process for each kmer in the first string in dna, then the function ends.

There are a lot of helper functions that I don't have pseudocode for. I think the book does a good job at describing how to implement these, and if I were to go through them all I would be coming close to rewriting the whole chapter in this post, but these are the helper functions that I used and their parameters.

• find_most_probable_kmer(string, k, profile_matrix)
• generate_count_matrix(kmers)
• generate_profile_matrix(kmers)
• generate_consensus_string(profile_matrix)
• generate_score(kmers)

I chose to have generate_count_matrix be a helper for generate_profile_matrix. On top of using generate_profile_matrix within the GreedyMotifSearch, will likely be useful for you in generate_score. The parameters I used for most of these are just how I went about implementing this, so there is probably a more efficient method, but the parameters for find_most_probable_kmer are directly from the book, since that was the previous coding challenge. It is definitely worth noting the exact parameters for it, since those went a long way in helping me understand the core for loop in the GreedyMotifSearch function.