Arithmetical Analysis of Biomolecular Finite Automaton

• Autorzy: Krasiński T. , Sakowski S. , Waldmajer J. , Popławski T.
• Języki publikacji: EN

Abstrakty

EN

In the paper we present a theoretical analysis of extension of the finite automaton built on DNA (introduced by the Shapiro team) to an arbitrary number of states and symbols. In the implementation we use a new idea of several restriction enzymes instead of one. We give arithmetical conditions for the existence of such extensions in terms of ingredients used in the implementation.

Słowa kluczowe

EN

biomolecular computer; DNA automaton; DNA computing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 128, nr 4
• Strony: 463--474
• Opis fizyczny: Bibliogr. 27 poz., rys.

Twórcy

autor

Krasiński T.

• Faculty of Mathematics and Computer Science, University of Łódź, Banacha 22, 90-238 Łódź, Poland

autor

Sakowski S.

• Faculty of Mathematics and Computer Science, University of Łódź, Banacha 22, 90-238 Łódź, Poland

autor

Waldmajer J.

• Group of Logic, Language and Information, Department of Philosophy, University of Opole, Katowicka 89, 45-061 Opole, Poland

autor

Popławski T.

• Department of Molecular Genetic, University of Łódź, Pomorska 141/143, 90-236 Łódź, Poland

Bibliografia

• [1] Adar R., Benenson Y., Linshiz G., Rosner A., Tishby N., Shapiro E.: Stochastic computing with biomolecular automata, PNAS 101, 9960-9965 (2004).
• [2] Adleman, L.: Molecular computation of solutions to combinatorial problems, Science 226, 1021-1024 (1994).
• [3] Bennett, C.: Logical reversibility of computation, IBM J.R.D. 17, 525-532, (1973).
• [4] Benenson, Y., Paz-Elizur, T., Adar, R., Keinan, E., Livneh, Z., Shapiro, E.: Programmable and autonomous computing machine made of biomolecules. Nature 414, 430-434 (2001).
• [5] Benenson, Y., Adar, R., Paz-Elizur, T., Livneh, Z., Shapiro, E.: DNA molecule provides a computing machine with both data and fuel. PNAS 100, 2191-2196 (2003).
• [6] Benenson Y., Gil B., Ben-Dor U., Adar R., Shapiro E.: An autonomous molecular computer for logical control of gene expression. Nature 429, 423-429 (2004).
• [7] Cavaliere, M., Jonoska, N., Yogev, S., Piran, R., Keinan, E., Seeman, N. Biomolecular implementation of computing devices with unbounded memory. LNCS 3384, 35-49 (2005).
• [8] Chen P., Jing L., Jian Z., Lin H., Zhizhou Z.: 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(2007).
• [9] Faulhammer D., Cukras A., Lipton R., Landweber L.: Molecular compution: RNA solutions to chess problems. PNAS 97, s. 1385-1389 (1999).
• [10] Krasiński T., Sakowski S.: Extended Shapiro Finite State Automaton. Foundations of Computing and Decision Science 33, 241-255 (2008).
• [11] Krasmski T., Sakowski S., Popławski T.: Autonomous push-down automaton built on DNA. Informatica 36, 263-276 (2012).
• [12] Lipton R.: DNA solution of hard computational problems. Science 268, 542-545 (1995).
• [13] Ogihara M., Ray A.: Simulating Boolean circuits on a DNA computer. Proc. of First Ann. Inter. Conf. on Computational Molecular Biology, 326-331 (1997).
• [14] Qian L., Winfree E.: Scaling Up Digital Circuit Computation with DNA Strand Displacement Cascades. Science 6034, 1196-1201 (2011).
• [15] Paun G., Rozenberg G., Salomaa, A.: DNA Computing. New Computing Paradigms. Springer. Berlin, Heidelberg, New York 1998.
• [16] Ran T., Kaplan S., Shapiro E.: Molecular implementation of simple logic program. Nature Nanotechnology 10, 642-648 (2009).
• [17] Reif J., Sahu S.: Autonomous programmable DNA nanorobotic devices using DNAzymes. Theoretical Computer Science 410(15): 1428-1439 (2009).
• [18] Rothemund P.: A DNA and restriction enzyme implementation of Turing machines. DIMACS 27, 75-120 (1995).
• [19] Seelig, G., Soloveichik D., Zhang D., Winfree E.: Enzyme-free nucleic acid logic circuits. Science 314, 1585-8 (2006).
• [20] Sekiguchi H., Komiya K., Kiga D. Yamamura M.: A Realization of DNA Molecular Machine That Walks Autonomously by Using a Restriction Enzyme. LNCS 4848, 54-65 (2008).
• [21] Soloveichik D., Winfree E.: The Computational Power of Benenson Automata. Theoretical Computer Science 344, 279-297 (2005).
• [22] Soreni, M., Yogev, S., Kossoy, E., Shoham, Y. and Keinan, E.: Parallel biomolecular computation on surfaces with advancedfinite automata. J. Am. Chem. Soc., 127, 3935-3943 (2005).
• [23] Stojanovic M., Stefanovic D.: A Deoxyribozime-Based Molecular Automaton. Nature Biotechnology 21, 1069-1074 (2003).
• [24] Unold, O., Troc M., Dobosz T., Trusiewicz A.: Extended molecular computing model. WSEAS Trans. Biol. Biomed. 1, 15-19 (2004).
• [25] Wasiewicz, P., Janczak, T., Mulawka, J. Płucienniczak, A.: The inference based on molecular computing. Cybernetics and Systems 31, 283-315 (2000).
• [26] Yin, P., Turberfield, A., Reif, J.: Designs of Autonomous Unidirectional Walking DNA Devices. LNCS 3384, 7-10 (2004).
• [27] Yurke B., Turberfield A., Mills A., Simmel F., Neumann J.: A DNA-fuelled molecular machine made of DNA. Nature 406, 605-608 (2000).