DNA Based Computing

Biological and mathematical operations have some similarities, despite their respective complexities:

1. The very complex structure of a living being is the result of applying simple operations to initial information encoded in a DNA sequence;
2. The result f(w) of applying a computable function to an argument w can be obtained by applying a combination of basic simple functions to w.

For the same reasons that DNA was presumably selected for living organisms as a genetic material, its stability and predictability in reactions, DNA strings can also be used to encode information for mathematical systems.

To solve the Hamiltonian Path problem, the objective is to find a path from start to end going through all the points only once. This problem is difficult for conventional computers to solve because it is a 'non-deterministic polynomial time problem' (NP). NP problems are intractable with deterministic (conventional/serial) computers, but can be solved using non-deterministic (massively parallel) computers. A DNA computer is a type of non-deterministic computer. Dr. Leonard Adleman (1994) was struck with the idea of using sequences of stored nucleotides (Adenine (A), Guanine (G), Cytosine (C), Thymine (T)) in molecules of DNA to store computer instructions and data in place of the sequences of electrical, magnetic or optical on-off states (0, 1 – Boolean Logic) used in today’s computers. The Hamiltonian Path problem was chosen because it is known as 'NP-complete'; every NP problem can be reduced to a Hamiltonian Path problem.

The following algorithm solves the Hamiltonian Path problem:
1. Generate random paths through the graph.
2. Keep only those paths that begin with the start city (A) and conclude with the end city (G).
3. If the graph has n cities, keep only those paths with n cities. (n = 7)
4. Keep only those paths that enter all cities at least once.
5. Any remaining paths are solutions.
Unrestricted model of DNA computing is the key to solve the problem in five steps in the above algorithm. These operations can be used to 'program' a DNA computer.
o Synthesis of a desired strand
o Separation of strands by length
o Merging: pour two test tubes into one to perform union
o Extraction: extract those strands containing a given pattern
o Melting/Annealing: break/bond two ssDNA molecules with complementary sequences
o Amplification: use PCR to make copies of DNA strands
o Cutting: cut DNA with restriction enzymes
o Ligation: Ligate DNA strands with complementary sticky ends using ligase
o Detection: Confirm presence/absence of DNA in a given test tube
Since Adleman's original experiment, several methods to reduce error and improve efficiency have been developed. The Restricted model of DNA computing solves several physical problems with the Unrestricted model. The Restricted model simplifies the physical obstructions in exchange for some additional logical considerations. The purpose of this restructuring is to simplify biochemical operations and reduce the errors due to physical obstructions.

The Restricted model of DNA computing:
o Separate: isolate a subset of DNA from a sample
o Merging: pour two test tubes into one to perform union
o Detection: Confirm presence/absence of DNA in a given test tube
Despite these restrictions, this model can still solve NP-complete problems such as the 3-colourability problem, which decides if a map can be coloured with three colours in such a way that no two adjacent territories have the same colour. Error control is achieved mainly through logical operations, such as running all DNA samples showing positive results a second time to reduce false positives. Some molecular proposals, such as using DNA with a peptide backbone for stability, have also been recommended.
DNA computing brings great optimism to revolutionize the computer industry in the use of molecules of DNA in a computer, in place of electronics, circuits and magnetic or optical storage media. Obviously, to perform one calculation at a time (serial logic), DNA computers are not a viable option. However, if one wanted to perform many calculations simultaneously (parallel logic), a computer such as the one described above can easily perform 1014 million instructions per second (MIPS). DNA computers also require less energy and space. In DNA computers data are entered and coded into DNA by chemical reactions and retrieved by synthesizing a key data and make them react with existing strands. Here the key DNA will stick to the required DNA strands containing data.

In short, in a DNA computer, the input and output are both strands of DNA. Furthermore, a computer in which the strands are attached to the surface of a chip (DNA chip) can now solve difficult problems quite quickly.