Adleman recently described how to solve a 7-node instance of
the Hamiltonian Path Problem using tools from molecular biology
(Science, November 1994). A major goal of subsequent research in this
area is to understand how DNA computing can be used to solve NP-hard
problems. Simple algorithms of Adleman and Lipton showed that 3Sat
and 3-Coloring can be solved in principle, but since their algorithms
are essentially exhaustive search, they can only be run on small
instances and hence can never be practical.
In this talk, we describe the pioneering work of Adleman and,
subsequently, Lipton, on DNA computing. We then show how improved
algorithms can be developed for the 3-Coloring and Independent Set
problems. Our algorithms use only the DNA operations proposed by
Adleman and Lipton, but combine them in more powerful ways, and use
polynomial preprocessing on a standard computer to tailor them to the
specific instance to be solved. Our results demonstrate that DNA
computing can do much more than just exhaustive search. Further
research in this direction will help determine whether or not DNA
computing can be viable for NP-hard problems.
We also present a probabilistic analysis of errors that arise in
generating the solution space for DNA computation.