paper-8

DNA means deoxyribonucleic acid. DNA computing, in the literal sense, is the use of DNA molecules, the molecules which encode genetic information for all living things, in computers. A DNA computing is basically a collection of specially selected DNA strands that combinations will result in the solution to some problem. Instead of using figures and formulae to solve a problem, that microscopic computer's input, output and software are made up of DNA molecules. DNA computers will be capable of storing billions of times more data DNA computers will be capable of storing billions of times more data. Since the DNA molecule is also a code, but instead made up of a sequence of four bases which pair up in a predictable manner, scientists believe in the possibility for using it as a molecular computer.

Although too simple to have any immediate applications, it could form the basis of a DNA computer in the future that could potentially operate with in human cells and act as a monitoring device to detect disease-causing changes. The DNA computer which is a molecular model of one of the simplest computing machines -- the automation which can answer certain yes or no questions.





DNA COMPUTING INTRODUCTION

DNA (deoxyribonucleic acid) computing is a very young branch of science that started less than a decade ago, when Leonard Adleman of the University of Southern California pioneered the field by using DNA in a test tube to solve a mathematical problem. Scientists around the globe are now trying to marry computer technology and biology by using nature's own design to process information.
DNA computing, in the literal sense, is the use of DNA (Deoxyribose Nucleic Acid) molecules, the molecules which encode genetic information for all living things, in computers. This is accomplished in a suspended solution of DNA, where certain combinations of DNA molecules are interpreted as a particular result to a problem encoded in the original molecules present.

ABSTRACT
DNA structure
A DNA computing is basically a collection of specially selected DNA strands that combinations will result in the solution to some problem. Technology is currently available both to select the initial strands and to filter the final solution. The promise of DNA computing is massive parallelism: with a given setup and enough DNA, one can potentially solve huge problems by parallel search. This can be much faster than a conventional computer, for which massive parallelism would require large amount of hardware, not simply more DNA.
Instead of using figures and formulae to solve a problem, that microscopic computer's input, output and software are made up of DNA molecules. A nanoscale computer made of bio-molecules that are so small that you can't run them one at a time. When a trillion computers run together they can perform a billion operations.
DNA computers will be capable of storing billions of times more data (say, at a density of 1 bit per cubic nanometer -- a trillion times less space) than your personal computer. Scientists are using genetic material to create nano-computers that might take the place of silicon-based computers in the next decade. The double heliex molecule that contains human genes stores data on four chemical bases -- known by the letters A,T,C and G -- giving it massive memory capability that scientists are only just beginning to tap into.


The living cells contain incredible molecular machines that manipulate information-encoding molecules such as DNA and RNA (its chemical cousin) in ways that are fundamentally very similar to computation. Data is represented by pairs of molecules on a strand of DNA and two naturally occurring enzymes act as the hardware to read copy and manipulate the code. When it is all mixed together in the test tube, the software and hardware operate on the input molecule to create the output.

BINARY CODE Vs DNA CODE

All computers is use today make use of binary code -1's and 0's, or one’s and offs on the circuits of a computer chip, forming the basis for every calculation a computer performs, from simple addition to the solution of the most complex differential equations. Since the DNA molecule is also a code, but instead made up of a sequence of four bases which pair up in a predictable manner, scientists believe in the possibility for using it as a molecular computer. However, rather than relying on the position of electronic switches on a microchip, much faster reactions of DNA nucleotides binding with their complements, a brute force method that would indeed work.





WORKING OF DNA COMPUTERS

Computer chip manufactures are racing to make the next microprocessor that will topple speed records. This competition is bound to hit a wall. Microprocessors made of silicon will eventually reach their limits of speed and miniaturization. Chip makes need a new material to produce faster computing speeds.
The new material that has been found to build the next generation of microprocessors is DNA molecules. Millions of natural supercomputers exist inside living organisms, including your body. DNA molecules, the material our genes are made of, have the potential to perform calculations many times faster than the world's most powerful human-build computers. DNA might one day be integrated into a computer chip to create a so-called biochip that wills puts computers even faster. DNA molecules have already been harnessed to perform complex mathematical problems.
Logic gates play a vital role 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 user to perform operations. These gates interpret input signals from silicon transistors, and convert those signals into a out signal that allows the computer to perform complex functions.
The DNA logic gates are the fist step toward creating a computer that has a structure similar to that of an electronic PC. Instead of using electrical signals of 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. For instance, a genetic gate called the "And gate" links two DNA inputs by chemically binding them so they're locked in an end-to end structure similar to the way two Legos might be fastened by a third Lego between them. The researchers believe that these logic gates might be combined with DNA microchips to create a breakthrough in DNA computing.

COMPONENTS

DNA computer components -- logic gates and biochips -- will take years to develop into practical, workable DNA computers. If such a computer is ever building, scientists say tat it will be more compacting, accurate and efficient than conventional computers.
As computer chips get faster and smaller, we are quickly approaching their physical speed limits. But researchers recently previewed a whole new era of advanced computing-- and the key is using molecules themselves. With strands of synthetic DNA they were able to create a crude molecular computer "chip” made of small glass plate covered with a thin layer of gold. Strands of DNA were coded represent solutions to a computational problem with 16 possible answers. Enzymes were then applied to the gold slide to strp out the entire DNA with incorrect answers, thus solving the calculation.

ADVANTAGES
First and foremost, DNA computing is useful because it has a capacity lacked by all current electronics-based computers: its massively parallel nature. Essentially while DNA can only carry out computations slowly, DNA computers can perform a staggering number of calculations simultaneously; specifically, on the order of 10^9 calculations per mL of DNA per second! This capability of multiple co temporal calculations immediately lends itself to several classes of problems which a modern electronic computer could never even approach solving. To give you an idea of the difference in time, a calculation that would take 10^22 modern computers working in parallel to complete in the span of one human's life would take one DNA computer only 1 year to polish 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
• DNA computers will be capable of storing billions of times more data (say, at a density of 1 bit per cubic nanometer -- a trillion times less space) than your personal computer.
• The DNA computer has very low energy consumption, so if it is put inside the cell it would not require much energy to work.
• Using DNA logic gates the DNA computers will be more powerful than the world's most powerful supercomputer.
• DNA computers perform calculations parallel to other calculations



APPLICATIONS

Although too simple to have any immediate applications, it could form the basis of a DNA computer in the future that could potentially operate with in human cells and act as a monitoring device to detect disease-causing changes. The model could also form the basis of computer that could be used to screen DNA libraries in parallel without sequencing each module.
The DNA computer which is a molecular model of one of the simplest computing machines -- the automation which can answer certain yes or no questions. As the technology is still in development phase the application level of these DNA computers are still made to solve complex mathematical problems. One of the problems which the DNA computer made to solve is 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 more number of cities increases the problem becomes more difficult. Adelman the inventor of DNA computer chose to find the shortest route between seven cities.
As the traditional computer has to crunch through all possibilities one at a time the DNA computer using the deoxyribonucleic acid ploughs through all the combinations more or less simultaneously. The trick lies in creating the right set of DNA strands to start the process, and then weeding out the wrong answers. The success proves that DNA can be used to calculate complex mathematical problems. It is parallel computing that allows DNA to solve the complex mathematical problems. However this is far from challenging silicon-based computers in terms of speed. The goal of DNA computing field is to create a device that can work independent of human involvement.
The future applications of DNA computers are more likely to center around cracking secret codes and mapping airline routes than running word processing programmers and sending e-mail.
IMPLEMENTATION OF GENETIC ALGORITHM USING
DNA

Software for representing Architecture of genes in DNA: Waltz algorithm is used to represent DNA architecture, Decoding DNA structure to strings of bits and for encoding the result in bits to DNA structures.
Some high level language like C and C++ can be used to manipulate gene code and fitness of offspring is calculated using Fitness function. These High Level Language use Heuristic search Techniques for generating fitness function.

C++ code for Genetic Algorithm


Conclusion

Currently, molecular computing is a field with a great deal of potential, but few results of practical value. In the wake of Adleman's solution of the Hamiltonian path problem, there came a host of other articles on computation with DNA; however, most of them were purely theoretical. While it currently exists only in theory, it's possible that in the years to come computers based on the work of Adleman, Lipton, and others will come to replace traditional silicon-based machines.
However, as work continues in this exciting area, molecular computers may impress us once again and challenge the dominance of electronic systems in solving even more types of problems. After all, the DNA based system of computation has had millions of years to evolve and perfect itself, while man-made systems have only existed for a small fraction of this span. It is an impressive computer indeed that can spend eons producing new and varied organisms through trial and error until it finally finds a solution - the intelligent species we call human beings. The computers of tomorrow are on the threshold.

paper-7

INTRODUCTION:-
While looking for alternative technologies to overcome the limitations of modern computing, researchers hit on the use of biological systems that could be imitated by computer systems. This was the genesis of DNA computing, which has brought about a variety of potential applications. From security to nanotechnology , where tiny DNA-based devices are programmed to repair cells in patients suffering from pathological illness.
The past two decades have seen massive progress in the field of information and computing technology. Consequently the applications of computing , and indeed the computer itself , have become a necessary thread in the fabric of our lives. The foundation on which computing is based , namely conventional silicon–based semiconductor technology, has so far been able to sustain the rate of growth predicted by Moore’s Law.
Moore’s Law postulates that the speed of the computing chip will double roughly every eighteen months.
The most progress so far has been the result of fine-tuning testing fabrication capabilities and packing chips with smaller and smaller transistors. But it is a bottleneck in terms of bizarre quantum phenomena at atomic size –scales that have to be achieved to sustain Moore’s predictions. Researches in the field have always concentrate on alternative technologies also.
This quest for new paradigms in computing led to birth of computer systems based on biological systems. This mode of computing is significantly different from using information technology to solve complex biological problems. Rather, it involves the use of biological molecules such as DNA, DNA analogues and RNA to perform the arduous task of computing by employing complex biological process analogues to the underlying computation.
WHAT IS DNA ?
Prior to delving into the principles of DNA computing, it becomes necessary to explore fundamentals of molecular biology. All organisms on this planet are made of same genetic blueprint. Coding of this decides our physical makeup-from colour of our eyes to whether we are human. In human there are trillions of cells and within every nucleus of each cell there are tightly coiled threads of deoxyribonucleic acid (DNA) .
DNA is a double stranded helix of nucleotides that carries the genetic information of a cell. This information is the code used within cells to form proteins and is the building block upon which life is formed. The complete set of instructions for ‘building’ an organism is called the “genome”. It contains the master blueprint for all cellular structures and activities for the lifetime of the cell or organism.
Strands of DNA are long polymers of millions of linked nucleotides .These nucleotides consist of one of four nitrogen bases, a five-carbon sugar and a phosphate group. The nucleotides that make up these polymers are named after nitrogen bases that comprise it, namely ,Adenine(A), Cytosine(C) , Guanine(G) and Thymine(T).These nucleotides only combine in such a way that C always pairs with G, and T always pairs with A . The two strands of DNA molecule are anti-parallel in that each strand runs in an opposite direction.





The particular order of the bases arranged along the sugar-phosphate backbone is called the DNA sequence and the combination of the four nucleotides in the estimated million long polymer strands results in billions of combinations within a single DNA double helix. These massive amounts of combinations allow us to differentiate between every living thing on the plane- from the large scale (mammals) to the small scale (differences in human hair colour).
Each time a cell divides into two daughter cells, its full genome is duplicated. For humans and other complex organisms, this duplication occurs in the nucleus. Strict base-pairing rules are adhered to. Adenine will pair only with thymine(an A-T pair) and cytosine with guanine (a C-G pair).Each daughter cell rules ensure that the new strand is an exact copy of the old one. This the minimises the incidences of errors(mutations) .That may affect the resulting organism or its offspring.


Each DNA molecule contain many genes, the basic physical and functional hereditary units. A gene is a specific sequence of nucleotides bases whose sequences carry the information required for constructing proteins, which provides the structural components of cells and tissues as well as enzymes for essential biochemical reactions. The nucleus of most human cells contains two sets of chromosomes , one set given by each parent. Chromosomes contain roughly equal parts of protein and DNA.
The mystery of DNA and its construction is slowly being unraveled through mathematical means. These biological phenomena involving DNA have given computing researchers the much needed food for thought to apply these concepts to fashion the entirely new field of DNA computing , which finds exciting potential applications from security (encryption-decryption standards )to improving the quality of life by programming tiny DNA-based therapeutic devices to repair cells in patients who may be suffering from debilitating pathological conditions.
DNA‘S GREAT PROMISE-
MASSIVE PARALLELISM AND DATA DENSITY :-
Basically computers can deal with computational work in two ways : through serial computation and parallel computation.
Serial computation means that the computer deals with computational work in sequence , one by one , so to speak and is the process employed by most conventional silicon-based or ‘von Neumann computers’. Parallel computation means that computers deal with a lot of computational tasks simultaneously. Apart from obvious advantages that massively parallel computing provides, DNA has one more important feature that lends to being use it as computing medium. When compared to silicon, which is the material of choice in today’s computers , 1 base of DNA measures 0.35nm , lending it a data density of 18 Mega bits per square inch. This in turn implies that 10^6 Giga bits of information can be stored per square inch. Comparing this with conventional hard drives that have a data density of 7 Giga bits per square inch, we instantly see that DNA has a higher data capacity by a factor of 10^5. So one gram of DNA can hold enough information to completely fill one billion CD’s.
Nature has also protected DNA against errors by the process of ‘exactcopy‘ complementary strands-a process that is analogous to the Redundant Array of Inexpensive Disks(RAID) , which employs two disks to reduce errors in the event that either fails.
Given these two salient points in its favour-parallelism and data density-it is quite natural that researchers in the field of DNA computing have been enjoying a certain degree of optimism.
ORIGINS OF DNA COMPUTING :-
With an appropriate setup and enough DNA we can potentially solve huge problems by parallel search. This means that we can attempt every solution to a given problem until we come across the right one through random calculations. Using DNA for those type of computation can be much faster than using a conventional computer, for which massive parallelism would require large amounts of hardware , not simply more DNA.
Dr Leonard Adleman , professor at the University of southern California is recognized as a father of DNA computing.



In early 1994,Dr Adleman put his theory of DNA computing to the test on a problem called the Hamiltonian Path problem that is popularly called as the ‘Travelling Salesman Problem’. The ‘salesman’ in this problem has a map of several cities that he must visit to sell his wares where these cities have only one-way streets between some but not all of them. The crux of the problem is that the salesman must find a route to travel that passes through each city (A through G) exactly once , with a designated beginning and end.
The salesman wants to make efficient use of his time and does not want to backtrack or double back on a path he has taken previously.
Mathematicians call this type of problem a non-deterministic polynomial time problem (NP). The idea of guessing the right answer to a problem, or checking all possible problems in parallel to determine which is correct, is called non-determinism. An algorithm that works in this manner is called a non-deterministic algorithm and any problem with such an algorithm that runs on a non0deterministic machine in polynomial time is called a non-deterministic polynomial time problem.
The NP problem was chosen for Dr Adleman’s DNA computing test, as it is a type problem that is difficult for conventional computers to solve. The parallel computing of a DNA combination suited for NP problem solving.
Dr Adleman, using a basic seven-city 13-street model for the Travelling Salesman Problem, created randomly-sequenced DNA strands 20 bases long to chemically represent each city’s strand halfway to represent each street.



Adleman’s DNA computing representation of the ‘Travelling Salesman problem’.
By placing a few grams of every DNA city and street in a testtube and allowing the natural bonding tendenccies of the DNA building blocks to occur ,the DNA bonding created over 10^6 answers answers in less than one second. Ofcourse not all of the answers that came in one second were the correct answers as Dr Adleman only needed to keep those paths that exhibited the following properties:
•The path must starts at city A and end at city G.
•Of those paths ,the correct paths must pass through all seven
cities at least once.
• The final Path(s) must contain each city in turn.
The correct answer was determined by filtering the strands of DNA according to their end-bases to determine which strands began from city A and ended with city G and discarding those that did not..

ADVANTANGES OF DNA COMPUTING :-
Speed :
Combining DNA strands as demonstrated by Dr Adleman, made computations equivalent to 10^9 or better,arguably over 100 times faster than fastest computer.
Minimal storage requirements :
DNA stores memory at a density of about one bit per cubic nanometer where conventional storage media requires 10^12 cubic nanometers to storage one bit.
Minimal power requirements :
No power is required for DNA computing while computation is taking place. The chemical bonds that are the building blocks of DNA happen without any outside power source.
DNA APPLICATIONS
DNA plays a key role in following security applications.

DNA Cryptography
Scientists of Duke University published a paper entitled ‘DNA-based Cryptography’a which argues that the high-level computational ability and incredibly compact information storage media of DNA computing has the possibility of DNA-based cryptography based on the one-time pads , limited to the confines of conventional electronic media , whereas small amounts of DNA can suffice for a huge one-time pad for use in public key infrastructure(PKI).

DNA Steganography:
Steganography is a variety of encryption that completely hides text or graphics usually unencrypted ,within other text or graphics that are electronically transmitted.
The term “steganography” derives from the Greek words steganos (hidden) and graphein (to write).
This method uses a simple code to convert the letters of alphabet into combinations of the four bases that make up DNA and create a strand of DNA based on that code. A piece of DNA spelling out the message to be hiddden is syntetically created which contains the secret encrypted message in the middle plus short marker sequences at the ends of the message. The encoded piece of DNA is then placed into a normal piece of human DNA, which is then mixed with DNA strands of similar length. The mixture is then dried onto a paper that can be cut up into microdots ,with each dot containing billions of strands of DNA. Not only is the microdot difficult to detect on the plain message medium but also only one strand of those billions within the microdot contains the message.
But the problems with DNA cryptography are evident in DNA steganography as well as. The ‘test tube’ environment used in this type of steganography is far from practical for everyday use.





DNA Limitations :-
Volume Complexity :
Dr Adleman speculated the more useful instances of the Hamiltonian path could be solved in linear time with a manageable volume of solution. Later conclude that , due to exponential growth of the number of paths with an increase in the number of vertices , the required mass of the solution for a graph with 200 vertices would exceed 3*10^25 kg! While other algorithms may be more efficient in terms of volume complexity.
Data representation :
One of the related problems with DNA computing is that there is no universal method of data representation. In today’s computer systems binary representation is universally agreed. DNA computing has no such standard because it does not have an operation to extract a strand if it has a particular value at a particular position.
No efficient Implementation :
One of the biggest problem facing the field of DNA computing is that no efficient implementation has been produced for testing, verification, and general explanation. The reason for this is that the resources required to execute these algorithms are both expensive and hard to find. DNA computing has a high incremental cost both in time of the operators and the raw materials that it uses.
Despite these difficulties, there still a number of researchers working on topics related to DNA computing.

Future of DNA computing :-
In spite of all these limitations ,we believe that DNA computing still has an important role to play and recent advances in the field of biomedical nanotechnology and the human genome project will provide an impetus to DNA computing researchers who seek to gain a better understanding of certain pathological conditions that currently afflict the human race.

paper-6

ABSTRACT
DNA Computers have the potential to perform calculations many times faster than the world's most powerful human-built computers. DNA computers will be capable of storing billions of times more data than your personal computer. DNA computing is currently one of the fastest growing fields in both Computer Science and Biology, and its future looks extremely promising. DNA computing is the use of DNA molecules, which encode genetic information for all living things, in computers. A functional DNA "computer" of the type most people are familiar with lies many years in the future. DNA computing is useful because it has a capacity lacked by all current electronics-based computers: its massively parallel nature. DNA computers can perform a staggering number of calculations simultaneously; specifically, on the order of 10^9 calculations per mL of DNA per second! Today we have not one but several companies making "DNA chips," where DNA strands are attached to a silicon substrate in large arrays (for example Affymetrix's genechip).






CONTENTS
• Introduction ………………………………………….1
• DNA Computation …………………………………..1
• History of DNA Computing ………………………….2
• DNA: A unique data structure ………………………..4
• DNA vs. Silicon …………………………………… ..5
• DNA Computers Solves A Complex Problem ………..5
• Test tube holds a trillion computers ………………….6
• The Future of DNA Computing ………………………7
• Advantages and Disadvantages ………………………8
• Conclusions ……………………………………………9
• Bibliography








INTRODUCTION
Computer chip manufacturers are furiously racing to make the next microprocessor that will topple speed records. Microprocessors made of silicon will eventually reach their limits of speed and miniaturization. Chipmakers need a new material to produce faster computing speeds. You won't believe where scientists have found the new material they need to build the next generation of microprocessors. DNA (deoxyribonucleic acid) molecules, the material our genes are made of, have the potential to perform calculations many times faster than the world's most powerful human-built computers. DNA might one day be integrated into a computer chip to create a so-called biochip that will push computers even faster. DNA molecules have already been harnessed to perform complex mathematical problems. DNA computers will be capable of storing billions of times more data than your personal computer.
DNA Computation
DNA computing, in the literal sense, is the use of DNA (Deoxyribose Nucleic Acid) molecules, the molecules that encode genetic information for all living things, in computers. This is accomplished in a suspended solution of DNA, where certain combinations of DNA molecules are interpreted as a particular result to a problem encoded in the original molecules present. DNA computing is currently one of the fastest growing fields in both Computer Science and Biology, and its future looks extremely promising. A highly interdisciplinary study incorporating the research results of computer scientists and biologists. In the literal sense, DNA computing is the use of DNA molecules, which encode genetic information for all living things, in computers. It is accomplished in a suspended solution of DNA, where certain combinations of DNA molecules are interpreted as a particular result to a problem encoded in the original molecules present. Dr. Leonard Aldeman is a pioneer of DNA computing for his solution to solve Hamiltonian Path Problem using DNA strands.

Inventor of DNA Computer
History of DNA Computing
In 1994, Leonard M. Adleman solved an unremarkable computational problem with a remarkable technique. It was a problem that a person could solve it in a few moments or an average desktop machine could solve in the blink of an eye. It took Adleman, however, seven days to find a solution. Why then was this work exceptional? Because he solved the problem with DNA.

DNA is a natural carrier of information
The type of problem that Adleman solved is a famous one. It's formally known as a Directed Hamiltonian Path problem, but is more popularly recognized as a variant of the so-called "Traveling salesman problem". In Adleman's version of the traveling salesman problem, a hypothetical salesman tries to find a route through a set of cities so that he visits each city only once. As the number of cities increases, the problem becomes more difficult until its solution is beyond analytical analysis altogether, at which point it requires brute force search methods. TSPs with a large number of cities quickly become computationally expensive, making them impractical to solve on even the latest super-computer. Nevertheless, his work is significant for a number of reasons.
• It illustrates the possibilities of using DNA to solve a class of problems that is difficult or impossible to solve using traditional computing methods.
• It's an example of computation at a molecular level, potentially a size limit that may never be reached by the semiconductor industry.
• It demonstrates unique aspects of DNA as a data structure
• It demonstrates that computing with DNA can work in a massively parallel fashion.
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 use 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. DNA computer components -- logic gates and biochips -- will take years to develop into a practical, workable DNA computer. If such a computer is ever built, scientists say that it will be more compact, accurate and efficient than conventional computers.
DNA: A unique data structure
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& G. It is also known as nucleotides, they are spaced every 0.35 nm along the DNA molecule, giving DNA a remarkable data density of nearly 18 Mbits/inch. In two dimensions, if you assume one base per square nanometer, the data density is over one million Gbits/sq inch. Compare this to the data density of a typical high performance hard drive, which is about 7 Gbits/sq inch -- a factor of over 100,000 smaller. Another important property of DNA is its double stranded nature. The bases A & T, and C & 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 to form double stranded DNA. This complementarity’s makes DNA a unique data structure for computation and can be exploited in many ways. Occasionally, DNA enzymes simply make mistakes, cutting where they shouldn't, or inserting a T for a G. DNA can also be damaged by thermal energy and UV energy from the sun.
DNA vs. Silicon
DNA, with its unique data structure and ability to perform many parallel operations, allows you to look at a computational problem from a different point of view. Of course there are multi-processor computers, and modern CPUs incorporate some parallel processing, but in general, in the basic von Neumann architecture computer, instructions are handled sequentially. A von Neumann machine, which is what all modern CPUs are, basically repeats the same "fetch and execute cycle" over and over again; it fetches an instruction and the appropriate data from main memory, and it executes the instruction. It does this many, many times in a row, really, really fast. Typically, increasing performance of silicon computing means faster clock cycles (and larger data paths), where the emphasis is on the speed of the CPU and not on the size of the memory.
DNA Computers Solves A Complex Problem
A DNA-based computer has solved a logic problem that no person could complete by hand, setting a new milestone for this infant technology that could someday surpass the electronic digital computer in certain areas. USC computer science professor Dr. Leonard Adleman carried out this experiment. His experiment proved that computing with molecules was possible. But the problem solved -- to find the shortest route among seven cities -- could easily have been solved by a person with a pencil and paper.Researchers think computers made from DNA would be well suited to tackle problems that are time-consuming for conventional computers. Sequences of DNA can be crafted to represent specific patterns of information, and chemical reactions manipulate the DNA -- much as mathematical computations operate on information stored in today's computers. One such problem is depicted above: An airline serves six cities, but not all of the cities have nonstop service with each other. What is the largest group of cities that all have nonstop service with one another? The answer is four (cities 2, 3, 4,& 5).

Test tube holds a trillion computers
Researchers at the Weizmann Institute in Israel have developed a computer so small that a trillion of its kind fit into a test tube.The nanocomputer consists of DNA and DNA-processing enzymes, both dissolved in a liquid.The inventors believe it could ultimately lead to a device capable of processing DNA inside the human body, finding abnormalities and creating healing drugs. In the medium term, it could be turned into a tool capable of speeding up the currently labour intensive job of DNA sequencing. Professor Ehud Shapiro, head of the Weizmann team, says the DNA computer is an automaton, completing its work without human intervention at each stage of processing. Today it is limited to processing DNA, which is synthetically designed. In the future it could process any DNA molecules. The machine's input, output and software program are all DNA molecules.



Previous efforts
DNA computing took a leap forwards in 1994 when Leonard Adleman of the University of Southern California used DNA. It stores a massive amount of data in a small space. Its effective density is roughly 100,000 times greater than modern hard disks. And while a desktop PC concentrates on doing one task at a time very quickly, billions of DNA molecules in a jar will attack the same problem billions of times over. Their goal was not to harness the power of biological computing to solve weighty mathematical problems, but to build a nanoscale computer, which takes naturally occurring information-bearing biological molecules such as DNA as an input. Their success in creating a nanomachine that works on synthetically produced short DNA strands is a huge step towards this goal.
The Future of DNA Computing
Currently, molecular computing is a field with a great deal of potential, but few results of practical value. In the wake of Adleman's solution of the Hamiltonian path problem, there came a host of other articles on computation with DNA; however, most of them were purely theoretical. Currently, a functional DNA "computer" of the type most people are familiar with lies many years in the future. But work continues: in his article Speeding Up Computation via Molecular Biology Lipton shows how DNA can be used to construct a Turing machine, a universal computer capable of performing any calculation. While it currently exists only in theory, it's possible that in the years to come computers based on the work of Adleman, Lipton, and others will come to replace traditional silicon-based machines.

ADVANTAGES AND DISADVANTAGES
DNA computing is useful because it has a capacity lacked by all current electronics-based computers: its massively parallel nature. DNA computers can perform a staggering number of calculations simultaneously; specifically, on the order of 10^9 calculations per mL of DNA per second! This capability of multiple cotemporal calculations immediately lends itself to several classes of problems which a modern electronic computer could never even approach solving.
DNA computers do have their disadvantages. To make these computers more realistically viable, the DNA splicing and selection equipment needs to be refined for this purpose and better methods for fishing developed. There is also no guarantee that the solution produced will necessarily be the absolute best solution, though it will certainly be a very good one, arrived at in a much shorter time than with a conventional computer. DNA computers could not (at this point) replace traditional computers. Some think that in the future, computers will be a combination of the current models and DNA, using the most attractive features of both to create a vastly improved total product. And of course we are talking about DNA here, the genetic code of life itself. Considering all the attention that DNA has garnered, it isn’t too hard to imagine that one day we might have the tools and talent to produce a small-integrated desktop machine that uses DNA, or a DNA-like biopolymer, as a computing substrate along with set of designer enzymes.



CONCLUSION
This first demonstration of DNA computing used a rather unsophisticated algorithm, but as the formalism of DNA computing becomes refined, new algorithms perhaps will one day allow DNA to overtake conventional computation and set a new record. On the side of the "hardware", improvements in biotechnology are happening at a rate similar to the advances made in the semiconductor industry. Just look at the number of advances in DNA-related technology that happened in the last five years. Today we have not one but several companies making "DNA chips," where DNA strands are attached to a silicon substrate in large arrays (for example Affymetrix's genechip). Production technology of MEMS is advancing rapidly, allowing for novel integrated small-scale DNA processing devices. The Human Genome Project is producing rapid innovations in sequencing technology. The future of DNA manipulation is speed, automation, and miniaturization.
And of course we are talking about DNA here, the genetic code of life itself. It certainly has been the molecule of this century and most likely the next one. Considering all the attention that DNA has garnered, it isn’t too hard to imagine that one day we might have the tools and talent to produce a small-integrated desktop machine that uses DNA, or a DNA-like biopolymer, as a computing substrate along with set of designer enzymes. Perhaps it won’t be used to play Quake IV or surf the web -- things that traditional computers are good.

paper-5

DNA COMPUTING
“THE BASE FOR FUTURE’S FASTEST COMPUTERS”


ABSTRACT:


In this paper we intend to present the computing technology that has a great future-DNA COMPUTING. The paper begins with an introduction to DNA COMPUTING and its origin.A brief description of DNA has been given. Adleman experiment has been discussed, which gives solution to the “ HAMILTONIAN PROBLEM” by the application of DNA COMPUTING. The salient features of DNA Computer (one that uses dna computing as its basic method of problem solving) have been mentioned. An insight into the advantages, disadvantages, applications and limitations of dna-computing has been made. Finally, the paper discusses the hurdles in its path of development at present , to make it feasible and realistic in the near future.

INTRODUCTION TO DNA-COMPUTING
DNA COMPUTING is a method for solving complex problems .In this method the input as well as the output are in the form of dna. This is possible because of the physical structure of dna. The entire computation takes place in the form of a bio-chemical reaction. Different methods can be applied in order to extract the correct solution to the problem. This needs to be done because the basic manner in which the computing is performed is a bio-chemical reaction. Both the right as well as the wrong answers are obtained at the same time. Hence the seperation methods.
ORIGIN OF DNA COMPUTING
The current speed of innovation and new developments in the PC industry, discussed in the section on the invention of the microprocessor, is based on Moore's Law, which states that the number of transistors that can be built on the same size piece of silicon will double every eighteen months. But the laws of physics suggest that this doubling cannot be sustained forever. Eventually transistors will become so tiny that their silicon components will approach the size of molecules. At these tiny distances, the dynamics of electrons are governed by the laws of quantum physics, permitting electrons to jump from one place to another without passing through the gap between, thereby causing fatal shortcuts. Consequently, physicists are looking for a successor to silicon. Below, I will summarise two principled alternatives that are currently being explored. A discussion of further options can be found in an essay by Michio Kaku.

DNA Fundamentals
DNA, Deoxyribonucleic Acid, is the molecular basis of heredity and localized especially in mostcell nucleus. DNA molecules consist of two long chains held together by complementary base pairs.
A DNA chain is a long, unbranched polymer composed of only four type subunits. These are the deoxyribonucleotides containing the bases adenine (A), cytosine(C), guanine (G), and thymine (T). The nucleotides are linked together by covalent phosphodiester bonds that join the 5’ carbon of one deoxyribose group to the 3’ carbon of the next. The four kinds of bases are attached to this repetitive sugar-phosphate chain.
The two long chains of a DNA molecule are held together by complementary base pairs. Three hydrogen bonds form between G and C, and two hydrogen bonds exist between A and T. The base-pairing mechanism is the basis for DNA replication.

DNA STRUCTURE
As a direct consequence of the base-pairing mechanism, it becomes evident that DNA carries information by means of the linear sequence of its nucleotides. Each nucleotide-A, C, T, or G – can be considered a letter in a four-letter alphabet that is used to write our biological messages in a linear “ticker-tape” form. Organisms differ because their respective DNA molecules carry different nucleotide sequences and therefore different biological message.
A typical animal cell contains a meter of DNA (3*10⁹ Nucleotides). Written in a linear alphabet of four letters, an unusually small human gene would occupy a quarter of a page of text, while the genetic information carried in a human cell would fill a book of more than 500,000 pages.



DNA COMPUTER:
DNA computer uses the recombinative property of dna to perform operations.The main benefit of using DNA computers to solve complex problems is that different possible solutions are created all at once. This is known as parallel processing. Humans and most electronic computers attempt to solve the problem one process at a time (linear processing). DNA itself provides the added benefits of being a cheap, energy-efficient resource.
In a different perspective, more than 10 trillion DNA molecules can fit into an area no larger than 1 cubic centimeter. With this, a DNA computer could hold 10 terabytes of data and perform 10 trillion calculations at a time.


THE ADLEMAN’S EXPERIMENT(Hamiltonian Path problem):

There is no better way to understand how something works than by going through an example step by step. So let’s solve Hamiltonian Path problem, using the DNA methods demonstrated by Adleman. The concepts are the same but the example has been simplified to make it easier to follow and present.

Suppose that I live in LA, and need to visit four cities: Houston, Chicago, Miami, and NY, with NY being my final destination. The airline I’m taking has a specific set of connecting flights that restrict which routes I can take (i.e. there is a flight from L.A. to Chicago, but no flight from Miami to Chicago). What should my itinerary be if I want to visit each city only once?

It should take you only a moment to see that there is only one route. Starting from L.A. you need to fly to Chicago, Dallas, Miami and then to N.Y. Any other choice of cities will force you to miss a destination, visit a city twice, or not make it to N.Y. For this example you obviously don’t need the help of a computer to find a solution. For six, seven, or even eight cities, the problem is still manageable. However, as the number of cities increases, the problem quickly gets out of hand. Assuming a random distribution of connecting routes, the number of itineraries you need to check increases exponentially. Pretty soon you will run out of pen and paper listing all the possible routes, and it becomes a problem for a computer...
...or perhaps DNA. The method Adleman used to solve this problem is basically the shotgun approach mentioned previously. He first generated all the possible itineraries and then selected the correct itinerary. This is the advantage of DNA. It’s small and there are combinatorial techniques that can quickly generate many different data strings. Since the enzymes work on many DNA molecules at once, the selection process is massively parallel.

Specifically, the method based on Adleman’s experiment would be as follows:

Generate all possible routes.
Select itineraries that start with the proper city and end with the final city.
Select itineraries with the correct number of cities.
Select itineraries that contain each city only once.
All of the above steps can be accomplished with standard molecular biology techniques.

Part I: Generate all possible routes
Strategy: Encode city names in short DNA sequences. Encode itineraries by connecting the city sequences for which routes exist.

DNA can simply be treated as a string of data. For example, each city can be represented by a "word" of six bases:

Los Angeles GCTACG
Chicago CTAGTA
Dallas TCGTAC
Miami CTACGG
New York ATGCCG

The entire itinerary can be encoded by simply stringing together these DNA sequences that represent specific cities. For example, the route from L.A -> Chicago -> Dallas -> Miami -> New York would simply be GCTACGCTAGTATCGTACCTACGGATGCCG, or equivalently it could be represented in double stranded form with its complement sequence.

So how do we generate this? Synthesizing short single stranded DNA is now a routine process, so encoding the city names is straightforward. The molecules can be made by a machine called a DNA synthesizer or even custom ordered from a third party. Itineraries can then be produced from the city encodings by linking them together in proper order. To accomplish this you can take advantage of the fact that DNA hybridizes with its complimentary sequence. For example, you can encode the routes between cities by encoding the compliment of the second half (last three letters) of the departure city and the first half (first three letters) of the arrival city. For example the route between Miami (CTACGG) and NY (ATGCCG) can be made by taking the second half of the coding for Miami (CGG) and the first half of the coding for NY (ATG). This gives CGGATG. By taking the complement of this you get, GCCTAC, which not only uniquely represents the route from Miami to NY, but will connect the DNA representing Miami and NY by hybridizing itself to the second half of the code representing Miami (...CGG) and the first half of the code representing NY (ATG...). For example:

Random itineraries can be made by mixing city encodings with the route encodings. Finally, the DNA strands can be connected together by an enzyme called ligase. What we are left with are strands of DNA representing itineraries with a random number of cities and random set of routes. For example:

We can be confident that we have all possible combinations including the correct one by using an excess of DNA encodings, say 10^13 copies of each city and each route between cities. Remember DNA is a highly compact data format, so numbers are on our side.

Part II: Select itineraries that start and end with the correct cities
Strategy: Selectively copy and amplify only the section of the DNA that starts with LA and ends with NY by using the Polymerase Chain Reaction.

After Part I, we now have a test tube full of various lengths of DNA that encode possible routes between cities. What we want are routes that start with LA and end with NY. To accomplish this we can use a technique called Polymerase Chain Reaction (PCR), which allows you to produce many copies of a specific sequence of DNA. PCR is an iterative process that cycles through a series of copying events using an enzyme called polymerase. Polymerase will copy a section of single stranded DNA starting at the position of a primer, a short piece of DNA complimentary to one end of a section of the DNA that you're interested in. By selecting primers that flank the section of DNA you want to amplify, the polymerase preferentially amplifies the DNA between these primers, doubling the amount of DNA containing this sequence. After many iterations of PCR, the DNA you're working on is amplified exponentially. So to selectively amplify the itineraries that start and stop with our cities of interest, we use primers that are complimentary to LA and NY. What we end up with after PCR is a test tube full of double stranded DNA of various lengths, encoding itineraries that start with LA and end with NY.



Next: Final steps
Part III: Select itineraries that contain the correct number of cities.
Strategy: Sort the DNA by length and select the DNA whose length corresponds to 5 cities.

Our test tube is now filled with DNA encoded itineraries that start with LA and end with NY, where the number of cities in between LA and NY varies. We now want to select those itineraries that are five cities long. To accomplish this we can use a technique called Gel Electrophoresis, which is a common procedure used to resolve the size of DNA. The basic principle behind Gel Electrophoresis is to force DNA through a gel matrix by using an electric field. DNA is a negatively charged molecule under most conditions, so if placed in an electric field it will be attracted to the positive potential. However since the charge density of DNA is constant (charge per length) long pieces of DNA move as fast as short pieces when suspended in a fluid. This is why you use a gel matrix. The gel is made up of a polymer that forms a meshwork of linked strands. The DNA now is forced to thread its way through the tiny spaces between these strands, which slows down the DNA at different rates depending on its length. What we typically end up with after running a gel is a series of DNA bands, with each band corresponding to a certain length. We can then simply cut out the band of interest to isolate DNA of a specific length. Since we known that each city is encoded with 6 base pairs of DNA, knowing the length of the itinerary gives us the number of cities. In this case we would isolate the DNA that was 30 base pairs long (5 cities times 6 base pairs).



Part IV: Select itineraries that have a complete set of cities
Strategy: Successively filter the DNA molecules by city, one city at a time. Since the DNA we start with contains five cities, we will be left with strands that encode each city once.

DNA containing a specific sequence can be purified from a sample of mixed DNA by a technique called affinity purification. This is accomplished by attaching the compliment of the sequence in question to a substrate like a magnetic bead. The beads are then mixed with the DNA. DNA, which contains the sequence you're after then hybridizes with the complement sequence on the beads. These beads can then be retrieved and the DNA isolated.

So we now affinity purify fives times, using a different city complement for each run. For example, for the first run we use L.A.'-beads (where the ' indicates compliment strand) to fish out DNA sequences which contain the encoding for L.A. (which should be all the DNA because of step 3), the next run we use Dallas'-beads, and then Chicago'-beads, Miami'-beads, and finally NY'-beads. The order isn’t important. If an itinerary is missing a city, then it will not be "fished out" during one of the runs and will be removed from the candidate pool. What we are left with are the are itineraries that start in LA, visit each city once, and end in NY. This is exactly what we are looking for. If the answer exists we would retrieve it at this step.

Reading out the answer
One possible way to find the result would be to simply sequence the DNA strands. However, since we already have the sequence of the city encodings we can use an alternate method called graduated PCR. Here we do a series of PCR amplifications using the primer corresponding to L.A., with a different primer for each city in succession. By measuring the various lengths of DNA for each PCR product we can piece together the final sequence of cities in our itinerary. For example, we know that the DNA itinerary starts with LA and is 30 base pairs long, so if the PCR product for the LA and Dallas primers was 24 base pairs long, you know Dallas is the fourth city in the itinerary (24 divided by 6). Finally, if we were careful in our DNA manipulations the only DNA left in our test tube should be DNA itinerary encoding LA, Chicago, Miami, Dallas, and NY. So if the succession of primers used is LA & Chicago, LA & Miami, LA & Dallas, and LA & NY, then we would get PCR products with lengths 12, 18, 24, and 30 base pairs.

Advantages
1. By DNA computing, people can get and analyze the information of materials. Through DNA computing, we can find all the genes in the DNA sequence and to develop tools for using this information in the study of some fields, such as biology, medicine biology, physics, and so on. The team from HP and U.C.L.A. has found a way to build circuits using chemical processes, making the switches as small as a molecule. Tim Gardner, a graduate student at Boston University, recently made a genetic system that can store a single bit of information—either a 1 or a 0.
2. More parallel: for some problem too big to fit or run in a silicon machine, DNA computer, which be with pure parallel power or massive memory, will be able to do a computation quickly than a powerful supercomputer.
3. By creating DNA computing, some fields are combined together to reach a desirable goal, by the way, this is improving those fields and some new fields come out.
Applications
A lot of research has been going on in this field and here is description of two softwares based on the concept of DNA computing and this idea of implementing the idea on DNA Computing in sotwares is called Soft Molecular Computing.

EDNA, integrated software platform
This software takes advantage of digital computers to gain realistic insights on actual test tube performance of a protocol before they are carried out in the lab. Basically the idea is to test whether a particular problem is feasible if carried out in lab. EDNA is object oriented and extensible, so that it can easily evolve as the field progresses. EDNA includes graphical interfaces and click-and-drag facilities to enable easy use.

CYBERCYCLER, Virtual Lab
A CYBERCYCLER has been constructed to experimentally demonstrate the feasibility of DNA based computation. The implemented transformation modules in the software are melting, hybridization, polymerization, ligation and CYBERGEL output. The CYBERCYCLER was originally written in C++ and its transformation modules are in the process of being converted to Java classes.

DNA Steganography
The idea of DNA Computing can also be used in the field of security for data transmission. The idea is very simple.
 First convert the alphabets into combination of four nucleotides.
 Create a strand of DNA based on that code
 This piece of DNA is placed in the middle plus short marker sequences at the ends of the message.
 The encoded piece of DNA is then placed into a piece of human DNA and is then mixed with other DNA strands.
 The mixture is then dried on to paper that can be cutup into microdots with each dot containing billions of strands of DNA.
 The key to decrypting the message lies in knowing which markers on each end of the DNA are the correct ones.
DNA Authentication
Taiwan introduced the world's first DNA authentication chip. Inside the chip is synthesized DNA, which can be identified by a device similar to an identification card or a credit card reader. The synthesized DNA inside the chip generates DNA signals which only the company's readers can detect and authenticate.
Disadvantages and limitations of DNA Computing:
1. Slow: algorithms proposed so far use really slow molecular-biological operations. Each primitive operation takes hours when you run them with a small test tube of DNA. Scale up to the vast amounts of DNA we're talking about, and they may slow down dramatically.
2. Hydrolysis: the DNA molecules can fracture. Over the six months you're computing, your DNA system is gradually turning to water. DNA molecules can break – meaning a DNA molecule, which was part of your computer, is fracture by time.
3. Unreliable: every operation you want to do in your DNA computer is random. The components in the DNA computer are probabilistic. Because there are some noisy components, the computing sometimes is not reliable. If a tiny subcircuit is supposed to give the answer "1," it may yield that answer 90 percent of the time and "0" the rest of the time. To make DNA computing work, we have to figure out how to build a reliable computer out of noisy components.
4. Not transmittable: the model of the DNA computer is concerned as a highly parallel computer, with each DNA molecule acting as a separate process or. In a standard multiprocessor a Connection-buses transmit information from one processor to the next. But the problem of transmitting information from one molecule to another in a DNA computer has yet to be solved. Current DNA algorithms compute successfully without passing any information, but this limits their flexibility.
5. Not practical: DNA computing is not a here and now practical technology. It just is a pie-in-the-sky research project.
6. No generality: Some concrete algorithms are just for solving some concrete problems. Every algorithm has some constraints on it.
CONCLUSION
Though DNA –COMPUTING is a method to solve very complex problems, at least on paper, its very difficult to realize it with the technology available today. More research and study has to be made in this field to make it a reality in the near future. If it happens so, then the present silicon technology would be replaced by dna, which itself has the capacity of storing data and can solve problems. We can expect this to happen ,if we really desire to have a computer which is far ahead of the ones’ we use today. Thus this is one of the fields that has a bright future and wider applications .
“If the purpose of life is to process information stored in DNA, then trying to perfect DNA computing, in a sense, we are trying to create life.”

paper-4

ABSTRACT

It's a hundred times faster than the best serial supercomputer. It's a billion times more energy efficient. It's a trillion times denser than the best storage media. It's a teaspoonful of DNA that's a computer! And Leonard Adleman invented it. Adleman, a mathematician well-known for his work in computer security and cryptography, was struck by the similarity between DNA - the basic stuff of life - and computers. Using what is essentially a four-letter alphabet, DNA stores information that is manipulated by living organisms in almost exactly the same way computers work their way through strings of 1s and 0s. So, could DNA be made to function like a computer? If the answer's yes, new ways of building entirely different kinds of computers would open up - computers so fast they could solve some of today's unsolvable problems, so small they would exist at the molecular level. Once he got the idea of using DNA to compute, Adleman had to think of a problem for it to solve. Hamilton's traveling salesman was the ticket. Could DNA find a single itinerary that would allow our airborne entrepreneur to travel efficiently through seven cities with fourteen interconnecting flights? A single gram of dried DNA, about the size of a half-inch sugar cube, can hold as much information as a trillion compact discs. Still in their infancy, DNA computers will be capable of storing billions of times more data than your personal computer. While it currently exists only in theory, it's possible that in the years to come computers based on the work of Adleman, Lipton, and others will come to replace traditional silicon-based machines. This paper provides some basic information about history, working, usefulness and what the future of DNA Computing would be. This paper tries it’s best to explore the concept of DNA computing.













INTRODUCTION

All the time, computer chip manufacturers are furiously racing to make the next microprocessor that will topple speed records. Sooner or later, though, this competition is bound to hit a wall. Microprocessors made of silicon will eventually reach their limits of speed and miniaturization. Chipmakers need a new material to produce faster computing speeds. Its unbelievable where scientists have found the new material they need to build the next generation of microprocessors. Millions of natural supercomputers exist inside living organisms, including your body. DNA (deoxyribonucleic acid) molecules, the material our genes are made of, have the potential to perform calculations many times faster than the world's most powerful human-built computers. DNA might one day be integrated into a computer chip to create a so-called biochip that will push computers even faster. DNA molecules have already been harnessed to perform complex mathematical problems. DNA computing, in the literal sense, is the use of DNA (Deoxyribose Nucleic Acid) molecules, the molecules that encode genetic information for all living things, in computers. This is accomplished in a suspended solution of DNA, where certain combinations of DNA molecules are interpreted as a particular result to a problem encoded in the original molecules present.

DNA COMPUTING BIRTH AND TRAVELLING SALESMAN PROBLEM

DNA computers technology is still in development, and didn't even exist as a concept a decade ago. 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". 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. DNA is used 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.
Drawing this problem out on paper, a solution could be found out faster than Adleman did using his DNA test-tube computer. Here are the steps taken in the Adleman DNA computer experiment:
• 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.
• 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.
• Within a few seconds, all of the possible combinations of DNA strands, which represent answers, are created in the test tube.
• Eliminating 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 DNA computer is far from challenging silicon-based 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. Nevertheless, his work is significant for a number of reasons.
• It illustrates the possibilities of using DNA to solve a class of problems that is difficult or impossible to solve using traditional computing methods.
• It's an example of computation at a molecular level, potentially a size limit that may never be reached by the semiconductor industry.
• It demonstrates unique aspects of DNA as a data structure
• It demonstrates that computing with DNA can work in a massively parallel fashion.

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. For instance, a genetic gate called the "And gate" links two DNA inputs by chemically binding them so they're locked in an end-to-end structure, similar to the way two Legos might be fastened by a third Lego between them. The researchers believe that these logic gates might be combined with DNA microchips to create a breakthrough in DNA computing.
DNA computer components -- logic gates and biochips -- will take years to develop into a practical, workable DNA computer. If such a computer is ever built, scientists say that it will be more compact, accurate and efficient than conventional computers.

DNA: A UNIQUE DATA STRUCTURE

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 a remarkable data density of nearly 18 Mbits per inch. In two dimensions, if assumed one base per square nanometer, the data density is over one million Gbits per square inch. Comparing this to the data density of a typical high performance hard drive, which is just 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. Occasionally, DNA enzymes simply make mistakes, cutting where they shouldn't, or inserting a T for a G. 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).

OPERATIONS IN PARALLEL

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

DNA: A SUCCESSOR TO SILICON

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.
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.
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 teardrop-sized 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.
The first DNA computers are unlikely to feature word processing, e-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. Studying DNA computers may also lead us to a better understanding of a more complex computer -- the human brain.
WILL FUTURE COMPUTERS BE MADE OF DNA?
Molecular biologists are beginning to unravel the information processing tools-such as enzymes, copying tools, proofreading mechanisms and so on-that evolution has spent billions of years refining. Now taking those tools in large numbers of DNA molecules and using them as biological computer processors. Here's how it works. Information specifying a computational problem too complex for even a supercomputer is encoded in DNA. Then various molecular-biological tools are used to process this information. In a hot-tub sized vat of DNA, at normal laboratory concentration, one might easily imagine having 1021 DNA molecules, each potentially encoding 400 bits of information. That's 100,000 billion times as much information as that can be stored in a 1-gigabyte hard disk. Each of these molecules acts, in a sense, as a separate processor in a giant multiprocessor. So, in effect, a thousand billion billion processors are available.
Sounds exciting, but there are problems. One is that the algorithms proposed so far use really slow molecular-biological operations. Each primitive operation in the DNA computer takes hours. That's a clock rate maybe 1011 times slower than a 100MHz Pentium. That's why there is no worry about a DNA-based computer replacing your Pentium. It will never respond quickly enough on simple problems. But, it makes up for its slothfulness with pure parallel power or massive memory on some problem too big to fit or run in a silicon machine. If all goes as expected, a DNA computer will be able to do a computation that would take millions of years on the most powerful supercomputer in, say, six months. But there are other hurdles. These processes take hours when you run them with a small test tube of DNA. Scale up to the vast amounts of DNA, and they may slow down dramatically. Another hazard is hydrolysis-the DNA molecules can fracture. Over the six months if computing goes on, DNA system is gradually turning to water.
In addition, every operation is somewhat random. Unlike Pentium's transistors-which reliably compute what they're supposed to-the components in the DNA computer are probabilistic. If a tiny sub circuit is supposed to give the answer "1," it may yield that answer 90 percent of the time and "0" the rest of the time. To make DNA computing work, there is need to figure out how to build a reliable computer out of noisy components.
Yet another hitch concerns the model of the DNA computer as a highly parallel computer, with each DNA molecule acting as a separate process or. In a standard multiprocessor-say a Cray or a Connection-buses transmit information from one processor to the next. But the problem of transmitting information from one molecule to another in a DNA computer has yet to be solved. Current DNA algorithms compute successfully without passing any information, but this limits their flexibility.
Finally, still looking for a giant problem for the DNA system to compute. No one has yet suggested a concrete puzzle worth solving-and a concrete algorithm for solving it using DNA-that couldn't be solved more quickly some other way.
All these obstacles sound daunting, and any one of them may be enough to kill DNA computing. But computer scientists have all kinds of creative ideas for overcoming these problems. DNA computing is where silicon computing was the year after the transistor was invented. It doesn't do anything useful yet, but who knows what might happen if you play with it?
DNA computing is not a here-and-now practical technology; it's a pie-in-the-sky research project. It has astounding possibilities, but it's going to take a lot of good ideas, hard work and luck to realize its potential. At a minimum, this research will shed a whole new light on the computing DNA does in living creatures. If the purpose of life is to process information stored in DNA, then in trying to perfect DNA computing, in a sense, it’s trying to create life.
CONCLUSION

So will DNA ever be used to solve a traveling salesman problem with a higher number of cities than can be done with traditional computers? Well, considering that the record is whopping 13,509 cities, it certainly will not be done with the procedure described above. It took this group only three months, using three Digital AlphaServer 4100s (a total of 12 processors) and a cluster of 32 Pentium-II PCs. The solution was possible not because of brute force computing power, but because they used some very efficient branching rules. This first demonstration of DNA computing used a rather unsophisticated algorithm, but as the formalism of DNA computing becomes refined, new algorithms perhaps will one day allow DNA to overtake conventional computation and set a new record.

On the side of the "hardware", improvements in biotechnology are happening at a rate similar to the advances made in the semiconductor industry. For instance, look at sequencing; what once took a graduate student 5 years to do for a PhD thesis takes Celera just one day. Just look at the number of advances in DNA-related technology that happened in the last five years. Today there are several companies making "DNA chips," where DNA strands are attached to a silicon substrate in large arrays (for example Affymetrix's gene chip). Production technology of MEMS is advancing rapidly, allowing for novel integrated small-scale DNA processing devices. The Human Genome Project is producing rapid innovations in sequencing technology. The future of DNA manipulation is speed, automation, and miniaturization.
DNA certainly has been the molecule of this century and most likely the next one. Considering all the attention that DNA has garnered, it isn’t too hard to imagine that one day we might have the tools and talent to produce a small-integrated desktop machine that uses DNA, or a DNA-like biopolymer, as a computing substrate along with set of designer enzymes. Perhaps it won’t be used to play Quake IV or surf the web -- things that traditional computers are good at -- but it certainly might be used in the study of logic, encryption, genetic programming and algorithms, automata, language systems, and lots of other interesting things that haven't even been invented yet.

The problems solved by DNA computers to date are rudimentary. Children could come up with the answers more quickly with a pencil and paper. But the researchers hope to someday inject tiny computers into humans to zap viruses, fix good cells gone bad and otherwise keep us healthy. They're also pursuing the idea that genetic material can self-replicate and grow into processors so powerful that they can handle problems too complex for silicon-based computers to solve. Eventually, the scientists aim to create self-sustaining computers that can be used, for instance, on deep-space voyages, to monitor and maintain the health of humans on board.

paper-3

DNA COMPUTING
DNA COMPUTING ABSTRACT

In this era where computational processes come to the rescue of Biological conundrums -the underlying dogma of Bioinformatics, this paper aspires to explore the vice-versa. The prime contention of the paper is to assert that DNA, the genetic material of all living organisms can be exploited as a computational tool.

Chipmakers need a new material to produce faster computing speed with fewer complexities. DNA, the material our genes are made of, is being used to build the next generation of microprocessors. Scientists are using this genetic material to create nano-computers that might take the place of silicon computers in the next decade.

A nascent technology that uses DNA molecules to build computers that are faster than the world’s most powerful human-built computers is called DNA computing. Molecular biologists are beginning to unravel the information processing tools such as enzymes, copying tools, proofreading mechanisms and so on, that evolution has spent millions of years refining. Now we are taking those tools in large numbers molecules and using them as biological computer processors.

DNA computing has a great deal of advantage over conventional silicon-based computing. DNA computers can store billions of times more data than your personal computer. DNA computers have the ability to work in a massively parallel fashion, performing many calculations simultaneously. DNA computing has made a remarkable progress in almost every field. It has found application in fields like biomedical, pharmaceutical, information security, cracking secret codes, etc.

Scientists see such DNA computers as future competitors for their more conve-
ntional cousins because miniaturization is reaching its limits and DNA has the potential to be
much faster than conventional computers.



1. Introduction

Man’s thirst for knowledge has driven the information revolution. Human brain, a master processor, processes the information about the internal and external environment and sends signals to take appropriate actions. In nature, such controls exist at every level. Even the smallest of the cells has a nucleus, which controls the cell. Where does this power actually come from? It lies in the DNA. The ability to harness this computational power shall determine the fate of next generation of computing.

DNA computing is a novel technology that seeks to capitalize on the enormous informational 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. The appeal of DNA computing lies in the fact that DNA molecules can store far more information than any existing conventional computer chip. Also, utilizing DNA for complex computation can be much faster than utilizing a conventional computer, for which massive parallelism would require large amounts of hardware, not simply more DNA.

The concepts of utilizing DNA computing in the field of data encryption and DNA authentication methods for thwarting the counterfeiting industry are subjects that have been surfacing in the media of late. Researchers have been looking at alternatives to the traditional microprocessor design. One of the most interesting and emerging technology is DNA computers. The computing power of a teardrop-sized DNA computer, will be more powerful than the world’s most powerful supercomputer.

The massive parallelism involved in DNA interaction vindicates the idea and hence the idea of using DNA as a computational tool for parallel processing.

2. What is DNA?
Before delving into the principles of DNA computing, we must have a basic understanding of what DNA actually is. All organisms on this planet are made of the same type of genetic blueprint which bind us together. The way in which that blueprint is
coded is the deciding factor as to whether you will be bald, have a bulbous nose, male, female or even whether you will be a human or an oak tree.
Within the cells of any organism is a substance called Deoxyribonucleic Acid (DNA) which is a double-stranded helix of nucleotides which carries the genetic information of a cell. This information is the code used within cells to form proteins and is the building block upon which life is formed.
Strands of DNA are long polymers of millions of linked nucleotides. These nucleotides consist of one of four nitrogen bases, a five carbon sugar and a phosphate group. The nucleotides that make up these polymers are named after the nitrogen base that it consists of; Adenine (A), Cytosine (C), Guanine (G) and Thymine (T). These nucleotides will only combine in such a way that C always pairs with G and T always pairs with A. The two strands of a DNA molecule are anti parallel where each strand runs in an opposite direction .

The combination of these 4 nucleotides in the estimated million long polymer strands can result in billions of combinations within a single DNA double-helix.These massive amount of combinations allows for the multitude of differences between every living thing on the planet from the large scale(mammal vs. plant), to the small(blue eyes vs. green eyes). What does all this chemistry and biology have to do with security you might ask? To answer that question we must first look at how biological science can be applied to mathematical computation in a field known as DNA computing.





Graphical representation of inherent bonding properties of DNA Illustration of double helix shape of DNA.



The bases (nucleotides) are spaced every 0.35 nanometers along the DNA molecule, giving it a remarkable data density of nearly 18Mbits per inch. These nucleotides will only combine in such a way that C always pairs with G and T always pairs with A. This complementarity makes DNA a unique data structure for computation and can be exploited in many ways.For example if one strand of DNA is of the sequence
AGTCAT
The other must be of the sequence
TCAGTA
i.e
A G T C A T
| | | | | |
T C A G T A

Because A always pairs T, and G with C.

This is called the complementarity of the DNA. One strand is always the complement of the other strand. Thus if two complementary single stranded DNA molecules come together they bind to form double stranded helical molecule.
POLYMERASE, LIGASE
These are enzymes that are vital for DNA replication and slick together the DNA molecules when they come into close proximity in a linear fashion.

3. A Successor to Silicon
Silicon microprocessors have been the heart of computing world for more than forty years. Computer chip manufacturers are furiously racing to make the next microprocessor that will topple speed records and in the process are cramming more and more electronic devices onto the microprocessor. Many have predicted that Moore’s law (which states that the microprocessors would double in complexity every two years) will soon reach its end, because of the physical speed and miniaturization limits of silicon microprocessors.

DNA computers have the potential to take computing to new levels, picking up where Moore’s law leave off. DNA computers could surpass their silicon-based predecessors. The several advantages of DNA over silicon are:

 As long as there are cellular organisms, there will 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.

 DNA molecules have a potential to store extensively large amount of information. It has been estimated that a gram of dried DNA can hold as much information as a trillion CD’s. More than 10 trillion DNA molecules can fit into an area of 1 cubic centimeter. With this small amount if DNA a computer would be able to hold 10 terabytes of data, and perform 10 trillion calculations at a time.
In a biochemical reaction taking place in a tiny surface area, a very large number of DNA molecules can operate in concert, creating a parallel processing system that mimics the ability of the most powerful supercomputer. DNA computers have the ability to perform many calculations simultaneously; specifically, on the order of 10^9 calculations per ml of DNA per second! A calculation that would take 10^22 modern computers working in parallel to complete in the span of one human’s life would take one DNA computer only 1 year to polish off!

4. Applications
 DNA logic gates are the first step towards 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. Recent works have shown how these gates can be employed to carry out fundamental computational operations, addition of two numbers expressed in binary. This invention of DNA logic gates and their uses are a breakthrough in DNA computing.
A group of researchers at Princeton University in early 2000 demonstrated an RNA computer similar to Adleman’s, which had the ability to solve a chess problem involving how many ways there are to place knights on a chessboard so that none can take the others.
While a desktop PC is designed to perform one calculation very fast, DNA strands produce billions of potential answers simultaneously. This makes the DNA computer suitable for solving "fuzzy logic" problems that have many possible solutions rather than the either/or logic of binary computers. In the future, some speculate, there may be hybrid machines that use traditional silicon for normal processing tasks but have DNA co-processors that can take over specific tasks they would be more suitable for.
 DNA computing is in its infancy, and its implications are only beginning to be explored. But DNA computing devices could revolutionize the pharmaceutical and biomedical fields. Some scientists predict a future where our bodies are patrolled by tiny DNA computers that monitor our well-being and release the right drugs to repair damaged or unhealthy tissue. They could act as ‘Doctors in a cell’.
DNA computing can be used by national governments for cracking secret codes, or by airlines wanting to map more efficient routes. The concept of using DNA computing in the fields of cryptography, steganography and authentication has been identified as a possible technology that may bring forward a new hope for unbreakable algorithms in the world of information security.
5. Scope and recent updates
Scientists have taken DNA from the free-floating world of the test tube and anchored it securely to a surface of glass and gold. University of Wiscosnin-Madison researchers have developed a thin, gold-coated plate of glass about an inch square. They believe it is the optimum working surface on which they can attach trillions of strands of DNA. Putting DNA computing on a solid surface greatly simplifies the complex and repetitive steps previously used in rudimentary DNA computers. Importantly it takes DNA out of the test tube and puts it on a solid surface, making the technology simpler, more accessible and more amenable to the development of large DNA computers capable of tackling the kind of complex problems that conventional computers now handle routinely. Researchers believe that by the year 2010 the first DNA chip will be commercially available.

Advantages
 The advantage of DNA approach is that it works in parallel, processing all possible answers simultaneously.
 DNA computing is an example of computing at a molecular level, potential a size limit that may never be reached by the semiconductor industry.
 It can be used to solve a class of problems that are difficult or impossible to solve using traditional computing methods.
 There is no power required for DNA computing while the computation is taking place. The chemical bonds that are the building blocks of DNA happen without any outside power source. It’s energy-efficiency is more than a million times that of a PC.

Disadvantages
 DNA computers require human assistance.
 Technological challenges remain before DNA computing. Researchers need to develop techniques to reduce number of computational errors produced by unwanted chemical reactions with the DNA strands. They need to eliminate, combine, or accelerate the steps in processing the DNA.
 The extrapolation and practical computational environment required are daunting. The ‘test tube’ environment used for DNA computing is far from practical for everyday use.



CONCLUSION

DNA computers have tremendous potential to compete with electronic computers, which boasts of superior speeds in computation.. A new face in the field of computation is introduced and the possibility of using DNA as a computational tool is high-lightened and described that even a molecular biology laboratory can be made to perform computational operations just like the dry lab or the computer lab, broadening the horizon of computational sciences. Scientists and mathematicians around the world are now looking at the application of DNA computers to a whole range of “intractable” computing problems.
DNA computing can be viewed as a manifestation of an emerging new area of science made possible by our rapidly developing ability to control the molecular world.