5.4 Conclusions


5.4 Conclusions

DNA computing still labors under a preponderance of theory. Laboratory experiments have only explored the nearest shoals. All the techniques from the section above, entitled Tools of the Trade, need to be examined with the same kind of rigor that Khodor and Gifford (1999) used to examine the sequence separation procedure. Potential improvements to the techniques should be explored. An efficient computational model should be derived from the least (or tolerably) error-prone manipulations along with algorithms for handling those errors that are unavoidable. This is the rather mundane work that would bring civilization to the hinterlands of current DNA computing. Nevertheless, glory will surely be heaped on she who demonstrates a DNA solution to a problem beyond the ken of silicon computation. This is the fabled fountain of youth for the field: The so-called killer app that will firmly establish DNA computing as more than just a curiosity. Yet no one truly knows if such a killer app exists. The catastrophes of errors may still sink all our hopes.

Meanwhile, one cause for real optimism in the future of DNA computing is its synergy with molecular biology. Almost any advances in techniques in one field will be useful to the other. The work of Seeman and others (Seeman et al. 1998; Gardner, Cantor, and Collins 2000; Elowitz and Leibler 2000) suggest that the major contribution of DNA computation may not even be to the field of computation but rather to the development of nanotechnology. Even if DNA computers never manage to leapfrog traditional silicon computers, they are still bound to be of value. Even if it proves impossible to implement a universal DNA computer—able to run all our software at blazingly fast speeds—the massively parallel nature of DNA computing is sure to be useful for certain practical problems. I take the position that DNA computation is likely to turn out to have a role similar to neural networks. They will be better than traditional methods for some problems, and worse for others. In this way, I expect DNA computation to complement rather than replace our current computational techniques.

Acknowledgments

Significant portions of this chapter have been reproduced from Maley (1998). I would like to thank MIT Press for their generosity in allowing me this freedom. I would also like to thank Erik Winfree and Laura Landweber for helpful comments and discussion. I would like to thank Stephanie Forrest for her patience and support. This work was carried out under her aegis and ONR Grant N00014-99-1-0417. Finally, I would like to thank Marvin Minsky for ushering me down this path.



References

Adleman, L. M. 1994. Molecular computation of solutions to combinatorial problems. Science 266: 1021–1024.

Adleman, L. M. 1996. On constructing a molecular computer. In DNA Based Computers, ed. R. J. Lipton and E. B. Baum, 1–22. Providence: American Mathematical Society,.

Adleman, L. M.P. W. K. Rothemund, S. Roweis, and E. Winfree., 1996. On applying molecular computation to the data encryption standard. In DNA Based Computers II. Vol. 44 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, ed. L. F. Landweber and E. B. Baum, 31–44. Providence: American Mathematical Society,.

Amos, M. A. Gibbons, and D. Hodgson., 1998. Error-resistant implementation of DNA computations. In DNA Based Computers II. Vol. 44 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, ed. L. F. Landweber and E. B. Baum, 151–162. Providence: American Mathematical Society,.

Amos, M., S. Wilson, D. A. Hodgson, G. Owenson, and A. Gibbons., 1998. Practical implementation of DNA computations. In Unconventional Models of Computation, ed. C. Calvde, J. Casti, and M. Dinneen, 1–18. Heidelberg: Springer Verlag.

Bach, E., A. Condon, E. Glaser, and C. Tanguary., 1996. DNA Models and Algorithms for NP-complete Problems. New York: IEEE Computer Society Press,.

Baum, E. B. 1998. DNA sequences useful for computation. In DNA Based Computers II. Vol. 44 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, ed. L. F. Landweber and E. B. Baum, 235–242. Providence: American Mathematical Society.

Baum, E. B., and D. Boneh., 1996. Running dynamic programming algorithms on a DNA computer. In DNA Based Computers II. Vol. 44 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, ed. L. F. Landweber and E. B. Baum, 77–86. Providence: American Mathematical Society.

Beaudry, A. A., and G. F. Joyce., 1992. Directed evolution of an RNA enzyme. Science 257: 635–641.

Beaver, D. 1995. Molecular computing. Technical Report TR95-001, Pennslyvania State University, University Park, Penn.

Beaver, D. 1996. A universal molecular computer. In DNA Based Computers, ed. E. B. Baum and R. J. Lipton, 29–36. Providence: American Mathematical Society.

Blumberg, A. J. 1999. Parallel computation on a DNA substrate. In DNA Based Computers III. Vol. 48 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, ed. H. Rubin, and D. H. Wood, 275–289. Providence: American Mathematical Society.

Boneh, D., C. Dunworth, and R. J. Lipton., 1995. Breaking DES using a molecular computer. Technical Report CS-TR-489-95, Princeton University, Princeton: N.J.

Boneh, D., C. Dunworth, and J. Sgall., 1995. On the computational power of DNA. Technical Report TR499-95, Princeton University, Princeton N.J.

Calude, C., J. Casti, and M. Dinneen, eds., 1998. Unconventional Models of Computation. Heidelberg: Springer Verlag.

Cha, R. S., and W. G. Thilly., 1995. Specificity, efficiency, and fidelity of PCR. In PCR primer, ed. C. W. Dieffenbach and G. S. Dveksler, 37–52. Plainview, N.Y.: Cold Spring Harbor Laboratory Press.

Conrad, M., and K.-P. Zauner., 1999. Design for a DNA conformational processor. In DNA Based Computers III. Vol. 48 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, ed. H. Rubin, and D. H. Wood, 290–295. Providence: American Mathematical Society.

Csuhaj-Varju´, E., R. Freund, L. Kari, and G. Páun., 1996. DNA computation based on splicing: Universality results. In Biocomputing: Proceedings of the 1996 Pacific Symposium, ed. L. Hunter, and T. Klein, 179–190. Singapore: World Scientific Publishing.

Cukras, A. R., D. Faulhammer, R. J. Lipton, and L. F. Landweber., 2000. Chess games: A model for RNA based computation. In Preliminary Proceedings of the Fourth DIMACS Workshop on DNA Based Computers, ed. L. Kari, 27–37.

Dawkins, R. 1995. River out of Eden. New York: Basic Books.

Deaton, R., R. C. Murphy, M. Garzon, D. R. Franceschetti, and J. Stevens., 1996. Good encodings for DNA-based solutions to combinatorial problems. In DNA Based Computers II. Vol. 44 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, ed. L. F. Landweber, and E. B. Baum, 247–258. Providence: American Mathematical Society.

Dieffenbach, C. W., and G. S. Dveksler., 1995. PCR Primer. Plainview, N.Y.: Cold Spring Harbor Laboratory Press.

Elowitz, M. B., and S. Leibler., 2000. A synthetic oscillatory network of transcriptional regulators. Nature 403: 335–338.

Eng, T. K. 2000. On solving 3CNF-satisfiability with an in vivo algorithm. In Preliminary Proceedings of the Fourth DIMACS Workshop on DNA Based Computers, ed. L. Kari, 163–171.

Faulhammer, D., A. R. Cukras, R. J. Lipton, and L. F. Landweber., 2000. When the knight falls: On constructing an RNA computer. In DNA Based Computers V. Vol. 54 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, ed. E. Winfree, and D. K. Gifford, 1–8. Providence: American Mathematical Society.

Gannon, F., and R. Powell., 1991. Construction of recombinant DNA. In Essential Molecular Biology, ed. T. A. Brown, 143–160. Oxford: Oxford University Press.

Gánti, I. 1987. The Principle of Life. Budapest: OMIKK.

Gardner, T. S., C. R. Cantor, and J. J. Collins., 2000. Construction of a genetic toggle switch in Escherichia coli. Nature 403: 339–342.

Gifford, D. K. 1994. On the path to computation with DNA. Science 266: 993–994.

Guarnieri, F., M. Fliss, and C. Bancroft., 1996. Making DNA add. Science 273: 220–223.

Hagiya, H., M. Arita, M. D. Kiga, K. Sakamoto, and S. Yokoyama., 1999. Towards parallel evaluation and learning of Boolean μ-formulas with molecules. In DNA Based Computers III. Vol. 48 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, ed. H. Rubin, and D. H. Wood, 105–114. Providence: American Mathematical Society.

Hartemink, A. J., D. K. Gifford, and J. Khodor., 2000. Automated constraint-based nucleotide sequence selection for DNA computation. In Preliminary Proceedings of the Fourth DIMACS Workshop on DNA Based Computers, ed. L. Kari, 287–297.

Head, T. 1987. Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors. Bull. Math. Biol. 49: 737–759.

Ji, S. 2000. The cell as a DNA-based molecular computer. In Preliminary Proceedings of the Fourth DIMACS Workshop on DNA Based Computers, ed. L. Kari, 151–162.

Kampis, G., and V. Csányi., 1991. Life, self-reproduction, and information: Beyond the machine metaphor. J. Theor. Biol. 148: 17–32.

Kaplan, P. D., G. Cecci, and A. Libchaber., 1995. Molecular computation: Adleman's experiment repeated. Technical report, NEC Research Institute, Princeton, N.J.

Kaplan, P. D., G. Cecchi, and A. Libchaber., 1996. DNA based molecular computation: Templatetemplate interactions in PCR. In DNA Based Computers II. Vol. 44 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Scierce, ed. L. F. Landweber, and E. B. Baum, 97–104. Providence: American Mathematical Society.

Kari, L. 1996. DNA computers, tomorrow's reality. Bull. Eur. Assoc. Theor. Comput. Sci. 59: 256–266.

Kari, L., ed., 2000. Preliminary Proceedings of the fourth DIMACS Workshop on DNA Based Computers, held at the University of Pennsylvania, 15–19 June 1998. In press.

Kari, L., and L. Landweber., 2000. Computational power of gene rearrangement. In DNA Based Computers V. Vol. 54 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, ed. E. Winfree, and D. K. Gifford, 203–213. Providence: American Mathematical Society.

Karp, R., C. Kenyon, and O. Waarts., 1995. Error resilient DNA computation. Research report 95–20, Laboratoire de l'Informatique du Parallélism, Ecole Normale Supe´rieure de Lyon.

Kazic, T. 2000. After the Turing machine: A metamodel for molecular computing. In Preliminary Proceedings of the Fourth DIMACS Workshop on DNA Based Computers, ed. L. Kari, 131–149.

Khodor, J., and D. K. Gifford., 1999. The efficiency of sequence-specific separation of DNA mixtures for biological computing. In DNA Based Computers III. Vol. 48 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, ed. H. Rubin, and D. H. Wood, 26–34. Providence: American Mathematical Society.

Khodor, J., and D. K. Gifford., 2000. Design and implementation of computational systems based on programmed mutagenesis. In Preliminary Proceedings of the Fourth DIMACS Workshop on DNA Based Computers, ed. L. Kari, 101–107.

Knight, T. F., and G. J. Sussman., 1997. Cellular gate technology. In Unconventional Models of Computation, ed. C. S. Calude, J. Casti, and M. J. Dinneen, 257–272. Singapore: Springer-Verlag.

Kurtz, S. A., S. Mahaney, J. Royer, and J. Simon., 1997. Biological computing. In Complexity Retrospective II, ed. L. A. Hemaspaandra, and A. L. Selman., Singapore: Springer Verlag.

Landweber, L. F., and E. B. Baum, eds., 1998. DNA Based Computers II. Vol. 44 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. Providence: American Mathematical Society.

Landweber, L. F., and L. Kari., 2000. The evolution of cellular computing: Nature's solution to a computational problem. In Preliminary Proceedings of the Fourth DIMACS Workshop on DNA Based Computers, ed. L. Kari, 3–13.

Landweber, L. F., R. J. Lipton, and M. O. Rabin., 1999. DNA2DNA computations: A potential "killer app?" In DNA Based Computers III. Vol. 48 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Scierce, ed. H. Rubin, and D. H. Wood, 161–172. Providence: American Mathematical Society.

Linial, M., and N. Linial., 1995. Letters to Science. Science 268: 481.

Lipton, R. J. 1995. DNA solution of hard computational problems. Science 268: 542–545.

Lipton, R. J., and E. D. Baum, eds., 1996. DNA Based Computers. Vol. 27 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. Providence: American Mathematical Society.

Liu, Q., A. G. Frutos, L. Wang, A. J. Thiel, S. D. Gillmor, T. Strother, A. E. Condon, R. M. Corn, M. G. Lagally, and L. M. Smith., 2000a. Progress towards demonstration of a surface based DNA computation: A one-word approach to solve a model satisfiability problem. In Preliminary Proceedings of the Fourth DIMACS Workshop on DNA Based Computers, ed. L. Kari, 15–25.

Liu, Q., L. Wang, A. G. Frutos, A. E. Condon, R. M. Corn, and L. M. Smith., 2000b. DNA computing on surfaces. Nature 371: 31–36.

Lönneborg, A., P. Sharma, and P. Stougaard., 1995. Construction of a subtractive cDNA libary using magnetic beads and PCR. In PCR Primer, ed. C. W. Dieffenbach, and G. S. Dveksler, 439–452. Plainview, N.Y.: Cold Spring Harbor Laboratory Press.

Lorsch, J. R., and J. W. Szostak., 1994. In vitro evolution of new ribozymes with polynucleotide kinase activity. Nature 371: 31–36.

Lustig, A. J. 1998. Mechanisms of silencing in Saccharomyces cerevisiae. Curr. Opin. Genetics Dev. 8: 233–239.

Maley, C. C. 1998. DNA computation: Theory, practice, and prospects. Evolutionary Comput. 6: 201–229.

Oliver, J. S. 1996. Computation with DNA-matrix multiplication. In DNA Based Computers II. Vol. 44 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, ed. L. F. Landweber, and E. B. Baum, 113–122. Providence: American Mathematical Society.

Ouyang, Q., P. D. Kaplan, S. Liu, and A. Libchaber., 1997. DNA solution of the maximal clique problem. Science 278: 446–449.

Păun, G., G. Rozenberg, and A. Salomaa., 1998. DNA computing: New Computing Paradigms. Heidelberg: Springer-Verlag.

Reif, J. 1998. Paradigms for biomolecular computation. In Unconventional Models of Computation, ed. C. Calude, J. Casti, and M. Dinneen, 72–93. Heidelberg: Springer Verlag.

Rothemund, P. W. K., 1996. A DNA and restriction enzyme implementation of Turing machines. In DNA Based Computers. Vol. 27 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, ed. R. J. Lipton, and E. D. Baum, 75–120. Providence: American Mathematical Society.

Roweis, S., E. Winfree, R. Burgoyne, N. Y. Chelyapov, M. R. Goodman, P. W. K. Rothemund, and L. M. Adleman., 1996. A sticker-based architecture for DNA computation. In DNA Based Computers II. Vol. 44 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Scierce, ed. L. F. Landweber, and E. B. Baum, 1–30. Providence: American Mathematical Society.

Rubin, H., and D. H. Wood, eds., 1999. DNA Based Computers III. Vol. 48 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. Providence: American Mathematical Society.

Sakamoto, K., D. Kiga, K. Komiya, H. Gouzu, S. Yokoyama, S. Ikeda, H. Sugiyama, and M. Hagiya., 2000. State transitions by molecules. In Preliminary Proceedings of the Fourth DIMACS Workshop on DNA Based Computers, ed. L. Kari, 87–99.

Santoro, S. W., and G. F. Joyce., 1997. A general purpose RNA-cleaving DNA enzyme. Proc. Natl. Acad. Sci. USA 94: 4262–4266.

Sassanfar, M., and J. W. Szostak., 1993. An RNA motif that binds ATP. Nature 364: 550–553.

Seeman, N. S., H. Wang, X. Yang, F. Liu, C. Mao, W. Sun, L. Wenzler, Z. Shen, R. Sha, H. Yan, M. H. Wong, P. Sa-Ardyen, B. Liu, H. Qiu, X. Li, J. Qi, S. M. Du, Y. Zhang, J. E. Mueller, T.-J. Fu, Y. Wang, and J. Chen., 1998. New motifs in DNA nanotechnology. Nanotechnology 9: 257–273.

Smith, W. D. 1995. DNA computers in vitro and vivo. Technical report, NEC Research Institute. Presented at DIMACS Workshop on DNA Based Computing, Princeton, 4 April.

Stemmer, W. P. C., 1994. Rapid evolution of a protein in vitro by DNA shuffling. Nature 370: 389–391.

Vahey, M. T., M. T. Wong, and N. L. Michael., 1995. A standard PCR protocol: Rapid isolation of DNA and PCR assay for β-globin. In PCR Primer, ed. C. W. Dieffenbach, and G. S. Dveksler, 17–22. Plainview, N.Y.: Cold Spring Harbor Laboratory Press.

Wang, L., Q. Liu, A. G. Frutos, S. D. Gillmor, A. J. Thiel, T. C. Strother, A. E. Condon, R. M. Corn, M. G. Lagally, and L. M. Smith., 2000. Surface-based DNA computing operations: DESTROY and READOUT. In Preliminary Proceedings of the Fourth DIMACS Workshop on DNA Based Computers, ed. L. Kari, 247 (poster).

Winfree, E. 1996. On the computational power of DNA annealing and ligation. In DNA Based Computers. Vol. 27 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, ed. R. J. Lipton, and E. D. Baum, 199–221. Providence: American Mathematical Society.

Winfree, E. 2000. Whiplash PCR for O(1) computing. In Preliminary Proceedings of the Fourth DIMACS Workshop on DNA Based Computers, ed. L. Kari, 175–188.

Winfree, E., and D. K. Gifford, eds., 2000. DNA Based Computers V, Vol. 54 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. Providence: American Mathematical Society.

Winfree, E., F. Lin, L. Wenzler, and N. C. Seeman., 1998. Design and self-assembly of two-dimensional DNA crystals. Nature 394: 539–545.

Winfree, E., X. Yang, and N. C. Seeman., 1998. Universal computation via self-assembly of DNA: Some theory and experiments. In DNA Based Computers II. Vol. 44 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, ed. L. F. Landweber, and E. B. Baum, 191–214. Providence: American Mathematical Society.

Yoshinobu, T., Y. Aoi., K. Tanizawa, and H. Iwasaki., 2000. Ligation errors in DNA computing. In Preliminary Proceedings of the Fourth DIMACS Workshop on DNA Based Computers, ed. L. Kari, 245–246.