05-04-2012, 01:08 PM
DNA COMPUTING
DNA COMPUTINg.doc (Size: 2.21 MB / Downloads: 53)
INTRODUCTION:
DNA computing or molecular
computing can be defined as the use of
biological molecules, primarily DNA (or
RNA), to solve computational problems
that are adapted to this new biological
format. DNA-based computing is at the
intersection of several threads of research. The information-bearing capability of DNA molecules is a cornerstone of modern theories of genetics and molecular biology. The information in a DNA molecule is contained in the sequence of nucleotide
bases, which hydrogen bond in a complementary fashion to form double -
stranded molecules from single-stranded
oligonucleotide.
DNA has enormous storage capacity much larger than silicon
computers for instance, 1 gram of DNA
can hold about 1x1014 MB of data. DNA computing is fundamentally similar to parallel computing in that it takes advantage of the many different molecules of DNA to try many different
possibilities at once. For certain specialized problems, DNA computers are faster and smaller than any other computer built so far. But DNA computing does not provide any new capabilities from the standpoint of computational complexity theory, the study of which computational problems are difficult to solve. Chips which use DNA for computation are called BIOCHIPS.
HISTORY:
Various aspects of life inspired early results in computer science in the 1950's (J. von Neumann's universal constructor and Computer. A second development occurred in the early 1970's with J.Holland's computational implementation of fundamental biological mechanisms, such as genetic
operations (splicing, recombination and
mutation)and evolution. Finally, a third
stage inaugurated by L. Adleman's 1994
proof of concept that recombinant properties of real DNA can actually use
massive parallelism to solve problems appropriately encoded into single DNA strands. In 1994, Leonard Adleman introduced the idea of using DNA to solve complex mathematical problems.
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, who codiscovered the structure of DNA in 1953. In fact, DNA is very similar to a
computer hard drive in how it stores permanent information about your genes. Adleman is often called the inventor of DNA computers. His article
in a 1994 issue of the journal Science outlined how to use DNA to solve a well-known mathematical problem, called the directed Hamilton Path problem, also known as the "traveling salesman" problem. The goal of the problem is to find the shortest route between a number of cities, going through each city only once. As you add
more cities to the problem, the problem
becomes more difficult.
Adleman chose to find the shortest route between seven cities. You could probably draw this problem out on paper and come to a solution faster than Adleman did using his DNA test-tube computer. Here are the steps taken in the
Adleman DNA computer experiment:
1) Strands of DNA represent the seven
cities. In genes, genetic coding is represented by the letters A, T, C and G.
Some sequence of these four letters represented each city and possible flight
path.
2) These molecules are then mixed in a
test tube, with some of these DNA strands sticking together. A chain of these strands represents a possible answer.
3) Within a few seconds, all of the possible combinations of DNA strands, which represent 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.
The success of the Adleman DNA computer proves that DNA can be used to calculate complex mathematical problems. However, this early DNAomputer is far from challenging siliconbased computers in terms of speed. The Adleman DNA computer created a group of possible answers very quickly, but it took days for Adleman to narrow down the possibilities. Another
drawback of his DNA computer is that it
requires human assistance. The goal of
the DNA computing field is to create a
device that can work independent of human involvement. Three years after Adleman's experiment, researchers at the
University of Rochester developed logic
gates made of DNA. Logic gates are a
vital part of how your computer carries
out functions that you command it to do.
These gates convert binary code moving
through the computer into a series of signals that the computer uses to perform
operations.
Currently, logic gates interpret input signals from silicon transistors, and convert those signals into an output signal that allows the computer to perform complex functions. The Rochester team's DNA logic gates are the first step toward creating a computer that has a structure similar to that of an electronic PC. Instead of using electrical signals to perform logical operations, these DNA logic gates rely on DNA code. They detect fragments of genetic material as input, splice together these fragments and form a single output.
STEPS IN DNA COMPUTING:
A DNA computation was classifed into
five simple operations that could be done
on a test tube of DNA:
1. Synthesis of a large numbers of
oligonucleotides.
2. Annealing (i. e., hybridization) of
oligonucleotides to produce doublestranded DNA molecules.
3. Extraction of molecules containing a
given sequence of bases.
4. Detection of any molecules in the
tube.
5. Amplification of all the DNA in the
tube.
ALGORITHM
1. Generate Random paths
2. From all paths created in step 1, keep
only those that start at s and end at t.
3. From all remaining paths, keep only
those that visit exactly n vertices.
4. From all remaining paths, keep only
those that visit each vertex at least once.
5.If any path remains, return “yes”;
otherwise, return “no”.
ADVANTAGES:
Silicon microprocessors have been the heart of the computing world for more than 40 years. In that time, manufacturers have crammed more and
more electronic devices onto their microprocessors. In accordance with Moore's Law, the number of electronic
devices put on a 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.
( silicon microprocessors)
DNA computers have the potential to take computing to new levels, picking up where Moore's Law leaves off. There are
several advantages to using DNA instead
of silicon:
• As long as there are cellular organisms, there will always be a supply of DNA.
• The large supply of DNA makes it a cheap resource.
• Unlike the toxic materials used to make traditional microprocessors, DNA biochips can be made cleanly.
• DNA computers are many times smaller than today's computers.
MINIATURIZATION:
DNA's key advantage is that it will make computers smaller than any computer that has come before them, while at the same time holding more data. One pound of DNA has the capacity to store more information than all the electronic computers ever built; and the computing power of a teardropsized DNA computer, using the DNA logic gates, will be more powerful than the world's most powerful supercomputer.
More than 10 trillion DNA molecules can fit into an area no larger than 1 cubic centimeter (0.06 cubic inches). With this small amount of DNA, a computer would be able to hold 10 terabytes of data, and perform 10 trillion calculations at a time.
By adding more DNA, more calculations could be performed. Unlike conventional computers, DNA computers perform calculations parallel to other calculations. Conventional computers operate linearly, taking on tasks one at a time. It is parallel computing that allows DNA to solve complex mathematical problems in hours, whereas it might take electrical computers hundreds of years to complete them. he first DNA computers are unlikely to feature word processing, mailing and solitaire programs. Instead,
their powerful computing power will be
used by national governments for cracking secret codes, or by airlines
wanting to map more efficient routes.
UNIQUE STRUCTURE OF DNA
The amount of information gathered on the molecular biology of DNA over the last 40 years is almost overwhelming in scope. So instead of getting bogged down in biochemical and biological details of DNA, we'll concentrate on only the information relevant to DNA computing. The data density of DNA is impressive. Just like a string of binary data is encoded with ones and zeros, a strand of DNA is encoded with four bases, represented by the letters A, T, C, and G. The bases (also known as nucleotides) are spaced every 0.35 nanometers along the DNA molecule, giving DNA an remarkable data density of nearly 18 Mbits per inch. In two dimensions, if you assume one base per square nanometer, the data density is over one million Gbits per square inch. Compare this to the data density of a typical high performance hard drive, which is about 7 Gbits per square inch -- a factor of over 100,000 smaller. Another important property of DNA is
its double stranded nature. The bases A
and T, and C and G, can bind together,
forming base pairs. Therefore every DNA sequence has a natural complement. For example if sequence S
is ATTACGTCG, its complement, S', is
TAATGCAGC. Both S and S' will come
together (or hybridize) to form double stranded DNA. This complementarity makes DNA a unique data structure for
computation and can be exploited in many ways. Error correction is one example. Errors in DNA happen due to
many factors.
DNA can also be damaged by thermal energy and UV energy from the sun. If the error occurs in one of the strands of double stranded DNA, repair enzymes can restore the proper DNA sequence by using the complement strand as a reference. In this sense, double stranded DNA is similar to a RAID 1 array, where data is mirrored on two drives, allowing data to be recovered from the second drive if errors occur on the first. In biological systems, this facility for error correction means that the error rate can be quite low. For example, in DNA replication, there is one error for every 10^9 copied bases or in other words an error rate of 10^-9. (In comparison, hard drives have read error rates of only 10^-13 for Reed-Solomon correction).
Parallel Operation:
In the cell, DNA is modified biochemically by a variety of enzymes,
which are tiny protein machines that read and process DNA according to nature's design. There is a wide variety
and number of these "operational" proteins, which manipulate DNA on the
molecular level. For example, there are enzymes that cut DNA and enzymes that
paste it back together. Other enzymes function as copiers, and others as repair
units. Molecular biology, Biochemistry,
and Biotechnology have developed techniques that allow us to perform many of these cellular functions in the test tube. It's this cellular machinery, along with some synthetic chemistry, that makes up the palette of operations
available for computation. Just like a CPU has a basic suite of operations like addition, bit-shifting, logical operators (AND, OR, NOT NOR), etc. that allow it to perform even the most complex calculations, DNA has cutting, copying, pasting, repairing, and many others. And note that in the test tube, enzymes do not function sequentially, working on one DNA at a time. Rather, many copies of the enzyme can work on many DNA molecules simultaneously. This is the power of DNA computing, that it can work in a massively parallel fashion.