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’.

DNA Computing

DNA computing is a novel technology that seeks to capitalize on the enormous capacity of DNA, biological molecules that can store huge amounts of information and are able to perform operations similar to that of a computer, through the deployment of enzymes, biological catalysts that act like software to execute desired operations. DNA computing brings greater optimization 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. For serial logic, DNA computers are not a viable option. However for parallel logic, a DNA computer can perform 10¹⁴ million instructions per second. It also requires less energy and space. The computing power of a teardrop sized DNA computer will be more powerful than the world’s most powerful super computer. 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 DNA 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.

DNA based logic gates & biochip

DNA computers will work through the use of DNA based logic gates. These logic gates are very much similar to what is used in our computers today with the only difference being the composition of input and output signals. In the current technology of logic gates, binary codes from the silicon transistors are converted into instructions that can be carried out by the computer. DNA computers on the other hand, use DNA codes in place of electrical signals as input to DNA logic gates. They detect fragments of genetic material as input, splice together these fragments and form a single output. For instance, a genetic gate called ‘AND gate’ links two DNA inputs by chemically binding them so that they are locked in an end-to-end structure.

The ability to build a biochip lies first and foremost in the ability to merge the biological parts with the electronics into hybrid systems. MEMS- Micro Electro Mechanical System is the practice of combining miniaturized mechanical and electronic components. Any successful biochip can be built by combining the latest electronic technologies. Successful MEMS technology will be the key to building biochips. One advantage of biochip is that its manufacture does not produce any toxic by-products.

A successor to silicon

Silicon microprocessors have been the heart of the computing world for more than forty years. In that time, manufacturers have crammed more and more electronic devices onto their microprocessors. In accordance with the Moore’s Law, the number of electronic devices put on microprocessor has doubled every 18 months. Moore’s Law is named after Intel founder Gordon Moore, who predicted in 1965 that microprocessors would double in complexity every two years. Many have predicted that Moore’s Law will soon reach its end, because of the physical speed and miniaturization limitations of silicon microprocessors. The current silicon technology has the following limitations:

· Circuit integration dimensions

· Clock frequency

· Power consumption

· Heat dissipation

DNA computers have the potential to take computing to new levels. There are several advantages of using DNA instead of silicon.

v As long as there are cellular organisms, there will always be a supply of DNA.

v The large supply of DNA makes it a cheap resource.

v Unlike toxic materials used to make traditional microprocessors, DNA biochips can be made cleanly.

v One pound of DNA has the capacity to store more information than all electronic computers ever built.

v It has the ability to perform many calculations simultaneously.

v Use of DNA will make the DNA computers many times smaller than today’s computer.

DNA

The complete set of instructions for making an organism is called its genome. It contains the master blueprint for all cellular structures and activities for the lifetime of the cell or organism. The genome consists of tightly coiled threads of Deoxyribo Nucleic Acid [DNA] and associated protein molecules, organized into structures called chromosomes. If unwound and tied together, the strands of DNA will stretch more than 5feet and will be only 50 trillionths of an inch wide. For each living organism, the components of these slender threads encode all the information necessary for building and maintaining life. DNA molecule consists of two strands that wrap around each other giving a double-helical structure made of sugar and phosphate molecules and is connected by rings of nitrogen containing chemicals called bases. Each strand is a linear arrangement of repeating similar units called nucleotides. A nucleotide is composed of one sugar [five carbon], one phosphate and a nitrogenous base. The two strands of a DNA molecule are anti-parallel and they are held together by weak hydrogen bonds between the bases.

Four different bases are present in DNA. They are Adenine [A], Cytosine[C], Guanine [G] and Thymine [T]. The particular order of the bases arranged along the sugar-phosphate backbone is called DNA sequence. Each DNA strand has two different ends that determine its polarity: the 3’end and 5’end. The chemical structure of DNA consists of a particular bond of two linear sequences of bases. Strict base pairing rules are adhered to. Adenine will only combine with thymine and cytosine always pairs with guanine. This is called complementarity of the DNA. It is also known as Watson-Crick complementarity. Thus if two complementary single stranded DNA molecules come together they bind to form double helical structure.

For example, if one strand of DNA is of the sequence

AGTACT

The other strand must be of the sequence

TCATGA

Polymerase and ligase are the two enzymes that are vital for DNA replication and sticking together of DNA molecules when they come into close proximity in a linear fashion.