Programming in Biomolecular Computation: Programs, Self-Interpretation and Visualisation

Published in Volume XXI, Issue 1, 2011, pages 73-106

Authors: L. Hartmann, N.D. Jones, J.G. Simonsen, S.B. Vrist

Abstract

Our goal is to provide a top-down approach to biomolecular computation. In spite of widespread discussion about connections between biology and computation, one question seems notable by its absence: Where are the programs? We identify a number of common features in programming that seem conspicuously absent from the literature on biomolecular computing; to partially redress this absence, we introduce a model of computation that is evidently programmable, by programs reminiscent of low-level computer machine code; and at the same time biologically plausible: its functioning is defined by a single and relatively small set of chemical-like reaction rules. Further properties: the model is stored-program: programs are the same as data, so programs are not only executable, but are also compilable and interpretable. It is universal: all computable functions can be computed (in natural ways and without arcane encodings of data and algorithm); it is also uniform: new “hardware” is not needed to solve new problems; and (last but not least) it is Turing complete in a strong sense: a universal algorithm exists, that is able to execute any program, and is not asymptotically inefficient.

Full Text (PDF)

References

[1] L. M. Adleman. On constructing a molecular computer. In DIMACS: series in Discrete Mathematics and Theoretical Computer Science, pages 1-21. American Mathematical Society, 1996.

[2] R. Backofen and P. Clote. Evolution as a computational engine. In Proceedings of the Annual Conference of the European Association for Computer Science Logic, pages 35-55. Springer-Verlag, 1996.

[3] D. Beaver. Computing with DNA. Journal of Computational Biology, 2(1):1-7, 1995.

[4] Y. Benenson. Biocomputers: from test tubes to live cells. Molecular BioSystems, 5(7):675-685, 2009.

[5] Y. Benenson, R. Adar, T. Paz-Elizur, Z. Livneh, and E. Shapiro. DNA molecule provides a computing machine with both data and fuel. In Proc Natl Acad Sci U S A, volume 100 of Lecture Notes in Computer Science, pages 2191-2196, 2003.

[6] Bohringer, Karl-Friedrich, Paulisch, and F. Newbery. Using constraints to achieve stability in automatic graph layout algorithms. In Proceedings of ACM CHI’90 Conference on Human Factors in Computing Systems, Constraint Based UI Tools, pages 43-51, 1990.

[7] L. Cardelli and G. Zavattaro. On the computational power of biochemistry. In AB ’08: Proceedings of the 3rd international conference on Algebraic Biology, pages 65-80, Berlin, Heidelberg, 2008. SpringerVerlag.

[8] L. Cardelli and G. Zavattaro. Turing universality of the biochemical ground form. Mathematical Structures in Computer Science, 19, 2009.

[9] P. Chapman. Life universal computer. http://www.igblan.freeonline.co.uk/igblan/ca/, (November), 2002.

[10] M. Clavel, F. Dur´an, S. Eker, P. Lincoln, N. Mart´ı-Oliet, J. Meseguer, and C. L. Talcott, editors. All About Maude – A High-Performance Logical Framework, How to Specify, Program and Verify Systems in Rewriting Logic, volume 4350 of Lecture Notes in Computer Science. Springer, 2007.

[11] A. Danchin. Bacteria as computers making computers. FEMS Microbiology Reviews, 33(1):3 – 26, 2008.

[12] V. Danos, J. Feret, W. Fontana, and J. Krivine. Abstract interpretation of cellular signalling networks. In VMCAI, volume 4905 of VMCAI, Lecture Notes in Computer Science, pages 83-97, 2008.

[13] V. Danos and C. Laneve. Formal molecular biology. Theor. Comp. Science, 325:69 – 110, 2004.

[14] P. Degano and R. Gorrieri, editors. Computational Methods in Systems Biology, 7th International Conference, CMSB 2009, Bologna, Italy, August 31-September 1, 2009. Proceedings, volume 5688 of Lecture Notes in Computer Science. Springer, 2009.

[15] G. Delzanno, C. D. Giusto, M. Gabbrielli, C. Laneve, and G. Zavattaro. The kappa-lattice: Decidability boundaries for qualitative analysis in biological languages. In Degano and Gorrieri [14], pages 158-172.

[16] P. Eades. A heuristic for graph drawing. Congressus Numerantium, 42:149-160, 1984.

[17] P. Eades, W. Lai, K. Misue, and K. Sugiyama. Preserving the mental map of a diagram. In COMPUGRAPHICS ’91, volume I, pages 34-43, 1991.

[18] R. Fleischer and C. Hirsch. Graph drawing and its applications. In M. Kaufmann and D. Wagner, editors, Drawing Graphs: Methods and Models, number 2025 in Lecture Notes in Computer Science, LNCS, chapter 1, pages 1-22. Springer-Verlag, Berlin, Germany, 2001.

[19] A. Frick, A. Ludwig, and H. Mehldau. A fast adaptive layout algorithm for undirected graphs. In R. Tamassia and I. G. Tollis, editors, Graph Drawing, volume 894 of Lecture Notes in Computer Science, pages 388-403. Springer, 1994.

[20] T. M. J. Fruchterman and E. M. Reingold. Graph drawing by forcedirected placement. Software: Practice and Experience, 21(11):1129- 1164, 1991.

[21] M. Gardner. Mathematical recreations. Scientific American, October 1970.

[22] U. D. E. Giral, A. Cetintas, A. Civril, and E. Demir. A compound graph layout algorithm for biological pathways. In Pach [36], pages 442-447.

[23] M. L. Guerriero, D. Prandi, C. Priami, and P. Quaglia. Process calculi abstractions for biology. Technical report, University of Trento, Italy, Jan. 01, 2006.

[24] M. Hagiya. Designing chemical and biological systems. New Generation Comput., 26(3):295, 2008.

[25] L. Hartmann, N. Jones, and J. Simonsen. Programming in biomolecular computation. In CS2BIO ’09: Proceedings of the 1st International Workshop on Interactions between Computer Science and Biology, Electronic Notes on Theoretical Computer Science series. Elsevier.

[26] J. Heer. Prefuse: a software framework for interactive information visualization. Master’s thesis, University of California, Berkeley, 2004.

[27] J. E. Jones. On the determination of molecular fields. ii. from the equation of state of a gas. Proceedings of the Royal Society of London. Series A, 106(738):463-477, October 1924.

[28] N. Jones, C. Gomard, and P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice Hall International Series in Computer Science. Prentice Hall, 1993.

[29] N. D. Jones. Computability and complexity: from a programming perspective. MIT Press, Cambridge, MA, USA, 1997.

[30] T. Kamada and S. Kawai. An algorithm for drawing general undirected graphs. Information Processing Letters, 31(1):7-15, 1989.

[31] L. Kari. Biological computation: How does nature compute? Technical report, University of Western Ontario, 2009.

[32] L. Kari and G. Rozenberg. The many facets of natural computing. Commun. ACM, 51(10):72-83, 2008.

[33] M. Minsky. Computation: finite and infinite machines. Prentice Hall, 1967.

[34] K. Misue, P. Eades, W. Lai, and K. Sugiyama. Layout adjustment and the mental map. Journal of Visual Languages and Computing, 6(2):183 – 210, 1995.

[35] C. L. Nehaniv. Asynchronous automata networks can emulate any synchronous automata network. International Journal of Algebra and Computation, 14(5-6):719-739, 2004.

[36] J. Pach, editor. Graph Drawing, 12th International Symposium, GD 2004, New York, NY, USA, September 29 – October 2, 2004, Revised Selected Papers, volume 3383 of Lecture Notes in Computer Science. Springer, 2004.

[37] T. Ran, S. Kaplan, and E. Shapiro. Molecular implementation of simple logic programs. Nat Nano, 4(10):642-648, Oct 2009.

[38] G. Sander. Graph layout for applications in compiler construction. Theor. Comput. Sci., 217(2):175-214, 1999.

[39] E. Shapiro. Mechanical Turing machine: Blueprint for a biomolecular computer. Technical report, Weizmann Institute of Science, 1999.

[40] E. Shapiro and Y. Benenson. Bringing DNA computers to life. Scientific American, 294:44-51, 2006.

[41] M. A. D. Storey, F. Fracchia, and H. M¨uller. Customizing a Fisheye View Algorithm to Preserve the Mental Map. Journal of Visual Languages and Computing, 10(3):245-267, 1999.

[42] C. Talcott. Pathway logic. In Formal Methods for Computational Systems Biology, volume 5016 of LNCS, pages 21-53. Springer, 2008. 8th International School on Formal Methods for the Design of Computer, Communication, and Software Systems.

[43] A. Turing. On computable numbers with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42(2):230-265, 1936-7.

[44] J. von Neumann and A. W. Burks. Theory of Self-Reproducing Automata. Univ. Illinois Press, 1966.

[45] E. Winfree. Toward molecular programming with DNA. SIGOPS Oper. Syst. Rev., 42(2):1-1, 2008.

[46] E. Winfree, X. Yang, and N. C. Seeman. Universal computation via self-assembly of DNA: Some theory and experiments. In DNA Based Computers II, volume 44 of DIMACS, pages 191-213. American Mathematical Society, 1996.

[47] S. Wolfram. A New Kind of Science. Wolfram Media, January 2002.

[48] P. Yin, A. J. Turberfield, and J. H. Reif. Design of an autonomous dna nanomechanical device capable of universal computation and universal translational motion. In Tenth International Meeting on DNA Based Computers (DNA10), volume 3384 of Lecture Notes in Computer Science, pages 426-444, 2005.

Bibtex

@article{sacscuza:hartmann2011pibcpsav,
  title={Programming in Biomolecular Computation: Programs, Self-Interpretation and Visualisation},
  author={L. Hartmann and N.D. Jones and J.G. Simonsen and S.B. Vrist},
  journal={Scientific Annals of Computer Science},
  volume={21},
  number={1},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2011},
  pages={73--106},
  publisher={``A.I. Cuza'' University Press}
}