Recall that nucleotides A and T are complements of each other, as are G and C. Having one strand and a supply of “free floating” nucleotides, one can imagine the synthesis of a complementary strand on a template strand. This model of replication was confirmed rigorously by Meselson and Stahl in 1958. The beginning and end of a DNA strand are denoted 5’ (pronounced “five prime”) and 3’ (pronounced “three prime”), respectively. For more details, see "DETOUR: The Most Beautiful Experiment in Biology" in the print companion.

The figure below shows a template strand AGTCGCATAGT and its complementary strand ACTATGCGACT.

Reverse complement

Figure: Complementary strands run in opposite directions. Each strand is read in the 5' → 3' direction.

At this point, you may think that we have made a mistake, since the complementary strand in this figure reads out TCAGCGTATCA from left to right rather than ACTATGCGACT. We have not: each DNA strand has a direction, and the complementary strand runs in the opposite direction to the template strand, as shown by the arrows in the figure. Each strand is read in the 5' → 3' direction. For more details, see "DETOUR: Directionality of DNA Strands" in the print companion or at Cogniterra.

Given a nucleotide p, we denote its complementary nucleotide as p*. The reverse complement of a string Pattern = p₁… p_n is the string Pattern_rc = p_n* … p₁* formed by taking the complement of each nucleotide in Pattern, then reversing the resulting string. We will need the solution to the following problem throughout this chapter:

Reverse Complement Problem: Find the reverse complement of a DNA string.

Input: A DNA string Pattern.
Output: Pattern_rc, the reverse complement of Pattern.

Code Challenge Solve the Reverse Complement Problem. (Solve at Cogniterra or Rosalind.)Solve it with the autograderFree to start in the interactive text

STOP and Think: Look again at the four most frequent 9-mers in the ori of Vibrio cholerae (shown below): ATGATCAAG, CTTGATCAT, TCTTGATCA, and CTCTTGATC.

atcaatgatcaacgtaagcttctaagcATGATCAAGgtgctcacacagtttatccacaac ctgagtggatgacatcaagataggtcgttgtatctccttcctctcgtactctcatgacca cggaaagATGATCAAGagaggatgatttcttggccatatcgcaatgaatacttgtgactt gtgcttccaattgacatcttcagcgccatattgcgctggccaaggtgacggagcgggatt acgaaagcatgatcatggctgttgttctgtttatcttgttttgactgagacttgttagga tagacggtttttcatcactgactagccaaagccttactctgcctgacatcgaccgtaaat tgataatgaatttacatgcttccgcgacgatttacCTCTTGATCATcgatccgattgaag atcttcaattgttaattctcttgcctcgactcatagccatgatgagCTCTTGATCATgtt tccttaaccctctattttttacggaagaATGATCAAGctgctgCTCTTGATCATcgtttc

Now do you notice anything surprising?

Interestingly, among the four most frequent 9-mers in ori of Vibrio cholerae, ATGATCAAG and CTTGATCAT are reverse complements of each other, resulting in the six total occurrences of these strings shown below.

atcaatgatcaacgtaagcttctaagcATGATCAAGgtgctcacacagtttatccacaac ctgagtggatgacatcaagataggtcgttgtatctccttcctctcgtactctcatgacca cggaaagATGATCAAGagaggatgatttcttggccatatcgcaatgaatacttgtgactt gtgcttccaattgacatcttcagcgccatattgcgctggccaaggtgacggagcgggatt acgaaagcatgatcatggctgttgttctgtttatcttgttttgactgagacttgttagga tagacggtttttcatcactgactagccaaagccttactctgcctgacatcgaccgtaaat tgataatgaatttacatgcttccgcgacgatttacctCTTGATCATcgatccgattgaag atcttcaattgttaattctcttgcctcgactcatagccatgatgagctCTTGATCATgtt tccttaaccctctattttttacggaagaATGATCAAGctgctgctCTTGATCATcgtttc

Finding a 9-mer that appears six times (either as itself or as its reverse complement) in a DNA string of length 500 is far more surprising than finding a 9-mer that appears three times (as itself). This observation leads us to the working hypothesis that ATGATCAAG and its reverse complement CTTGATCAT indeed represent DnaA boxes in Vibrio cholerae. This computational conclusion makes sense biologically because the DnaA protein that binds to DnaA boxes and initiates replication does not care which of the two strands it binds to. Thus, for our purposes, both ATGATCAAG and CTTGATCAT represent DnaA boxes.

However, before concluding that we have found the DnaA box of Vibrio cholerae, the careful bioinformatician should check if there are other short regions in the Vibrio cholerae genome exhibiting multiple occurrences of ATGATCAAG (or CTTGATCAT). After all, maybe these strings occur as repeats throughout the entire Vibrio cholerae genome, rather than just in the ori region. To this end, we need to solve the following problem.

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

Input: Strings Pattern and Genome.
Output: All starting positions in Genome where Pattern appears as a substring.

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

Exercise Break Return a space-separated list of starting positions (in increasing order) where CTTGATCAT appears as a substring in the Vibrio cholerae genome.

After solving the Pattern Matching Problem, we discover that ATGATCAAG appears 17 times in the following starting positions of the Vibrio cholerae genome:

116556, 149355, 151913, 152013, 152394, 186189, 194276, 200076, 224527,
307692, 479770, 610980, 653338, 679985, 768828, 878903, 985368

With the exception of the three occurrences of ATGATCAAG in ori at starting positions 151913, 152013, and 152394, no other instances of ATGATCAAG form clumps, i.e., appear close to each other in a small region of the genome. You may check that the same conclusion is reached when searching for CTTGATCAT. We now have strong statistical evidence that ATGATCAAG/CTTGATCAT may represent the hidden message to DnaA to start replication.

STOP and Think: Can we conclude that ATGATCAAG/CTTGATCAT also represents a DnaA box in other bacterial genomes?

Some Hidden Messages are More Surprising than Others