HAMILTONIAN PATH PROBLEM

In 1994, Leonard Adleman introduced the idea of using DNA to solve complex mathematical problem. Adleman, a computer scientist at the University of Southern California, came to the conclusion that DNA had computational potential after reading the book ‘Molecular Biology of the Gene’ written by James Watson.

Adleman is often called the inventor of DNA computers. His article released in 1994 described how to use DNA to solve a well known mathematical problem called the directed Hamiltonian Path problem. The goal of the problem is to find the shortest route between a numbers of cities, going through each city only once. As we add more cities, the problem becomes more difficult. Adleman chose to find the shortest route between seven cities. The Hamiltonian Path problem is difficult for conventional computers to solve because it is a non-deterministic polynomial time problem. NP problems are intractable with deterministic [serial] computers, but can be solved using non-deterministic [massively parallel] computers. A DNA computer is a type of non-deterministic computer. This problem was chosen because it is known as NP complete. Every NP problem can be reduced to a Hamiltonian Path problem.

The steps taken in the Adleman’s DNA computer experiment are:

i. Strands of DNA represent the seven cities. Some sequence of four bases A, T, G, C represented each city and possible flight path.

ii. These molecules are then mixed in a test tube with some of the DNA strands sticking together. A chain of these strands represents a possible path.

iii. Within a few seconds, all of the possible combinations of DNA strands which are possible answers are created in the test tube.

Adleman eliminates the wrong molecules through chemical reactions which leaves behind only the flight paths that connect all seven cities.

Adleman’s Algorithm

Step 1 : Generate random path through the graph.

Step 2 : Keep only those paths, which begin with V_in and end

with V_out.

Step 3 : If the graph has n vertices then keep only those

paths, which enter exactly n vertices.

Step 4 : Keep only those paths, which enter all of the vertices

in the graph at least once.

Step 5 : If any path remain say ‘yes’ otherwise say ‘no’.