DNA Computing And Optimization Of The Algorithm

Information-processing capabilities of organic molecules can be used in computers to replace digital switches; this is the basic idea in DNA computing. There are obvious limits to miniaturization with current computer technologies. For a drastic innovation, it was suggested already a long time ago that the basic components should go to the molecular level. The result would be much smaller than anything we can make with present technology. Quantum computing and DNA computing are two recent manifestations of this suggestion. This work isabout the latter. DNA computing are based on two fundamental features: (1) The massive parallelism of DNA strands; (2) Watson-Crick complementarity. Classic theoretical computer science is grounded on rewriting operations; this is true for most automata and language theory models. As we shall see, nature manipulates the DNA molecules in a computing manner by using operations of a quite different type: cut and paste, adjoining, insertion, deletion, etc. It has been proved that by using such operations we can build computing models that are equivalent in power with Turing machines.Previous research on DNA computing has shown that DNA algorithms are useful to solve some combinatorial problems, such as the Hamiltonian path problem, traveling salesman problem, 3-SAT problem, breaking the DES...