Chapter 1 Epilogue
Complications in ori Predictions
In this chapter, we have considered three genomes and found three different hypothesized 9-mers encoding ATGATCAAG in Vibrio cholerae, CCTACCACC in Thermotoga petrophila, and TTATCCACA in E. coli. We must warn you that finding ori is often more complex than in the three examples we considered. Some bacteria have even fewer DnaA boxes than E. coli, making it difficult to identify them. The ter region is often located not directly opposite to ori but may be significantly shifted, resulting in reverse and forward half-strands having substantially different lengths. The position of the skew minimum is often only a rough indicator of ori position, which forces researchers to expand their windows when searching for DnaA boxes, bringing in extraneous repeated substrings. Finally, skew diagrams do not always look as nice as that of E. coli; for example, the skew diagram for Thermotoga petrophila is shown below.
STOP and Think: What evolutionary process could possibly explain the shape of the skew diagram for Thermotoga petrophila?
Since the skew diagram for Thermotoga petrophila is complex and the ori for this genome has not even been experimentally verified, there is a chance that the region predicted by Ori-Finder as the ori region for Thermotoga petrophila (or even for Vibrio cholerae) is actually incorrect!
You should now have a good sense of the practical considerations involved in locating ori and DnaA boxes computationally. We will take the training wheels off and ask you to solve a Final Challenge by working with the Salmonella enterica genome.
Final Challenge Find a DnaA box in Salmonella enterica.Solve it with the autograderFree to start in the interactive text
If you enjoyed this material, please join us for our next chapter! There is much more to learn about the fundamental algorithms that have helped make biology a computational discipline. And if you're interested in more algorithms, we recommend the Algorithms and Data Structures Micromasters on EdX, where some of our materials are used as well.
Bibliography Notes
Using the skew to find replication origins was first proposed by Lobry, 1996 and also described in Grigoriev, 1998. Grigoriev, 2011 provides an excellent introduction to the skew approach, and Sernova and Gelfand, 2008 gave a review of algorithms and software tools for finding replication origins in bacteria. Lundgren et al., 2004 demonstrated that archaea may have multiple ori. Wang et al., 2011 inserted an artificial ori into the E. coli genome and showed that it triggers replication. Xia, 2012 was the first to conjecture that bacteria may have multiple replication origins. Gao and Zhang, 2008 developed the Ori-Finder software program for finding bacterial replication origins.
Liachko et al., 2013 provided the most comprehensive description of the replication originsofyeast. Solov’ev, 1966 was the first to derive accurate formulas for approximating the probabilities of patterns in a string. Gardner, 1974 wrote an excellent introductory article about the Best Bet for Simpletons paradox. Guibas and Odlyzko, 1981 provided an excellent coverage of the overlapping words paradox that illustrates the complexity of computing the probabilities of patterns in a random text. They also derived a rather complicated proof of Conway’s formula for Best Bet for Simpletons. Sedgewick and Flajolet, 2013 gave an overview of various approaches for computing the probabilities of patterns in a string.