Lesson 2.4

From Motif Finding to Finding a Median String

8 min read1 code challenge✓ Read

Watch the lectureFrom Implanted Patterns to Regulatory Motifs (Part 3)

The Motif Finding Problem

Now that we have a good grasp of scoring a collection of k-mers, we are ready to formulate the Motif Finding Problem.

Motif Finding Problem: Given a collection of strings, find a set of k-mers, one from each string, that minimizes the score of the resulting motif.

• Input: A collection of strings Dna and an integer k.
• Output: A collection Motifs of k-mers, one from each string in Dna, minimizing Score(Motifs) among all possible choices of k-mers.

A brute force algorithm for the Motif Finding Problem (referred to as BruteForceMotifSearch) considers every possible choice of k-mers Motifs from Dna (one k-mer from each string of n nucleotides) and returns the collection Motifs having minimum score. Because there are n - k + 1 choices of k-mers in each of t sequences, there are (n - k + 1)^t different ways to form Motifs. For each choice of Motifs, the algorithm calculates Score(Motifs), which requires k · t steps. Thus, assuming that k is smaller than n, the overall running time of the algorithm is O(n^t · k · t). We need to come up with a faster algorithm!

Reformulating the Motif Finding Problem

Because BruteForceMotifSearch is inefficient, we will think about motif finding in a different way. Instead of exploring all Motifs in Dna and deriving the consensus string from Motifs afterwards:

Motifs → Consensus(Motifs),

we will explore all potential k-mer consensus strings first and then find the best possible collection Motifs for each consensus string:

Consensus(Motifs) → Motifs.

To reformulate the motif finding problem, we need to devise an alternative way of computing Score(Motifs). Until now, we have computed Score(Motifs), the number of lower case letters in the motif matrix, column-by-column. For example, we previously computed the score of the NF-κB motif matrix as 3 + 4 + 0 + 0 + 1 + 1 + 1 + 5 + 2 + 3 + 6 + 4 = 30. The figure below illustrates that Score(Motifs) can just as easily be computed row-by-row (3 + 4 + 2 + 4 + 3 + 2 + 3 + 2 + 4 + 3 = 30). Note that each element in the latter sum represents the number of mismatches between the consensus string TCGGGGATTTCC and a motif in the corresponding row of the motif matrix, i.e., the Hamming distance between these strings. For the first row of the motif matrix below, d(TCGGGGATTTCC, TCGGGGgTTTtt) = 3.

Figure: The motif and score matrices in addition to consensus string for the NF-κB binding sites. Rather than add the non-consensus elements (i.e., lower case nucleotides) column-by-column, we can add them row-by-row, as highlighted on the right of the motifs matrix. Each value at the end of a row corresponds to the Hamming distance between that row and the consensus string.

Given a collection of k-mers Motifs = {Motif₁, … , Motif_t} and a k-mer Pattern, we now define d(Pattern, Motifs) as the sum of Hamming distances between Pattern and each Motif_i:

d(Pattern, Motifs) = Σ_i=1^t HammingDistance(Pattern, Motif_i).

Because Score(Motifs) corresponds to counting the lower case elements of Motifs column-by-column and d(Consensus(Motifs), Motifs) corresponds to counting these elements row-by-row, we obtain that

Score(Motifs) = d(Consensus(Motifs), Motifs).

This equation gives us an idea. Instead of searching for a collection of k-mers Motifs minimizing

Score(Motifs)

let's instead search for a potential consensus string Pattern minimizing

d(Pattern, Motifs)

among all possible k-mers Pattern and all possible choices of k-mers Motifs in Dna. This problem is equivalent to the Motif Finding Problem.

Equivalent Motif Finding Problem: Given a collection of strings, find a collection of k-mers (one from each string) that minimizes the distance between all possible patterns and all possible collections of k-mers.

• Input: A collection of strings Dna and an integer k.
• Output: A k-mer Pattern and a collection of k-mers, one from each string in Dna, minimizing d(Pattern, Motifs) among all possible choices of Pattern and Motifs.

The Median String Problem

But wait a second — have we not just made our task more difficult? Instead of having to search for all Motifs, we now have to search all Motifs as well as all k-mers Pattern. The key observation for solving the Equivalent Motif Finding Problem is that, given Pattern, we don’t need to explore all possible collections Motifs in order to minimize d(Pattern, Motifs).

To explain how this can be done, we define Motifs(Pattern, Dna) as a collection of k-mers that minimizes d(Pattern, Motifs) for a given Pattern and all possible sets of k-mers Motifs in Dna. For example, for the strings Dna shown below, the five colored 3-mers represent Motifs(AAA, Dna).

STOP and Think Given a collection of strings Dna and a k-mer Pattern, design a fast algorithm for generating Motifs(Pattern, Dna).

The reason why we don’t need to consider all possible collections Motifs in Dna = Dna₁, ..., Dna_t is that we can generate the k-mers in Motifs(Pattern, Dna) one at a time; that is, we can select a k-mer in Dna_i independently of selecting k-mers in all other strings in Dna. Given a k-mer Pattern and a longer string Text, we use d(Pattern, Text) to denote the minimum Hamming distance between Pattern and any k-mer in Text,

d(Pattern, Text) = min_{all k-mers Pattern' in Text} HammingDistance(Pattern, Pattern')

For example,

d(GATTCTCA, GCAAAGACGCTGACCAA) = 3.

A k-mer in Text that achieves the minimum Hamming distance with Pattern is denoted Motif(Pattern, Text). For the above example,

Motif(GATTCTCA, GCAAAGACGCTGACCAA) = GACGCTGA.

We note that the notation Motif(Pattern, Text) is ambiguous because there may be multiple k-mers in Text that achieve the minimum Hamming distance with Pattern. For example, Motif(AAG, GCAATCCTCAGC) could be either AAT or CAG. If there are multiple k-mers in Text having minimum Hamming distance with Pattern, we select the first such k-mer in Text as Motif(Pattern, Text).

Given a k-mer Pattern and a set of strings Dna = {Dna₁, … , Dna_t}, we define d(Pattern, Dna) as the sum of distances between Pattern and all strings in Dna,

d(Pattern, Dna) = Σ_i=1^t d(Pattern, Dna _i ) .

For example, for the strings Dna shown below, d(AAA, Dna) = 1 + 1 + 2 + 0 + 1 = 5.

Our goal is to find a k-mer Pattern that minimizes d(Pattern, Dna) over all k-mers Pattern, the same task that the Equivalent Motif Finding Problem is trying to achieve. We call such a k-mer a median string for Dna.

Median String Problem: Find a median string.

• Input: A collection of strings Dna and an integer k.
• Output: A k-mer Pattern that minimizes d(Pattern, Dna) among all possible choices of k-mers.

Notice that finding a median string requires solving a double minimization problem. We must find a k-mer Pattern that minimizes d(Pattern, Dna), where this function is itself computed by taking a minimum over all choices of k-mers from each string in Dna.

We now give the pseudocode for a brute force solution to the Median String Problem.

MedianString(Dna, k)
    distance ← ∞
    Median ← ""
    for each k-mer Pattern from AA…AA to TT…TT
        if distance > d(Pattern, Dna)
                distance ← d(Pattern, Dna)
                Median ← Pattern
    return Median

Although this pseudocode is short, it is not without potential pitfalls. Check out "Charging Station: Solving the Median String Problem" in the print companion or at Cogniterra if you fall into one of them.

STOP and Think Instead of making a time-consuming search through all possible k-mers in MedianString, can you only search through all k-mers that appear in Dna?

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

• Input: An integer k, followed by a collection of strings Dna.
• Output: A k-mer Pattern that minimizes d(Pattern, Dna) among all possible choices of k-mers. (If there are multiple such strings Pattern, then you may return any one.)

Why have we reformulated the Motif Finding Problem?

To see why we reformulated the Motif Finding Problem as the equivalent Median String Problem, consider the runtime of MedianString and BruteForceMotifSearch. The former algorithm computes d(Pattern, Dna) for each of the 4^k k-mers Pattern. Each computation of d(Pattern, Dna) requires a single pass over each string in Dna, which requires approximately k · n · t operations for t strings of length n in Dna. Therefore, MedianString has a running time of O(4^k · n · k · t), which in practice compares favorably with the O(n^t · k · t) running time of BruteForceMotifSearch because the length of a motif (k) typically does not exceed 20 nucleotides, whereas t is measured in the thousands.

The Median String Problem teaches an important lesson, which is that sometimes rethinking how a problem is formulated can lead to dramatic improvements in the runtime required to solve it. In this case, our simple observation that Score(Motifs) could just as easily be computed row-by-row as column-by-column produced the faster MedianString algorithm.

Of course, the ultimate test of a bioinformatics algorithm is how it performs in practice. Unfortunately, since MedianString has to consider 4^k k-mers, it becomes too slow for the Subtle Motif Problem, for which k = 15. We will run MedianString with k = 13 in the hope that it will capture a substring of the correct 15-mer motif. The algorithm still requires half a day to run on our computer and returns the median string AAAAAtAGaGGGG (with distance 29). This 13-mer is not a substring of the implanted pattern AAAAAAAAGGGGGGG, but it does come close.

STOP and Think How can a slightly incorrect median string of length 13 help us find the correct median string of length 15?

We have thus far assumed that the value of k is known in advance, which is not the case in practice. As a result, we are forced to run our motif finding algorithms for different values of k and then try to deduce the correct motif length. Since some regulatory motifs are rather long — later in the chapter, we will search for a biologically important motif of length 20 — MedianString may be too slow to find them.