23-04-2011, 02:28 PM
[attachment=12707]
DNA Computing
Abstract— An overview and categorization of existing research in DNA based computation, the possible advantages that different models have over conventional computational methods, and potential applications that might emerge from, or serve to motivate, the creation of a working Bimolecular Computer. The emerging paradigms of DNA based (or bimolecular) computation has yet to find a practical use, despite many possible advantages over existing computational methods. Possible applications are discussed for different models of DNA computation as well as their relative viability.
DNA computing has a great deal of advantage over conventional silicon-based computing. DNA computers can store billions of times more data than personal computer. DNA computers have the ability to work in a massively parallel fashion, performing many calculations simultaneously. DNA molecules that provide the input can also provide all the necessary operational energy.
Computer scientists are joining forces with molecular biologists and chemists to explore the potential for computation using information carrying biological polymers such as nucleic acids (DNA and RNA). "DNA computing” is a subset of molecular computing. "The key feature of DNA for computing is its information content.
DNA computing is in its infancy, and its implications are only beginning to be explored. But it could transform the future of computers, especially in pharmaceutical and biomedical Applications.
I. INTRODUCTION
DNA is the major information storage molecule in living cells, and billions of years of evolution have tested and refined both this wonderful informational molecule and highly specific enzymes that can either duplicate the information in DNA molecules or transmit this information to other DNA molecules.
Instead of using electrical impulses to represent bits of information, the DNA computer uses the chemical properties of these molecules by examining the patterns of combination or growth of the molecules or strings. DNA can do this through the manufacture of enzymes, which are biological catalysts that could be called the 'software' used to execute the desired calculation.
A. Structure of DNA
All organisms on this planet are made of the same type of genetic blueprint, which bind us together. 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. 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 letters A (Adenine), T (Thymine), C (Cytosine) and G (Guanine).
Fig 1.Graphical representation of inherent bonding properties of DNA Fig 2.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 complementarily makes DNA a unique data structure for computation and can be exploited in many ways.
The idea of using DNA to store and process information took off in the year 1994 when Leonard Adleman, a computer scientist at the University of Southern California, came to the conclusion that DNA had computational potential. Adleman caused an avalanche in the fields of biology; mathematics and computers by solving a problem called the Directed Hamiltonian Path problem or sometimes referred to as the Travelling Salesman Problem.
DNA computers use deoxyribonucleic acids--A (adenine), C (cytosine), G (guanine) and T (thymine)--as the memory units and recombinant DNA techniques already in existence carry out the fundamental operations. In a DNA computer, computation takes place in test tubes or on a glass slide coated in 24K gold. The input and output are both strands of DNA, whose genetic sequences encode certain information. A program on a DNA computer is executed as a series of biochemical operations, which have the effect of synthesizing, extracting, modifying and cloning the DNA strands.
The only fundamental difference between conventional computers and DNA computers is the capacity of memory units: electronic computers have two positions (on or off), whereas DNA has four (C, G, A or T). Many restriction enzymes cut the two strands of double-stranded DNA at different positions leaving overhangs of single-stranded DNA. Two pieces of DNA may be rejoined if their terminal overhangs are complementary.
DNA represents information as a pattern of molecules on a strand. Each strand represents one possible answer. In each experiment, the DNA is tailored so that all conceivable answers to a particular problem are included. Researchers then subject all the molecules to precise chemical reactions that imitate the computational abilities of a traditional computer. Because molecules that make up DNA bind together in predictable ways, it gives a powerful "search" function. If the experiment works, the DNA computer weeds out all the wrong answers, leaving one molecule or more with the right answer. All these molecules can work together at once, so you could theoretically have 10 trillion calculations going on at the same time in very little space.
II. IMPLEMENTATION
DNA computing is a field that holds the promise of ultra-dense systems that pack megabytes of information into devices the size of a silicon transistor. Each molecule of DNA is roughly equivalent to a little computer chip. Conventional computers represent information in terms of 0's and 1's, physically expressed in terms of the flow of electrons through logical circuits, whereas DNA computers represent information in terms of the chemical units of DNA. Computing with an ordinary computer is done with a program that instructs electrons to travel on particular paths; with a DNA computer, computation requires synthesizing particular sequences of DNA and letting them react in a test tube or on a glass plate. In a scheme devised by Richard Lipton, the logical command "and" is performed by separating DNA strands according to their sequences, and the command "or" is done by pouring together DNA solutions containing specific sequences, merging.
By forcing DNA molecules to generate different chemical states, which can then be examined to determine an answer to a problem by combination of molecules into strands or the separation of strands, the answer is obtained.
Most of the possible answers are incorrect, but one or a few may be correct, and the computer's task is to check each of them and remove the incorrect ones using restrictive enzymes. The DNA computer does that by subjecting all of the strands simultaneously to a series of chemical reactions that mimic the mathematical computations an electronic computer would perform on each possible answer. When the chemical reactions are complete, researchers analyze the strands to find the answer -- for instance, by locating the longest or the shortest strand and decoding it to determine what answer it represents.
Computers based on molecules like DNA will not have vonNeumann architecture, but instead function best in parallel processing applications. They are considered promising for problems that can have multiple computations going on at the same time. Say for instance, all branches of a search tree could be searched at once in a molecular system while vonNeumann systems must explore each possible path in some sequence.
Information is stored in DNA as CG or AT base pairs with maximum information density of 2bits per DNA base location. Information on a solid surface is stored in a NON-ADDRESSED array of DNA words (W) of a fixed length (16 mers).
DNA Words are linked together to form large combinatorial sets of molecules.DNA computers are massively parallel, while electronic computers would require additional hardware, DNA computers just need more DNA. This could make the DNA computer more efficient, as well as more easily programmable.
A. How much information cam they store and process
Nucleic Acids are used because of density, efficiency and speed. DNA molecules can store far more information than any existing computer memory chip. This means that DNA computing is a far denser packing of molecular information compared with silicon-based computers. A single bacterium cell measures just a micron square - about the same size as a single silicon transistor - but holds more than a megabyte of DNA memory and has all the computational structures to sense and respond to its environment. To try to put this in some understandable perspective, it has been estimated that a gram of DNA can hold as much information as a trillion CDs.
So DNA molecules would be like mega-memory. In a biochemical reaction hundreds of trillions of DNA molecules can operate in parallel. DNA computers could store a bit, 0 or 1, of data in one cubic nanometer, one trillionth the size of the conventional computer's electronic storage. Thus a DNA computer could store massive quantities of information in the space a standard computer would use to store much less. A pound of DNA could contain more computer memory than all the electronic computers ever made. It would be about twice as fast as the fastest supercomputer, performing more than 2,000 instructions per second. DNA computers also require miniscule amounts of energy to perform. Because the biochemical operations involved are subject to errors and are often slow, rigorous tests of the accuracy and further technological development are needed.
B. what about efficiency
In both the solid-surface glass-plate approach and the test tube approach, each DNA strand represents one possible answer to the problem that the computer is trying to solve. The strands have been synthesized by combining the building blocks of DNA, called nucleotides, with one another, using techniques developed for biotechnology. The set of DNA strands is manufactured so that all conceivable answers are included. Because a set of strands is tailored to a specific problem, a new set would have to be made for each new problem.
Most electronic computers operate linearly--they manipulate one block of data after another--biochemical reactions are highly in parallel: a single step of biochemical operations can be set up so that it affects trillions of DNA strands. While a DNA computer takes much longer than a normal computer to perform each individual calculation, it performs an enormous number of operations at a time and requires less energy and space than normal computers.
Obviously if you want to perform one calculation at a time, DNA computers are not a viable option. When Adleman derived an optimal solution to a seven-city traveling-salesman problem, it took approximately one week. Unfortunately, you can solve the same problem on a piece of paper in about an hour - or by a digital computer in a few seconds. But when the number of cities is increased to just 70, the problem becomes intractable for even a 1,000-Mips supercomputer.
Adleman, now considered the father of DNA computing, is a professor at the University of Southern California and spawned the field with his paper, "Molecular Computation of Solutions of Combinatorial Problems." Since then, Adleman has demonstrated how the massive parallelism of a trillion DNA strands can simultaneously attack different aspects of a computation to crack even the toughest combinatorial problems, such as the government's supposedly uncrackable Data Encryption Standard.
DNA Computing
Abstract— An overview and categorization of existing research in DNA based computation, the possible advantages that different models have over conventional computational methods, and potential applications that might emerge from, or serve to motivate, the creation of a working Bimolecular Computer. The emerging paradigms of DNA based (or bimolecular) computation has yet to find a practical use, despite many possible advantages over existing computational methods. Possible applications are discussed for different models of DNA computation as well as their relative viability.
DNA computing has a great deal of advantage over conventional silicon-based computing. DNA computers can store billions of times more data than personal computer. DNA computers have the ability to work in a massively parallel fashion, performing many calculations simultaneously. DNA molecules that provide the input can also provide all the necessary operational energy.
Computer scientists are joining forces with molecular biologists and chemists to explore the potential for computation using information carrying biological polymers such as nucleic acids (DNA and RNA). "DNA computing” is a subset of molecular computing. "The key feature of DNA for computing is its information content.
DNA computing is in its infancy, and its implications are only beginning to be explored. But it could transform the future of computers, especially in pharmaceutical and biomedical Applications.
I. INTRODUCTION
DNA is the major information storage molecule in living cells, and billions of years of evolution have tested and refined both this wonderful informational molecule and highly specific enzymes that can either duplicate the information in DNA molecules or transmit this information to other DNA molecules.
Instead of using electrical impulses to represent bits of information, the DNA computer uses the chemical properties of these molecules by examining the patterns of combination or growth of the molecules or strings. DNA can do this through the manufacture of enzymes, which are biological catalysts that could be called the 'software' used to execute the desired calculation.
A. Structure of DNA
All organisms on this planet are made of the same type of genetic blueprint, which bind us together. 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. 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 letters A (Adenine), T (Thymine), C (Cytosine) and G (Guanine).
Fig 1.Graphical representation of inherent bonding properties of DNA Fig 2.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 complementarily makes DNA a unique data structure for computation and can be exploited in many ways.
The idea of using DNA to store and process information took off in the year 1994 when Leonard Adleman, a computer scientist at the University of Southern California, came to the conclusion that DNA had computational potential. Adleman caused an avalanche in the fields of biology; mathematics and computers by solving a problem called the Directed Hamiltonian Path problem or sometimes referred to as the Travelling Salesman Problem.
DNA computers use deoxyribonucleic acids--A (adenine), C (cytosine), G (guanine) and T (thymine)--as the memory units and recombinant DNA techniques already in existence carry out the fundamental operations. In a DNA computer, computation takes place in test tubes or on a glass slide coated in 24K gold. The input and output are both strands of DNA, whose genetic sequences encode certain information. A program on a DNA computer is executed as a series of biochemical operations, which have the effect of synthesizing, extracting, modifying and cloning the DNA strands.
The only fundamental difference between conventional computers and DNA computers is the capacity of memory units: electronic computers have two positions (on or off), whereas DNA has four (C, G, A or T). Many restriction enzymes cut the two strands of double-stranded DNA at different positions leaving overhangs of single-stranded DNA. Two pieces of DNA may be rejoined if their terminal overhangs are complementary.
DNA represents information as a pattern of molecules on a strand. Each strand represents one possible answer. In each experiment, the DNA is tailored so that all conceivable answers to a particular problem are included. Researchers then subject all the molecules to precise chemical reactions that imitate the computational abilities of a traditional computer. Because molecules that make up DNA bind together in predictable ways, it gives a powerful "search" function. If the experiment works, the DNA computer weeds out all the wrong answers, leaving one molecule or more with the right answer. All these molecules can work together at once, so you could theoretically have 10 trillion calculations going on at the same time in very little space.
II. IMPLEMENTATION
DNA computing is a field that holds the promise of ultra-dense systems that pack megabytes of information into devices the size of a silicon transistor. Each molecule of DNA is roughly equivalent to a little computer chip. Conventional computers represent information in terms of 0's and 1's, physically expressed in terms of the flow of electrons through logical circuits, whereas DNA computers represent information in terms of the chemical units of DNA. Computing with an ordinary computer is done with a program that instructs electrons to travel on particular paths; with a DNA computer, computation requires synthesizing particular sequences of DNA and letting them react in a test tube or on a glass plate. In a scheme devised by Richard Lipton, the logical command "and" is performed by separating DNA strands according to their sequences, and the command "or" is done by pouring together DNA solutions containing specific sequences, merging.
By forcing DNA molecules to generate different chemical states, which can then be examined to determine an answer to a problem by combination of molecules into strands or the separation of strands, the answer is obtained.
Most of the possible answers are incorrect, but one or a few may be correct, and the computer's task is to check each of them and remove the incorrect ones using restrictive enzymes. The DNA computer does that by subjecting all of the strands simultaneously to a series of chemical reactions that mimic the mathematical computations an electronic computer would perform on each possible answer. When the chemical reactions are complete, researchers analyze the strands to find the answer -- for instance, by locating the longest or the shortest strand and decoding it to determine what answer it represents.
Computers based on molecules like DNA will not have vonNeumann architecture, but instead function best in parallel processing applications. They are considered promising for problems that can have multiple computations going on at the same time. Say for instance, all branches of a search tree could be searched at once in a molecular system while vonNeumann systems must explore each possible path in some sequence.
Information is stored in DNA as CG or AT base pairs with maximum information density of 2bits per DNA base location. Information on a solid surface is stored in a NON-ADDRESSED array of DNA words (W) of a fixed length (16 mers).
DNA Words are linked together to form large combinatorial sets of molecules.DNA computers are massively parallel, while electronic computers would require additional hardware, DNA computers just need more DNA. This could make the DNA computer more efficient, as well as more easily programmable.
A. How much information cam they store and process
Nucleic Acids are used because of density, efficiency and speed. DNA molecules can store far more information than any existing computer memory chip. This means that DNA computing is a far denser packing of molecular information compared with silicon-based computers. A single bacterium cell measures just a micron square - about the same size as a single silicon transistor - but holds more than a megabyte of DNA memory and has all the computational structures to sense and respond to its environment. To try to put this in some understandable perspective, it has been estimated that a gram of DNA can hold as much information as a trillion CDs.
So DNA molecules would be like mega-memory. In a biochemical reaction hundreds of trillions of DNA molecules can operate in parallel. DNA computers could store a bit, 0 or 1, of data in one cubic nanometer, one trillionth the size of the conventional computer's electronic storage. Thus a DNA computer could store massive quantities of information in the space a standard computer would use to store much less. A pound of DNA could contain more computer memory than all the electronic computers ever made. It would be about twice as fast as the fastest supercomputer, performing more than 2,000 instructions per second. DNA computers also require miniscule amounts of energy to perform. Because the biochemical operations involved are subject to errors and are often slow, rigorous tests of the accuracy and further technological development are needed.
B. what about efficiency
In both the solid-surface glass-plate approach and the test tube approach, each DNA strand represents one possible answer to the problem that the computer is trying to solve. The strands have been synthesized by combining the building blocks of DNA, called nucleotides, with one another, using techniques developed for biotechnology. The set of DNA strands is manufactured so that all conceivable answers are included. Because a set of strands is tailored to a specific problem, a new set would have to be made for each new problem.
Most electronic computers operate linearly--they manipulate one block of data after another--biochemical reactions are highly in parallel: a single step of biochemical operations can be set up so that it affects trillions of DNA strands. While a DNA computer takes much longer than a normal computer to perform each individual calculation, it performs an enormous number of operations at a time and requires less energy and space than normal computers.
Obviously if you want to perform one calculation at a time, DNA computers are not a viable option. When Adleman derived an optimal solution to a seven-city traveling-salesman problem, it took approximately one week. Unfortunately, you can solve the same problem on a piece of paper in about an hour - or by a digital computer in a few seconds. But when the number of cities is increased to just 70, the problem becomes intractable for even a 1,000-Mips supercomputer.
Adleman, now considered the father of DNA computing, is a professor at the University of Southern California and spawned the field with his paper, "Molecular Computation of Solutions of Combinatorial Problems." Since then, Adleman has demonstrated how the massive parallelism of a trillion DNA strands can simultaneously attack different aspects of a computation to crack even the toughest combinatorial problems, such as the government's supposedly uncrackable Data Encryption Standard.
