A review of models and practical implementations of DNA computation

Tadeusz Krasiński, Sebastian Sakowski


In this paper we discuss various possibilities of using DNA to information processing. We describe some practical implementations and theoretical models of computation built on DNA.


algorithm; theoretical model; DNA computing

Full Text:

PDF (Polski)


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

Amos M.: Theoretical and Experimental DNA Computation. Springer, Berlin, Heidelberg, New York 2005.

Benenson Y., Paz-Elizur T, Adar R., Keinan E., Livneh Z., Shapiro E.: Programmable and autonomous computing machine made of biomolecules. Nature 414, 2001, s. 430-434.4.

Benenson Y., Adar R., Paz-Elizur T., Livneh Z., Shapiro E.: DNA molecule provides a computing machine with both data and fuel. PNAS 100, 2003, s. 2191-2196.

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

Bennett C: Logical reversibility of computation. IBM J. R.&D. 17, 1973, s. 525-532,.

Faulhammer D., Cukras A., Lipton R., Landweber L.: Molecular compution: RNA solutions to chess problems. PNAS 97, 1999, s. 1385-138.

Head T.: Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behavior. Bulletin of Mathematical Biology 49, 1987, s. 737-759.

Hopcroft J., Ullman J.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979.

Krasiński T.: Automaty i języki formalne. Wydawnictwo UL, Łódź 2007.

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

Ogihara M., Ray A.: Simulating Boolean circuits on a DNA computer. Proceeding of the First Annual International Conference on Computational Molecular Biology, 1997, s. 226-231.

Paun G.: On the power of the splicing operation. Internationals Journal of Computer Mathematics 59,1995, s. 27-35.

Paun G., Rozenberg G., Salomaa, A.: DNA Computing. New Computing Paradigms. Springer. Berlin, Heidelberg, New York 1998.

Paun G.: Membrane computing: An introduction. Springer, Berlin 2002.

Paun G.: Computing with membrane. Journal of Computer and System Science 61, 2000, s. 108-143.

Rothemund P., Winfree E.: The program-size complexity of self-assembled squares (extended abstract). Proceedings of the Third-Second Annual ACM Symposiom on Theory of Computing, ACM Press, 1999, s. 459-468.

Rothemund P., Papadakis N., Winfree E.: Algorithmic self-assembly of DNA Sierpiński triangles. PLoS Biol. 424, 2004.

Rothemund P.: A DNA and restriction enzyme implementation of Turing machines. American Mathematical Society, 1995, s. 75-120.

Seeman N: DNA Nicks and Nodes and Nanotechnology. Nano Letters, 2001, s. 22-26.

Seeman N: DNA engineering and its application to nanotechnology. Trends Biotechnol. 17,4,1999, s. 37-443.

Soreni M., Yogev S., Kossoy E., Shoham Y., Keinan E.: Parallel biomolecular computation on surfaces with advanced finite automata. J. Am. Chem. Soc, 127, 2005, s. 3935-3943.

Stojanovic M., Stefanovic D.: A Deoxyribozime-Based Molecular Automaton. Nature Biotechnology 21,2003, s. 1069-1074.

Stryer L., Tymoczko J., Berg J.: Biochemia. PWN, Warszawa 2005.

Unold O., Troć M., Dobosz T., Trusiewicz A.: Extended molecular computing model. WSEAS Trans. Biol. Biomed. 1,2004, s. 15-19.

Winfree E., Liu F., Wenzler L., Seeman N.: Design and self-assembly of twodimensional DNA crystals. Nature 394,1998, s. 539-544.

Węgrzyn S., Grają J., Bugajski S., Gibas M., Winiarczyk R., Znamirowski L., Miszczak J., Nowak S.: Nano i kwantowe systemy informatyki. Wyd. Pol. ŚL, Gliwice 2003.

Węgrzyn S., Znamirowski L.: Zarys nanonauki i informatycznych molekularnych nanotechnologii. Wyd. Pol. ŚL, Gliwice 2007.

DOI: http://dx.doi.org/10.21936/si2008_v29.n4A.517