1 Introduction

The cracking of the genetic code by means of a rapid series of experiments and logical inferences is arguably the first instance of a “big science” approach in the history of molecular genetics (Judson, 1996). Theoretical considerations had already indicated that any nucleic acid code words must comprise a minimum of three letters (Crick, 1966). After it was demonstrated in 1961 that an artificial poly-U RNA template directs incorporation of the amino acid proline into a polypeptide, and thus that UUU was the code for PRO, Marshall Nirenberg’s lab had by 1963 deduced an incomplete “dictionary” of 50 three-letter code words (Nirenberg et al., 1965), and a substantially complete genetic code table was created by 1965 (Nirenberg et al., 1966; also see Figure 13.1). The iconic 4 × 4 × 4 table is now a standard feature of biology textbooks and has been incorporated into bioinformatic computational schemes as a fundamental feature.

In this chapter, we consider properties of short segments of the genetic code that are of interest both theoretically, as unexplored computational challenges, and practically, bearing on the evolution and function of the code and coding molecules. Taken together, the solution of these challenges at the intersection of computational and biological science provides reciprocal illumination to each.

3 Algorithmic and programming considerations

An introduction to the theory of data mining for such ORFs typically begins with the propounding of short dsDNA sequence exemplars of length L = 15 ~ 25 base pairs that are constrained by the 5&1 condition. A practical algorithmic generator of such exemplars must be able to access the entire space of dsDNA sequences that satisfy the 5&1 condition for a specified L, sample that space in an at least approximately random manner, and be efficient in terms of both central processing unit (CPU) run time and required memory space. We developed two such algorithms (Carr et al., 2014a), the first based on a two-level recursive search that generates a dsDNA skeleton with at least one stop codon in each of five frames, and then completes the remainder of the dsDNA sequence by adding bases at random to the skeleton so as to produce an ORF exemplar in which the 5&1 condition is maintained. An app that generates dsDNA sequence exemplars that satisfy the 5&1 condition for L ≤ 100 is available at http://www.ucs.mun.ca/~donald/orf/biocomp/. We provide a more complete discussion of the pedagogical use of the web application in a previous study (Carr et al., 2014b). The second algorithm used an exhaustive search that enumerated all those dsDNA sequences of length L that satisfied the 5&1 condition without storing the results as exemplars.

The recursive and exhaustive algorithms show that there are no solutions for L = 5 ~ 10, and 96 for L = 11 (Figure 13.2, after Carr et al., 2014a). Enumerations from the two methods agree for 11 ≤ L ≤ 19, at which point the recursive algorithm succumbs to memory limitations. For L < 22, CPU usage for the exhaustive algorithm was measured on a single, quad-core PC. For L ≥ 22, CPU usage was measured over a network of such machines: by L = 25, exact CPU usage is obscured by competing demands from other users on the same network. Calculation of the number of 5&1 solutions for L > 25 with the resources available to us would require several days.

4 Analytical and random sampling solutions to L > 25 sequences: Triplet-based approximations

Given these limitations, we have developed a simplified analytical formulation of the 5&1 problem, in which the 64 triplets in the universal genetic code comprise C = 61 coding and S = (64 – C) = 3 stop triplets. If we disregard the actual nucleotide composition of coding and noncoding triplets and the overlapping nature of the six RFs, the probability that any given triplet is a coding triplet is C = 61/64. Next, the probability that a string of T triplets will be an ORF is simply calclulated as

p(ORFT)=CT,$\mathrm{p}\left(\mathrm{ORFT}\right)={\mathrm{C}}^{\mathrm{T}},$$\mathrm{p}\left(\mathrm{ORFT}\right)={\mathrm{C}}^{\mathrm{T}},$

and the probability that such a string will include at least one stop is calculated as

$\mathrm{p}\left(\mathrm{stop}\right)=1–{\mathrm{C}}^{\mathrm{T}}\text{.}$

Then, an approximation of the probability that a string of triplets satisfies the 5&1 condition p(NORFT) is the joint probability that RF1 is open and RFs 2-5 are all closed, or that any of RF2, RF3, … RF6 is open and the other five RFs closed. Thus,

$\mathrm{p}\left(5\&1\mathrm{T}\right)=\left(6\right)\left({\mathrm{C}}^{\mathrm{T}}\right){\left(1–{\mathrm{C}}^{\mathrm{T}}\right)}^5$

Figure 13.3 shows a simultaneous plot of Eqs. (13.1), (13.2), and (13.3). Where Eq. (13.3) has a constant factor K = 6 and p(stop) enters the function as its fifth power, p(5&1 T)] initially tracks p(stop) toward the enumerable limit of L = 25 as observed, but the function maximizes at T = 37 (L = 111) at p = 0.4 of a 5&1 solution.

Thus, and counterintuitively, the scarcity of 5&1 solutions for smaller values of T (T < 37, L < 111) is determined by the low probability of exactly five simultaneously stopped frames (1 − C^T)⁵, rather than the relative scarcity of ORFs (C^T/4^L). For larger T >> 37, any given ORF is almost certainly accompanied by five frames with multiple stops.

We evaluated Eq. (13.3) as an estimator of p(5&1) by sampling for each of L = 3 ~ 450 (mod 3) a set 10⁶ random dsDNA sequences, and ascertaining the fraction that satisfied the 5&1 condition under the universal genetic code. Figure 13.4 shows that Eq. (13.3) very slightly overestimates the proportion of 5&1 solutions in the Monte Carlo simulation for L < 37. This is to be expected given the absence of constraints in the triplet approximation (triplet assignments, overlapping RFs, etc.), and otherwise the equation provides a close upper bound.

5 Alternative genetic codes

Besides the universal code with three stop triplets (Figure 13.1), there are several variant codes with one, two, or four stops (Itzkovitz and Alon, 2007). Figure 13.5 shows simultaneous plots of Eq. (13.3) with S = 1, 2, or 4, such that C = 63/64, 62/64, and 60/64, respectively. All variants have the same p_max = 0.40 as the three-stop code, at L = 342, 168, and 84, respectively. This maximum arises as the zero (horizontal) slope of the first derivative of Eq. (13.3) when C^T = 1/6. Substituting this back into Eq. (13.3) gives p = 0.40. Because C is a constant for any one model of the code and co-occurs with T only in the form C^T, the derivative of p(NORFT) is necessarily identical for different values of C. The equation for p_max can then be rearranged and solved to predict T, as

$\mathrm{T}=log\left(1/6\right)/\left(log\mathrm{C}\right)=-0.7782/\left(log\mathrm{C}\right)$

The upper bound on a 10% cutoff for p(5&1) increases rapidly as the number of stops decreases: for example, at the upper 10% probability bound, there are more than three times as many solutions with a one-stop (L = 254, T = 762) as with a three-stop code (L = 83, T = 249).

6 Implications for the evolution of ORF size

Broad conservation of the universal code in nuclear genomes indicates that a three-stop code optimizes some selective advantage (Itzkovitz and Alon, 2007), whereas retention of an unstopped TGA in the common ancestor of all Metazoan mitochondrial DNA (mtDNA) codes suggests that there is some advantage for a two-stop code, and the relatively recent evolution of the four-stop code in Chordata offers some advantage over a three-stop intermediate (Cannaozzi and Schneider, 2012). We have shown here that short random DNA sequences have a high probability of including single ORF over certain size ranges, and that this probability is inversely proportional to the number of stops in the genetic codes used. Might size variation of ORF coding sequences across genetic codes be subject to natural selection?

A recent model of stop codon evolution (Johnson et al., 2011) proposes that multi-stop codes provide a backstop against readthrough, balanced against an increased probability of random stop mutations. Like ours, the model predicts an inverse relationship between the number of stop triplets and the length of coding sequences. Consistent with this, their sampling of NCBI data shows a marked (though nonsignificant) relationship between longer coding sequence and fewer stops, for pairs of genomes in the same taxon alternatively decoded with one- versus two-, one- versus three-, or two- versus three-stop codes. There is no such trend for the two- versus four-stop Chordata comparison. Johnson et al. (2011) note a previous suggestion that reassignment of TGA from sense to stop has occurred frequently in association with the evolutionary reduction of genome size in mtDNA genomes, in apparent contradiction to the predicted direction. However, a phylogenetic perspective on the various mtDNA codes shows that this reassignment has occurred only once, in the shared ancestral code of all Animalia and Yeast (Ophisthokonta); this will be considered elsewhere.

In their data, coding sequences for genomes with three-stop codes are in the range of 250 ~ 400 bp, with animal mtDNA at about 300 bp: these are rather longer than our optimal of 111 or 84 bp for S = 3 or 4, respectively, but they are well within the range of reasonable probability (Figure 13.5). A longer coding sequence might also be assembled from several shorter single-ORF fragments, so long as the individual ORFs were assembled in the same RF. Recall that fragments shorter than the optimum are more likely to have multiple ORFs. Selection could then act to modify the function of the corresponding polypeptide product while maintaining a single ORF. DNA sequences 5’ or 3’ to the ORF region can be added easily, since there is a high probability that any 3-bp sequence added in the open frame also will be open [~(61/64)³ = 0.87], while the other five frames are already stopped. The fewer the stops, the longer the likely candidate sequences are. For example, in a four-stop code, there is less than 1% chance that an approximately 300-bp DNA will contain one and only one ORF, whereas for a one-stop code, there is a far greater than 10% chance that a sequence of many hundreds of base pairs will do so.

Are short, random DNA sequences with single ORFs of utility in evolution? It has recently been demonstrated that some free-living bacteria can take up ex vivo, fragmented DNA from the environment and incorporate it into their genomes by replication-dependent transformation (Overballe-Petersen et al., 2013). Fragments of 20 ~ 100 bp were most efficiently transformed at higher rates than larger fragments. We have shown that random fragments of just this size are most likely to include a single ORF, which might mediate the success of any such horizontal transfer and its incorporation into the host genome as a functional coding sequence. Overballe-Petersen et al., 2013 hypothesize that “rates of molecular evolution in naturally transformable species may be influenced by the diversity of free environmental DNA.” Our results suggest that one type of evolutionary diversity in random DNA may be the varying high probability that small fragments of various lengths will include unique ORFs subject to modification by natural selection.