Bioinformatics AlgorithmsAn Active Learning Approach
You are reading the free online edition. Autograded code challenges and a certificate are in the interactive text, free to start.Solve these problems with autograders, free

Lesson 2.5

Greedy Motif Search

5 min read2 code challenges✓ Read

Watch the lectureHow Rolling Dice Helps Us Find Regulatory Motifs (Part 1)

Using the profile matrix to roll dice

Many algorithms are iterative procedures that must choose among many alternatives at each iteration. Some of these alternatives may lead to correct solutions, whereas others may not. Greedy algorithms select the “most attractive” alternative at each iteration. For example, a greedy algorithm in chess might attempt to capture an opponent’s most valuable piece at every move. Yet anyone who has played chess knows that this strategy of looking only one move ahead will likely produce disastrous results. In general, most greedy algorithms typically fail to find an exact solution of the problem; instead, they are often fast heuristics that trade accuracy for speed in order to find an approximate solution. Nevertheless, for many biological problems that we will study in this book, greedy algorithms will prove quite useful.

In this section, we will explore a greedy approach to motif finding. Again, let Motifs be a collection of k-mers taken from t strings Dna. Recall from our discussion of entropy that we can view each column of Profile(Motifs) as a four-sided biased die. Thus, a profile matrix with k columns can be viewed as a collection of k dice, which we will roll to randomly generate a k-mer. For example, if the first column of the profile matrix is (0.2, 0.1, 0.0, 0.7), then we generate A as the first nucleotide with probability 0.2, C with probability 0.1, G with probability 0.0, and T with probability 0.7.

Below, we reproduce the profile matrix for the NF-κB binding sites, where the lone colored entry in the i-th column corresponds to the i-th nucleotide in ACGGGGATTACC. The probability Pr(ACGGGGATTACC | Profile) that Profile generates ACGGGGATTACC is computed by simply multiplying the highlighted entries in the profile matrix.

Probability random string

A k-mer tends to have a higher probability when it is more similar to the consensus string of a profile. For example, for the same Profile (shown below) and its consensus string TCGGGGATTTCC:

Pr(TCGGGGATTTCC | Profile) = 0.7 · 0.6 · 1.0 · 1.0 · 0.9 · 0.9 · 0.9 · 0.5 · 0.8 · 0.7 · 0.4 · 0.6
= 0.0205753

which is larger than the value of Pr(ACGGGGATTACC | Profile) = 0.000839808 that we computed previously.

Profile matrix

Exercise Break Compute Pr(TCGTGGATTTCC | Profile), where Profile is the matrix shown above.

Given a profile matrix Profile, we can evaluate the probability of every k-mer in a string Text and find a Profile-most probable k-mer in Text, i.e., a k-mer that was most likely to have been generated by Profile among all k-mers in Text. For example, ACGGGGATTACC is the Profile-most probable 12-mer in GGTACGGGGATTACCT. Indeed, every other 12-mer in this string has probability 0. In general, if there are multiple Profile-most probable k-mers in Text, then we select the first such k-mer occurring in Text.

Profile-most Probable k-mer Problem: Find a Profile-most probable k-mer in a string.

  • Input: A string Text, an integer k, and a 4 × k matrix Profile.
  • Output: A Profile-most probable k-mer in Text.

Code Challenge Solve the Profile-most Probable k-mer Problem. (Solve at Cogniterra or Rosalind.)Solve it with the autograderFree to start in the interactive text

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.

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

Code Challenge Implement GreedyMotifSearch. (Solve at Cogniterra or Rosalind.)Solve it with the autograderFree to start in the interactive text

  • 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.

Analyzing greedy motif finding

In contrast to MedianString, GreedyMotifSearch is fast and can be run with k = 15 to solve the Subtle Motif Problem (recall that we settled for k = 13 in the case of MedianString). However, it trades speed for accuracy and returns gtAAAtAgaGatGtG (total distance: 58), which is very different from the true implanted motif AAAAAAAAGGGGGGG.

STOP and Think Why does GreedyMotifSearch (reproduced below for your convenience) perform so poorly?

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
    output BestMotifs

At first glance, GreedyMotifSearch may seem like a reasonable algorithm, but it is not! Let’s see whether GreedyMotifSearch will find the (4, 1)-motif ACGT implanted in the following strings Dna:

ttACCTtaac
gATGTctgtc
acgGCGTtag
ccctaACGAg
cgtcagAGGT

We will assume an optimistic scenario in which the algorithm has already correctly chosen the implanted 4-mer ACCT from the first string in Dna and constructed the corresponding Profile:

A: 1 0 0 0
C: 0 1 1 0
G: 0 0 0 0
T: 0 0 0 1

The algorithm is now ready to search for a Profile-most probable 4-mer in the second string. The issue, however, is that there are so many zeroes in the profile matrix that the probability of every 4-mer but ACCT is zero! Thus, unless ACCT is present in every string in Dna, there is little chance that GreedyMotifSearch will find the implanted motif. Zeroes in the profile matrix are not just a minor annoyance but rather a persistent problem that we must address.