2The idea of DNA computing came in Adelman’s mind when he was reading the classic text “the molecular biology of the gene”, co-authored by James D.Watson of Watson-Crick family. He resembled the formation of new DNA of operation of Turing machine which is described is in 1936 by Alan M.Turing, the famous British mathematician Turing machine was not intended to be real but rather to be conceptual. He inspired with the DNA polymers, a single molecule that “hops” into a strand of DNA and slids along it, “reading” each base it passes and “writing” it complement onto a new, growing DNA strand which is similar turing machine which had two tapes, moved along the “input” tape reading data while simultaneously moving along “output” tape reading and writing other.
In 1994, Leonard Adleman1 solved a particular type of NP problem14 (nondeterministic polynomial) which is known as Hamiltonian Path Problem1,2,4,6,10 or Travelling Salesman Problem, using DNA. A directed graph G with designated vertices Vin and Vout, is said to have a Hamiltonian path if and only if there exist a sequence of compatible ‘one way’ edges e1,e2…ez, which begins at Vin and ends at Vout and enter every other vertex exactly once. He found the shortest path between seven cities by using the following algorithm:
Generate random paths through the graph.
Keep only those paths which begin with Vin and end with Vout.
If the graph has n vertices than keep only those paths which enter exactly n vertices.
Keep only those paths which enter all the vertices of the graph at least once.
If any path remaining “yes”, otherwise “no”.
He implemented his algorithm on DNA by carrying out various chemical reactions such as first associating some sequence of DNA to each vertex than ligation reaction, amplification, purification and using some gels (Agarose gel). And finally, after seven days of lab work he came across the solution of Hamiltonian path problem.
Inspired by the work of Adleman, on 28th April, 1995, Richard J. Lipton3 proposed a paper to solve famous SAT problem (The Boolean Satisfiability problem) of computer science. A SAT5 problem can be simply described as problem of deciding weather a given Boolean expression has any correct solutions; more precisely ; it can be stated as the following question: Given a Boolean expression, do there exist any assignments of truth values (True and False) to the variables of the expression such that the expression as a whole evaluates to be true? SAT is also a type of NP- problem. Researchers have used DNA computing with Acrydite™ gel7 technology to solve time tabling problem. Apart from this various NP problems such as Clique problem, Knapsack problem8 are solved by researchers by using the DNA computing.
DNA Computing is a new technology which is based on the enormous information capacity, massive parallelism in DNA and also on the biological molecules that can store huge amount of information and able to perform operation similar to that of computers. 18Today’s computer use binary codes – 1’s and 0’s or ON’s and OFF’s, which are basis of all possible calculations that a computer performs. In the same way DNA computer is collection of the strands that have been specially selected to help in the search of solution of some problem.
