Deamination

Solving the Minimum Skew Problem now provides us with an approximate location of ori at position 3923620 of E. coli. In an attempt to confirm this hypothesis, let's look for a hidden message representing a potential DnaA box near this location. Solving the Frequent Words Problem in a window of length 500 starting at position 3923620 (shown below) reveals no 9-mers (along with their reverse complements) that appear three or more times! Even if we have located ori in E. coli, it appears that we still have not found the DnaA boxes that jump-start replication in this bacterium …

aatgatgatgacgtcaaaaggatccggataaaacatggtgattgcctcgc ataacgcggtatgaaaatggattgaagcccgggccgtggattctactcaa ctttgtcggcttgagaaagacctgggatcctgggtattaaaaagaagatc tatttatttagagatctgttctattgtgatctcttattaggatcgcactg ccctgtggataacaaggatccggcttttaagatcaacaacctggaaagga tcattaactgtgaatgatcggtgatcctggaccgtataagctgggatcag aatgaggggttatacacaactcaaaaactgaacaacagttgttctttgga taactaccggttgatccaagcttcctgacagagttatccacagtagatcg cacgatctgtatacttatttgagtaaattaacccacgatcccagccattc ttctgccggatcttccggaatgtcgtgatcaagaatgttgatcttcagtg

STOP and Think What would you do next?

Before we give up, let’s examine the ori of Vibrio cholerae one more time to see if it provides us with any insights on how to alter our algorithm to find DnaA boxes in E. coli. You may have noticed that in addition to the three occurrences of ATGATCAAG and three occurrences of its reverse complement CTTGATCAT, the Vibrio cholerae ori contains additional occurrences of ATGATCAAC and CATGATCAT, which differ from ATGATCAAG and CTTGATCAT in only a single nucleotide:

atcaATGATCAACgtaagcttctaagcATGATCAAGgtgctcacacagtttatccacaac ctgagtggatgacatcaagataggtcgttgtatctccttcctctcgtactctcatgacca cggaaagATGATCAAGagaggatgatttcttggccatatcgcaatgaatacttgtgactt gtgcttccaattgacatcttcagcgccatattgcgctggccaaggtgacggagcgggatt acgaaagCATGATCATggctgttgttctgtttatcttgttttgactgagacttgttagga tagacggtttttcatcactgactagccaaagccttactctgcctgacatcgaccgtaaat tgataatgaatttacatgcttccgcgacgatttacctCTTGATCATcgatccgattgaag atcttcaattgttaattctcttgcctcgactcatagccatgatgagctCTTGATCATgtt tccttaaccctctattttttacggaagaATGATCAAGctgctgctCTTGATCATcgtttc

Finding eight approximate occurrences of our target 9-mer and its reverse complement in a short region is even more statistically surprising than finding the six exact occurrences of ATGATCAAG and its reverse complement CTTGATCAT that we stumbled upon in the beginning of our investigation. Furthermore, the discovery of these approximate 9-mers makes sense biologically, since DnaA can bind not only to "perfect" DnaA boxes but to their slight variations as well.

We say that position i in k-mers p₁ … p_k and q₁ … q_k is a mismatch if p_i ≠ q_i. For example, CGAAT and CGGAC have two mismatches. The number of mismatches between strings p and q is called the Hamming distance between these strings and is denoted HammingDistance(p, q).

Hamming Distance Problem: Compute the Hamming distance between two strings.

Input: Two strings of equal length.
Output: The Hamming distance between these strings.

Code ChallengeSolve the Hamming Distance Problem. (Solve on Cogniterra or Rosalind.)Solve it with the autograderFree to start in the interactive text

We say that a k-mer Pattern appears as a substring of Text with at most d mismatches if there is some k-mer substring Pattern' of Text having d or fewer mismatches with Pattern, i.e., HammingDistance(Pattern, Pattern') ≤ d. Our observation that a DnaA box may appear with slight variations leads to the following generalization of the Pattern Matching Problem.

Approximate Pattern Matching Problem: Find all approximate occurrences of a pattern in a string.

Input: Strings Pattern and Text along with an integer d.
Output: All starting positions where Pattern appears as a substring of Text with at most d mismatches.

Code Challenge Solve the Approximate Pattern Matching Problem. (Solve on Cogniterra or Rosalind.)Solve it with the autograderFree to start in the interactive text

Our goal now is to modify our previous algorithm for the Frequent Words Problem in order to find DnaA boxes by identifying frequent k-mers, possibly with mismatches. Given strings Text and Pattern as well as an integer d, we define Count_d(Text, Pattern) as the total number of occurrences of Pattern in Text with at most d mismatches. For example, Count₁(AACAAGCTGATAAACATTTAAAGAG, AAAAA) = 4 because AAAAA appears four times in this string with at most one mismatch: AACAA, ATAAA, AAACA, and AAAGA. Note that two of these occurrences overlap.

Exercise Break Compute Count₂(AACAAGCTGATAAACATTTAAAGAG, AAAAA).

Computing Count_d(Text, Pattern) simply requires us to compute the Hamming distance between Pattern and every k-mer substring of Text, which is achieved by the following pseudocode.

ApproximatePatternCount(Text, Pattern, d)
    count ← 0
    for i ← 0 to |Text| − |Pattern|
        Pattern′ ← Text(i , |Pattern|)
        if HammingDistance(Pattern, Pattern′) ≤ d
            count ← count + 1
    return count

STOP and Think What is the running time of ApproximatePatternCount?

Code Challenge Implement ApproximatePatternCount. (Solve on Cogniterra.)
Solve it with the autograderFree to start in the interactive text

Input: Strings Pattern and Text as well as an integer d.
Output: Count_d(Text, Pattern).

A most frequent k-mer with up to d mismatches in Text is simply a string Pattern maximizing Count_d(Text, Pattern) among all k-mers. Note that Pattern does not need to actually appear as a substring of Text; for example, as we already saw, AAAAA is the most frequent 5-mer with 1 mismatch in AACAAGCTGATAAACATTTAAAGAG, even though it does not appear exactly in this string. We will need to keep this in mind while solving the following problem.

Frequent Words with Mismatches Problem: Find the most frequent k-mers with mismatches in a string.

Input: A string Text as well as integers k and d. (You may assume k ≤ 12 and d ≤ 3.)
Output: All most frequent k-mers with up to d mismatches in Text.

One way to solve the Frequent Words with Mismatches problem is to generate all 4^k k-mers Pattern, compute ApproximatePatternCount(Text, Pattern, d) for each k-mer Pattern, and then find k-mers with the maximum number of approximate occurrences. This is an inefficient approach in practice, since many of the 4^k k-mers should not be considered because neither they nor their mutated versions (with up to d mismatches) appear in Text.

Instead, the following pseudocode will generalize the BetterFrequentWords function and its use of the frequency table. It uses a single map that counts the number of times a given string has an approximate match in Text. For a given k-mer substring Pattern of Text, we need to increase 1 to the count of every k-mer that has Hamming distance at most d from Pattern. The collection of all such k-mers is called the d-neighborhood of Pattern, denoted Neighbors(Pattern, d). Check out "Charging Station: Generating the Neighborhood of a String" in the print companion or at Cogniterra to learn how to implement Neighbors.


FrequentWordsWithMismatches(Text, k, d)
    Patterns ← an array of strings of length 0
    freqMap ← empty map
    n ← |Text|
    for i ← 0 to n - k
        Pattern ← Text(i, k)
        neighborhood ← Neighbors(Pattern, d)
        for j ← 0 to |neighborhood| - 1
            neighbor ← neighborhood[j]
            if freqMap[neighbor] doesn't exist
                freqMap[neighbor] ← 1
            else
                freqMap[neighbor] ← freqMap[neighbor] + 1
    m ← MaxMap(freqMap)
    for every key Pattern in freqMap
        if freqMap[Pattern] = m
            append Pattern to Patterns
    return Patterns

Code Challenge Solve the Frequent Words with Mismatches Problem. (Solve on Cogniterra or Rosalind.)Solve it with the autograderFree to start in the interactive text

We now redefine the Frequent Words Problem to account for both mismatches and reverse complements. Recall that Pattern_rc refers to the reverse complement of Pattern.

Frequent Words with Mismatches and Reverse Complements Problem: Find the most frequent k-mers (with mismatches and reverse complements) in a string.

Input: A DNA string Text as well as integers k and d.
Output: All k-mers Pattern maximizing the sum Count_d(Text, Pattern)+ Count_d(Text, Pattern_rc) over all possible k-mers.

Code Challenge Solve the Frequent Words with Mismatches and Reverse Complements Problem. (Solve on Cogniterra or Rosalind.) Solve it with the autograderFree to start in the interactive text

Some Hidden Messages are More Elusive than Others

Deamination