Looking for hidden messages in multiple genomes

We should not jump to the conclusion that ATGATCAAG/CTTGATCAT is a hidden message for all bacterial genomes without first checking whether it even appears in known ori regions from other bacteria. After all, maybe the clumping effect of ATGATCAAG/CTTGATCAT in the ori region of Vibrio cholerae is simply a statistical fluke that has nothing to do with replication. Or maybe different bacteria have different DnaA boxes…

Let's check the proposed ori region of Thermotoga petrophila, a bacterium that thrives in extremely hot environments; its name derives from its discovery in the water beneath oil reservoirs, where temperatures can exceed 80° Celsius.

aactctatacctcctttttgtcgaatttgtgtgatttatagagaaaatcttattaactga aactaaaatggtaggtttggtggtaggttttgtgtacattttgtagtatctgatttttaa ttacataccgtatattgtattaaattgacgaacaattgcatggaattgaatatatgcaaa acaaacctaccaccaaactctgtattgaccattttaggacaacttcagggtggtaggttt ctgaagctctcatcaatagactattttagtctttacaaacaatattaccgttcagattca agattctacaacgctgttttaatgggcgttgcagaaaacttaccacctaaaatccagtat ccaagccgatttcagagaaacctaccacttacctaccacttacctaccacccgggtggta agttgcagacattattaaaaacctcatcagaagcttgttcaaaaatttcaatactcgaaa cctaccacctgcgtcccctattatttactactactaataatagcagtataattgatctga

This region does not contain a single occurrence of ATGATCAAG or CTTGATCAT! Thus, different bacteria may use different DnaA boxes as "hidden messages" to the DnaA protein.

Application of our algorithm solving the Frequent Words Problem to the ori region above reveals that the following six 9-mers appear in this region 3 or more times:

AACCTACCA AAACCTACC ACCTACCAC CCTACCACC GGTAGGTTT TGGTAGGTT

Something peculiar must be happening because it is extremely unlikely that six different 9-mers will occur so frequently within the same short region in a random string. We will cheat a little and consult with Ori-Finder, a software tool for finding replication origins in DNA sequences. This software chooses CCTACCACC (along with its reverse complement GGTGGTAGG) as a working hypothesis for the DnaA box in Thermotoga petrophila. Together, these two complementary 9-mers appear five times in the replication origin:

aactctatacctcctttttgtcgaatttgtgtgatttatagagaaaatcttattaactga aactaaaatggtaggtttGGTGGTAGGttttgtgtacattttgtagtatctgatttttaa ttacataccgtatattgtattaaattgacgaacaattgcatggaattgaatatatgcaaa acaaaCCTACCACCaaactctgtattgaccattttaggacaacttcagGGTGGTAGGttt ctgaagctctcatcaatagactattttagtctttacaaacaatattaccgttcagattca agattctacaacgctgttttaatgggcgttgcagaaaacttaccacctaaaatccagtat ccaagccgatttcagagaaacctaccacttacctaccacttaCCTACCACCcgggtggta agttgcagacattattaaaaacctcatcagaagcttgttcaaaaatttcaatactcgaaa CCTACCACCtgcgtcccctattatttactactactaataatagcagtataattgatctga

The Clump Finding Problem

Now imagine that you are trying to find ori in a newly sequenced bacterial genome. Searching for “clumps” of either ATGATCAAG /CTTGATCAT or CCTACCACC/GGTGGTAGG is unlikely to help, since this new genome may use a completely different hidden message! Before we lose all hope, let’s change our computational focus: instead of finding clumps of a specific k-mer, let’s try to find every k-mer that forms a clump in the genome. Hopefully, the locations of these clumps will shed light on the location of ori.

Our plan is to slide a window of fixed length L along the genome, looking for a region where a k-mer appears several times in short succession. The parameter value L = 500 reflects the typical length of ori in bacterial genomes.

We defined a k-mer as a "clump" if it appears many times within a short interval of the genome. More formally, given integers L and t, a k-mer Pattern forms an (L, t)-clump inside a (longer) string Genome if there is an interval of Genome of length L in which this k-mer appears at least t times. (This definition assumes that the k-mer completely fits within the interval. This also does not take reverse complements into account yet.) For example, TGCA forms a (25,3)-clump in the following Genome:

gatcagcataagggtccCTGCAATGCATGACAAGCCTGCAGTtgttttac

From our previous examples of ori regions, ATGATCAAG forms a (500,3)-clump in the Vibrio cholerae genome, and CCTACCACC forms a (500,3)-clump in the Thermotoga petrophila genome. We are now ready to formulate the following problem.

Clump Finding Problem: Find patterns forming clumps in a string.

Input: A string Genome, and integers k, L, and t.
Output: All distinct k-mers forming (L, t)-clumps in Genome.

The Clump Finding Problem is a more complex problem than we have encountered thus far, and writing a function solving it from scratch would be difficult. However, this is where modularity in writing programs is so helpful. We already have a FrequencyTable function that will produce a frequency table for a given window of a string of length L. If we apply it to a given window, then we simply need to check if there are any string keys in the table whose values are at least equal to t. We will append any such keys that we have not already seen in some other window of Text to a growing list of strings. In the end, this list of strings will contain the (L, t)-clumps of Text. This is handled by the following FindClumps function.


FindClumps(Text, k, L, t)
    Patterns ← an array of strings of length 0
    n ← |Text|
    for every integer i between 0 and n − L
        Window ← Text(i, L)
        freqMap ← FrequencyTable(Window, k)
        for every key s in freqMap
            if freqMap[s] ≥ t
                append s to Patterns
    remove duplicates from Patterns
    return Patterns

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

Exercise Break: If you think your solution to the Clump Finding Problem is efficient enough, try it out on the E. coli genome, the workhorse of bacterial genomics. How many different 9-mers form (500,3)-clumps in the E. coli genome? (In other words, do not count a 9-mer more than once.)

Download Genome (4.6 MB)

We find hundreds of different 9-mers forming (500,3)-clumps in the E. coli genome, and it is absolutely unclear which of these 9-mers might represent a DnaA box in the bacterium’s ori region.

At this point, an unseasoned researcher might give up, since it appears that we do not have enough information to locate ori in E. coli. But a fearless veteran bioinformatician would try to learn more about the details of replication in the hope that they provide new algorithmic insights into finding ori.

An Explosion of Hidden Messages

Looking for hidden messages in multiple genomes

The Clump Finding Problem