A Solution to the Problem of the Maximal Number of Symbols for Biomolecular Computer

Jacek Waldmajer, Sebastian Sakowski


The authors present a solution to the problem of generating the maximum possible number of symbols for a biomolecular computer using restriction enzyme BbvI and ligase as the hardware, and transition molecules built of double-stranded DNA as the software. The presented solution offers an answer to the open question, in the algorithm form, of the maximal number of symbols for a biomolecular computer that makes use of the restriction enzyme BbvI.

Full Text:



Adleman, L. (1994). Molecular computation of solutions to combinatorial problems. Science, 226, 1021-1024.

Benenson, Y., Paz-Elizur, T., Adar, R., Keinan, E., Livneh, Z., & Shapiro, E. (2001).

Programmable and autonomous computing machine made of biomolecules. Nature, 414,


Benenson, Y., Adar, R., Paz-Elizur, T., Livneh, Z., & Shapiro, E. (2003). DNA molecule

provides a computing machine with both data and fuel. PNAS, 100, 2191-2196.

Benenson, Y., Gil, B., Ben-Dor, U., Adar, R., Shapiro, E. (2004). An autonomous molecular computer for logical control of gene expression. Nature, 429, 423{429.

Bennett, Ch. (1982). The Thermodynamics of computation - a Review. International Journal of Theoretical Physics, 21(12), 905-940.

Bennett, Ch., & Landauer, R. (1985). The fundamental physical limits of computation. Scientifc American, 253, 48-56.

Chen, P., Jing, L., Jian, Z., Lin, H., Zhizhou, Z. (2007). Differential dependence on DNA ligase of type II restriction enzymes: a practical way toward ligase-free DNA automaton. Biochem. and Bioph. Research Communications, 353, 733-737.

Feynman, R. P. (1961). There's plenty of room at the bottom, In D. Gilbert (Ed.) Miniaturization, Reinhol, 282-296.

Gopinath, A., Miyazono, E., Faraon, A., Rothemund, P.W.K. (2016). Engineering and mapping nanocavity emission via precision placement of DNA origami. Nature, 535, 401-405.

Krasinski, T., Sakowski, S., Waldmajer, J., Poplawski, T. (2013). Arithmetical analysis of biomolecular finite automaton. Fundamenta Informaticae, 128, 463-474.

Ran, T., Douek, Y., Milo, L., & Shapiro, E. (2012). A programmable NOR-based device for transcription profile analysis. Scientifc reports, 2, 641.

Rothemund P. W. K. (1995). DNA and restriction enzyme implementation of Turing machines. Discrete Mathematics and Theoretical Computer Science, 27, 75-120.

Rothemund, P. W., Papadakis, N., & Winfree, E. (2004). Algorithmic self-assembly of DNA Sierpinski triangles. PLoS biology, 2(12), 2041-2053.

Rothemund, P.W.K (2006). Folding DNA to Create Nanoscale Shapes and Patterns. Nature, 440, 297-302.

Seeman, N. (2001). DNA Nicks and Nodes and Nanotechnology. Nano Letters, 1, 22-26.

Sakowski, S., Krasinski, T., Sarnik, J., Blasiak, J., Waldmajer, J., Poplawski, T. (2017). A detailed experimental study of a DNA computer with two endonucleases. Zeitschrift fur Naturforschung C, 72(7-8), 303-313.

Sakowski, S., Krasinski, T., Waldmajer, J., Sarnik, J., Blasiak, J., & Poplawski, T. (2017). Biomolecular computers with multiple restriction enzymes. Genetics and molecular biology, 40(4), 860-870.

Soreni, M., Yogev, S., Kossoy E., Shoham Y., Keinan E. (2005). Parallel biomolecular computation on surfaces with advanced finite automata. Journal of the American Chemical Society 127, 3935-3943.

Unold, O., Troc, M., Dobosz, T., Trusiewicz, A. (2004). Extended molecular computing model. WSEAS Transactions on Biology and Biomedicine 1, 15-19.

Waldmajer, J., Bonikowski, Z., Sakowski, S. (2019). Theory of tailor automata. Theoretical Computer Science, in press, DOI: https://doi.org/10.1016/j.tcs.2019.02.002

Whitesides, G. M., Mathias, J. P., & Seto, C. T. (1991). Molecular self-assembly and nanochemistry: a chemical strategy for the synthesis of nanostructures. Science, 254(5036), 1312-1319.

DOI: https://doi.org/10.31449/inf.v43i4.2725

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.