DNA computing is a form of computing which uses DNA and molecular biology, instead of the traditional silicon-based computer technologies. A single gram of DNA about the size of a cube with volume of 1cm³ can hold as much information as a trillion compact discs. Originally, the word computing was synonymous with counting and calculating, and a science that deals with the original sense of computing mathematical calculations. ... Jump to: navigation, search Space-filling model of a section of DNA molecule Deoxyribonucleic acid (DNA) is a nucleic acid that contains the genetic instructions specifying the biological development of all cellular forms of life (and many viruses). ... Molecular biology is the study of biology at a molecular level. ... Jump to: navigation, search A computer is a device or machine for processing information from data according to a program — a compiled list of instructions. ... This article needs to be cleaned up to conform to a higher standard of quality. ...

This field was initially developed by Leonard Adleman of the University of Southern California. In 1994, Adleman demonstrated a proof-of-concept use of DNA as form of computation which was used to solve the seven-point Hamiltonian path problem. Since the initial Adleman experiments, advances have been made, and various Turing machines have been proven to be constructable. Leonard Adleman Leonard Adleman (born December 31, 1945) is a theoretical computer scientist and professor of computer science and molecular biology at the University of Southern California. ... Jump to: navigation, search The University of Southern California (also known as USC, SC, Southern California, and Southern Cal), Californias oldest private research university, is located in the urban center of Los Angeles, California. ... Jump to: navigation, search 1994 was a common year starting on Saturday of the Gregorian calendar, and was designated the International year of the Family. ... A proof of concept is a short and/or incomplete realization (or synopsis) of a certain method or idea(s) to demonstrate its feasibility. ... In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem is the problem of determinining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph. ... Jump to: navigation, search An artistic representation of a Turing Machine . ...

There are works over one dimensional lengths, bidimensional tiles, and even three dimensional DNA graphs processing.

On April 28, 2004, Ehud Shapiro and researchers at the Weizmann Institute announced in the journal Nature that they had constructed a DNA computer. This was coupled with an input and output module and is capable of diagnosing cancerous activity within a cell, and then releasing an anti-cancer drug upon diagnosis. Jump to: navigation, search April 28 is the 118th day of the year (119th in leap years) in the Gregorian Calendar, with 247 days remaining. ... Jump to: navigation, search 2004 (MMIV) was a leap year starting on Thursday of the Gregorian calendar. ... Ehud Shapiro (born 1955) is a Jewish scientist in Israel who is developing a DNA computer. ... The Weizmann Institute of Science (מכון ויצמן למדע) is an institute of higher learning and research in Rehovot, Israel. ... Nature is one of the oldest and most reputable general-purpose scientific journals, first published on November 4, 1869. ... Jump to: navigation, search When normal cells are damaged or old they undergo apoptosis; cancer cells, however, avoid apoptosis. ...

DNA computing is fundamentally similar to parallel computing -- we take advantage of the many different molecules of DNA to try many different possibilities at once. Parallel computing is the simultaneous execution of the same task (split up and specially adapted) on multiple processors in order to obtain faster results. ...

For certain specialized problems, DNA computers are faster and smaller than any other computer built so far. But DNA computing does not provide any new capabilities from the standpoint of computational complexity theory, the study of which computational problems are difficult. For example, problems which grow exponentially with the size of the problem (EXPSPACE problems) on von Neumann machines still grow exponentially with the size of the problem on DNA machines. For very large EXPSPACE problems, the amount of DNA required is too large to be practical. (Quantum computing, on the other hand, does provide some interesting new capabilities). Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) space, where p(n) is a polynomial function of n. ... A von Neumann machine is a model created by John von Neumann for a computing machine that uses a single storage structure to hold both the set of instructions on how to perform the computation and the data required or generated by the computation. ... Molecule of alanine used in NMR implementation of error correction. ...

References

• Leonard M. Adleman. [Molecular Computation Of Solutions To Combinatorial Problems]. Science, volume 266, p.1021-1024. November 2004. The first DNA computing paper. Describes a solution for the directed Hamiltonian path problem.
• Martyn Amos. Theoretical and Experimental DNA Computation. Springer, June 2005. The first general text to cover the whole field.
• Dan Boneh, Christopher Dunworth, Richard J. Lipton, and Jiri Sgall. On the Computational Power of DNA. DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science, volume 71. 1996. Describes a solution for the boolean satisfiability problem.
• Gheorge Paun, Grzegorz Rozenberg, Arto Salomaa, DNA Computing - New Computing Paradigms, Springer, 1998. The book starts with an introduction to DNA-related matters, the basics of biochemistry and language and computation theory, and progresses to the advanced mathematical theory of DNA computing.
• Lila Kari, Greg Gloor, Sheng Yu. Using DNA to solve the Bounded Post Correspondence Problem. Theoretical Computer Science, volume 231, number 2, p.192-203. 2000. Describes a solution for the bounded Post correspondence problem, a hard-on-average NP-complete problem.
• The history of the International Meeting on DNA Computing (Proceedings - Links) -- [[1]]

In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem is the problem of determinining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph. ... The Boolean satisfiability problem (SAT) is a decision problem considered in complexity theory. ... The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. ...

External links

• How Stuff Works explanation
• Physics Web
• Ars Technica
• A Bibliography of Molecular Computation and Splicing Systems
• NY Times DNA Computer for detecting Cancer