Lesson 1.2
Hidden Messages in the Replication Origin
Watch the lectureThe Search for Hidden Messages in the Replication Origin (Part 1)
DnaA boxes
In the rest of this chapter, we will focus on the relatively easy case of finding ori in bacterial genomes, most of which consist of a single circular chromosome. Research has shown that the region of the bacterial genome encoding ori is typically a few hundred nucleotides long. Our plan is to begin with a bacterium in which ori is known, and then determine what makes this genomic region special in order to design a computational approach for finding ori in other bacteria. Our example is Vibrio cholerae, the pathogenic bacterium that causes cholera; here is the nucleotide sequence appearing in the ori of Vibrio cholerae:
atcaatgatcaacgtaagcttctaagcatgatcaaggtgctcacacagtttatccacaac
ctgagtggatgacatcaagataggtcgttgtatctccttcctctcgtactctcatgacca
cggaaagatgatcaagagaggatgatttcttggccatatcgcaatgaatacttgtgactt
gtgcttccaattgacatcttcagcgccatattgcgctggccaaggtgacggagcgggatt
acgaaagcatgatcatggctgttgttctgtttatcttgttttgactgagacttgttagga
tagacggtttttcatcactgactagccaaagccttactctgcctgacatcgaccgtaaat
tgataatgaatttacatgcttccgcgacgatttacctcttgatcatcgatccgattgaag
atcttcaattgttaattctcttgcctcgactcatagccatgatgagctcttgatcatgtt
tccttaaccctctattttttacggaagaatgatcaagctgctgctcttgatcatcgtttc
How does the bacterial cell know to begin replication exactly in this short region within the much larger Vibrio cholerae chromosome, which consists of 1,108,250 nucleotides? There must be some “hidden message” in the ori region ordering the cell to begin replication here. Indeed, we know that the initiation of replication is mediated by DnaA, a protein that binds to a short segment within the ori known as a DnaA box. You can think of the DnaA box as a message within the DNA sequence telling the DnaA protein: “bind here!” The question is how to find this hidden message without knowing what it looks like in advance—can you find it? In other words, can you find something that stands out in ori? This discussion motivates the following problem.
Hidden Message Problem: Find a “hidden message” in the replication origin.
- Input: A string Text (representing the replication origin of a genome).
- Output: A hidden message in Text.
STOP and Think: Does the Hidden Message Problem represent a clearly stated computational problem?
Hidden messages in "The Gold-Bug"
Although the Hidden Message Problem poses a legitimate intuitive question, it again makes absolutely no sense to a computer scientist because the notion of a “hidden message” is not precisely defined. The ori region of Vibrio cholerae is currently just as puzzling as the parchment discovered by William Legrand in Edgar Allan Poe's story "The Gold-Bug". Written on the parchment was
53‡‡†305))6·;4826)4‡.)4‡);806·;48†8^60))85;161;:‡·8
†83(88)5·†;46(;88·96·?;8)·‡(;485);5·†2:·‡(;4956·2(5
·—4)8^8·;4069285);)6†8)4‡‡;1(‡9;48081;8:8‡1;48†85;4
)485†528806·81(‡9;48;(88;4(‡?34;48)4‡;1‡(;:188;‡?;
Upon seeing the parchment, the narrator remarks, "Were all the jewels of Golconda awaiting me upon my solution of this enigma, I am quite sure that I should be unable to earn them." Legrand retorts, "It may well be doubted whether human ingenuity can construct an enigma of the kind which human ingenuity may not, by proper application, resolve." He reasons that the three consecutive symbols ;48 appear with surprising frequency on the parchment.
53‡‡†305))6·;4826)4‡.)4‡);806·;48†8^60))85;161;:‡·8 †83(88)5·†;46(;88·96·?;8)·‡(;485);5·†2:·‡(;4956·2(5 ·—4)8^8·;4069285);)6†8)4‡‡;1(‡9;48081;8:8‡1;48†85;4 )485†528806·81(‡9;48;(88;4(‡?34;48)4‡;1‡(;:188;‡?;
Legrand had already deduced that the pirates spoke English; he therefore assumed that the high frequency of ;48 implied that it encodes the most frequent English word, THE. Substituting ; for T, 4 for H, and 8 for E, Legrand had a slightly easier text to decipher (shown below), which would eventually lead him to the buried treasure. Can you decode this message too?
53‡‡†305))6·THE26)H‡.)H‡)TE06·THE†E^60))E5T161T:‡·E
†E3(EE)5·†TH6(TEE·96·?TE)·‡(THE5)T5·†2:·‡(TH956·2(5
·—H)E^E·TH0692E5)T)6†E)H‡‡T1(‡9THE0E1TE:E‡1THE†E5TH )HE5†52EE06·E1(‡9THET(EETH(‡?3HTHE)H‡T1‡(T:1EET‡?T
Counting words
Operating under the assumption that DNA is a language of its own, let's borrow Legrand's method and see if we can find any surprisingly frequent "words" within the ori of Vibrio cholerae. We have added reason to look for frequent words in the ori because for various biological processes, certain nucleotide strings often appear surprisingly often in small regions of the genome. This is often because certain proteins can only bind to DNA if a specific string of nucleotides is present, and if there are more occurrences of the string, then it is more likely that binding will successfully occur. (It is also less likely that a mutation will disrupt the binding process.)
For example, ACTAT is a surprisingly frequent substring of ACAACTATGCATACTATCGGGAACTATCCT.
We will use the term k-mer to refer to a string of length k and define Count(Text, Pattern) as the number of times that a k-mer Pattern appears as a substring of Text. Following the above example,
Count(ACAACTATGCATACTATCGGGAACTATCCT, ACTAT) = 3.
We note that Count(CGATATATCCATAG, ATA) is equal to 3 (not 2) since we should account for overlapping occurrences of Pattern in Text.
To compute Count(Text, Pattern), our plan is to “slide a window” down Text, checking whether each k-mer substring of Text matches Pattern. We will therefore refer to the k-mer starting at position i of Text as Text(i, k). Throughout this book, we will often use 0-based indexing, meaning that we count starting at 0 instead of 1. In this case, Text begins at position 0 and ends at position |Text| − 1 (|Text| denotes the number of symbols in Text). For example, if Text = GACCATACTG, then Text(4, 3) = ATA. Note that the last k-mer of Text begins at position |Text| − k, e.g., the last 3-mer of GACCATACTG starts at position 10 − 3 = 7. This discussion results in the following pseudocode for computing Count(Text, Pattern).
Important Note: We do not assume that you know how to program; we only expect you to program. However, we do need to communicate the computational methods used in modern biology. To do so, we will use the language of pseudocode, which is more precise than human language. Please click here for an overview of pseudocode.
PatternCount(Text, Pattern)
count ← 0
for i ← 0 to |Text| − |Pattern|
if Text(i, |Pattern|) = Pattern
count ← count + 1
return countWe now will encounter our first "Code Challenge" assessment. You can complete these challenges in any programming language as part of the interactive version of this textbook at Cogniterra. If you haven't programmed before and are interested in learning how, we suggest our "Biology Meets Programming" course.
Code Challenge Implement PatternCount. (Solve at Cogniterra or Rosalind.)
Input: Strings Text and Pattern.
Output: Count(Text, Pattern).Solve it with the autograderFree to start in the interactive text
The Frequent Words Problem
We say that Pattern is a most frequent k-mer in Text if it maximizes Count(Text, Pattern) among all k-mers. You can see that ACTAT is a most frequent 5-mer of ACAACTATGCATACTATCGGGAACTATCCT, and ATA is a most frequent 3-mer of CGATATATCCATAG.
STOP and Think: Can a string have multiple most frequent k-mers?
We now have a rigorously defined computational problem.
Frequent Words Problem: Find the most frequent k-mers in a string.
- Input: A string Text and an integer k.
- Output: All most frequent k-mers in Text.
A straightforward algorithm for finding the most frequent k-mers in a string Text checks all k-mers appearing in this string (there are |Text| − k + 1 such k-mers) and then computes how many times each k-mer appears in Text. To implement this algorithm, called FrequentWords, we will need to generate an array Count, where Count(i) stores Count(Text, Pattern) for Pattern = Text(i, k) (see figure below).
Figure: The array Count for Text = ACTGACTCCCACCCC and k = 3. For example, Count(0) = Count(4) = 2 because ACT (shown in boldface) appears twice in Text.
The pseudocode for FrequentWords is shown below.
FrequentWords(Text, k)
FrequentPatterns ← an empty set
Count ← an array of length |Text|-k+1
for i ← 0 to |Text| − k
Pattern ← Text(i, k)
Count(i) ← PatternCount(Text, Pattern)
maxCount ← maximum value in array Count
for i ← 0 to |Text| − k
if Count(i) = maxCount
add Text(i, k) to FrequentPatterns
remove duplicates from FrequentPatterns
return FrequentPatternsSTOP and Think Take another look at the pseudocode for FrequentWords (especially if your algorithm for the Frequent Words Problem took time to run). How fast is this algorithm?
Although FrequentWords finds most frequent k-mers, it is not very efficient. Each call to PatternCount(Text, Pattern) checks whether the k-mer Pattern appears in position 0 of Text, position 1 of Text, and so on. Since each k-mer requires |Text| − k + 1 such checks, each one requiring as many as k comparisons, the overall number of steps of PatternCount(Text, Pattern) is (|Text| − k + 1) · k. Furthermore, FrequentWords must call PatternCount |Text| − k + 1 times (once for each k-mer of Text), so that its overall number of steps is (|Text| − k + 1) · (|Text| − k + 1) · k. To simplify the matter, computer scientists often say that the runtime of FrequentWords has an upper bound of |Text|2 · k steps and refer to the complexity of this algorithm as O(|Text|2 · k). For more details, see "DETOUR: Big-O Notation" in the print companion or at Cogniterra.
If |Text| and k are small, as is the case when looking for DnaA boxes in the typical bacterial ori, then an algorithm with running time of O(|Text|2 · k) is perfectly acceptable. But once we find some new biological application requiring us to solve the Frequent Words Problem for a very long Text, we will quickly run into trouble. What can we do instead?
A Faster Frequent Words Approach
If you were to solve the Frequent Words Problem by hand for a small example, you would probably form a table like the one in the figure below for Text equal to "ACGTTTCACGTTTTACGG" and k equal to 3. You would slide a length-k window Text, and if the current k-mer substring of text does not occur in the table, then you would create a new entry for it. Otherwise, you would add 1 to the entry corresponding to the current k-mer substring of Text. We call this table the frequency table for Text and k.
Figure: A table corresponding to counting the number of occurrences of every 3-mer in Text = "ACGTTTCACGTTTTACGG".
In the previous FrequentWords algorithm, we also make a single pass down text, but each time we encounter a k-mer window, we call the PatternCount subroutine, which requires its own pass down the entire length of Text. But when we build a frequency table, we make one pass down Text, and every time we encounter a k-mer, we simply add 1 to the k-mer’s count.
We know that an array of length n is an ordered table of values, where we access the values using the integer indices 0 through n-1. The frequency table is a generalized version of an array called a map or dictionary for which the indices are allowed to be arbitrary values (in this case, they are strings). More precisely, the indices of a map are called keys.
Given a map dict, we can access the value associated with a key key using the notation dict[key]. In the case of a frequency table called freq, we can access the value associated with some key string pattern using the notation freq[pattern]. The following pseudocode function takes a string text and an integer k as input and returns their frequency table as a map of string keys to integer values.
FrequencyTable(Text, k)
freqMap ← empty map
n ← |Text|
for i ← 0 to n − k
Pattern ← Text(i, k)
if freqMap[Pattern] doesn't exist
freqMap[Pattern]← 1
else
freqMap[pattern] ←freqMap[pattern]+1
return freqMapOnce we have built the frequency table for a given Text and k, we can find all frequent k-mers if we determine the maximum value in the table, and then identify the keys of the frequency table achieving this value, appending each one that we find to a growing list. We are now ready to write a function BetterFrequentWords to solve the Frequent Words Problem. This function relies on a function MaxMap that takes a map of strings to integers as an input and returns the maximum value of this map as output.
BetterFrequentWords(Text, k)
FrequentPatterns ← an array of strings of length 0
freqMap ← FrequencyTable(Text, k)
max ← MaxMap(freqMap)
for all strings Pattern in freqMap
if freqMap[pattern] = max
append Pattern to frequentPatterns
return frequentPatternsSTOP and ThinkWrite a function MaxMap. Make sure that your function will work even if the values are all negative.
Code Challenge Solve the Frequent Words Problem. (Solve at Cogniterra or Rosalind.)
Solve it with the autograderFree to start in the interactive text
- Input: A string Text and an integer k.
- Output: All most frequent k-mers in Text.
Frequent Words in Vibrio cholerae
The table above reveals the most frequent k-mers in the ori region from Vibrio cholerae (reproduced below), along with the number of times that each k-mer occurs.
atcaatgatcaacgtaagcttctaagcatgatcaaggtgctcacacagtttatccacaac ctgagtggatgacatcaagataggtcgttgtatctccttcctctcgtactctcatgacca cggaaagatgatcaagagaggatgatttcttggccatatcgcaatgaatacttgtgactt gtgcttccaattgacatcttcagcgccatattgcgctggccaaggtgacggagcgggatt acgaaagcatgatcatggctgttgttctgtttatcttgttttgactgagacttgttagga tagacggtttttcatcactgactagccaaagccttactctgcctgacatcgaccgtaaat tgataatgaatttacatgcttccgcgacgatttacctcttgatcatcgatccgattgaag atcttcaattgttaattctcttgcctcgactcatagccatgatgagctcttgatcatgtt tccttaaccctctattttttacggaagaatgatcaagctgctgctcttgatcatcgtttc
STOP and Think: Do any of the counts in the above table seem surprisingly large?
For example, the 9-mer ATGATCAAG appears three times in the ori region of Vibrio cholerae—is it surprising?
atcaatgatcaacgtaagcttctaagcATGATCAAGgtgctcacacagtttatccacaac
ctgagtggatgacatcaagataggtcgttgtatctccttcctctcgtactctcatgacca
cggaaagATGATCAAGagaggatgatttcttggccatatcgcaatgaatacttgtgactt
gtgcttccaattgacatcttcagcgccatattgcgctggccaaggtgacggagcgggatt
acgaaagcatgatcatggctgttgttctgtttatcttgttttgactgagacttgttagga
tagacggtttttcatcactgactagccaaagccttactctgcctgacatcgaccgtaaat
tgataatgaatttacatgcttccgcgacgatttacctcttgatcatcgatccgattgaag
atcttcaattgttaattctcttgcctcgactcatagccatgatgagctcttgatcatgtt
tccttaaccctctattttttacggaagaATGATCAAGctgctgctcttgatcatcgtttc
We highlight a most frequent 9-mer instead of using some other value of k because experiments have revealed that bacterial DnaA boxes are usually nine nucleotides long. The probability that there exists a 9-mer appearing three or more times in a randomly generated DNA string of length 500 is approximately 1/1300. For more details, see "DETOUR: Probabilities of Patterns in a String" in the print companion or at Cogniterra.
In fact, there are four different 9-mers repeated three or more times in this region: ATGATCAAG, CTTGATCAT, TCTTGATCA, and CTCTTGATC. The low likelihood of witnessing even one repeated 9-mer in the ori region of Vibrio cholerae leads us to the working hypothesis that one of these four 9-mers may represent a potential DnaA box that, when appearing multiple times in a short region, jump-starts replication. But which one?
STOP and Think: Is any one of the four most frequent 9-mers in the ori of Vibrio cholerae "more surprising" than the others?