DNA COMPUTING : DNA COMPUTING A Conceptual Overview
By MITALI NARWANI 1 Slide 2: DNA Computing DNA computing or molecular computing can be defined as the use of biological molecules, primarily DNA (or RNA), to solve computational problems that are adapted to this new biological format.
DNA computing is a field in which computational problems are coded into the DNA structure, and left under the action of enzymes and chemicals.
From the resulting DNA structure the result is interpreted and evaluated. 2 Slide 3: Logic Gates In our conventional silicon based computers the basic units of data interpretation are logic gates like AND,OR etc.
These logic gates consist of transistors which in turn are made of silicon-a semiconductor.
Logic gates provide series of smaller steps for complex calculations.
Binary logic works on 1’s and 0’s in the central processing unit. 3 Slide 4: DNA Logic Gates In a DNA computer the basic units of data interpretation are logic gates made up of DNA strands.
In DNA logic gate inputs are replaced by single stranded DNA molecule. The way by which these molecules bind dictates the operation.
Chemical binding of two DNA strands in end-end operation illustrates the gate operation.
DNA ligase seals the gap between any two input strands to give a single strand which is output. 4 Slide 5: Need For Better Resource Efficient MP’s 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.
Many have predicted that Moore's Law will soon reach its end, because of the physical speed and miniaturization limitations of silicon microprocessors. 5 Dense Information Storage : Dense Information Storage 6 This image shows 1 gram of DNA on a CD. The CD can hold 800 MB of data.
1 gram of DNA can hold about 1x1014 MB of data.
The number of CDs required to hold this amount of information, lined up edge to edge, would circle the Earth 375 times, and would take 163,000 centuries to listen to. How enormous is the parallelism? : How enormous is the parallelism? 7 The main characteristic of DNA computers is parallel processing.
Parallel processing means the simultaneous solving of a problem by several means or resources.
A test tube of DNA can contain trillions of strands. Each operation on a test tube of DNA is carried out on all strands in the tube in parallel !
Check this out……. We Typically use How extraordinary is the energy efficiency? : How extraordinary is the energy efficiency? 8 Modern scientific tests and studies have revealed that a DNA computer was running
2 x 1019 operations per joule which is very much better than our present day computers. Slide 9: How DNA Computation Works? There is no better way to understand how something works than by illustrative example.
Here is presented a directed Hamiltonian Path problem, and solved using the DNA methods demonstrated by Adleman-the inventor of DNA computers.
Adleman, a computer scientist University of Southern California, was the first to build a test tube DNA computer. 9 Slide 10: A hamiltonian path in a graph is a path visiting each node only once, starting and ending at a given locations 10 Slide 11: TSP: A salesman must go from the city A to the city Z, visiting other cities in the meantime. Some of the cities are linked by plane. Is it any path from A to Z only visiting each city once?
A=Atlanta , Z=Detroit-YES
A=Boston ,Z=Chicago- NO 11 Slide 12: Code each city (node) as an 8 unit DNA string
Code each permitted link with 8 unit DNA strings
Generate random paths between N cities (exponential)
Identify the paths starting at A and ending at Z
Keep only the correct paths (size, hamiltonian) An example : the Traveling Salesman Problem 12 Slide 13: Atlanta – Boston:
R: (ACTGGGCT) Solution A+B+C+D:
ACTTGCAGTCGGACTGGGCTATGTCCGAGCAA Hybridization and ligation between city molecules and intercity link molecules Coding the paths 13 Slide 14: 1.Identify the paths starting at A and ending at Z
PCR for identifying sequences starting with the last nucleotides of A and ending at the first nucleotides of Z
2. Keep only the paths with N cities (N=number of cities)
3. Keep only those paths with all of the cities (once)
Antibody bead separation with each vertex (city) Filter the correct solutions 14 Slide 15: Experimental Conclusions A Hamiltonian path problem is a very complex problem because with each variable added the computational complexity increases several times.
From the above experiment one can deduce that DNA can be used to solve complex mathematical problems.
In the experiment the problem was coded into the DNA structure and hence it can be treated as software.
The enzymes and chemicals which operated on this DNA structure during reactions to modify it for obtaining possible answers can be viewed as hardware. 15 Slide 16: Elimination Of Unwanted Results There are 2 types of methods to do the above process:
2.Gel Electrophorosis. 16 Slide 17: Fluoroscence Spectrum Two possible outputs in the solution :-
If oligonucleotide present output = “1”.
If not present output = “0”.
Detection of output:
Beam of electrons of = 480 nm sent in
If cleavage occurs donor emits fluorescent
radiation on a wavelength of = 520 nm
resulting in peak emission.
Hence output = “1”.
If cleavage doesn’t occur majority of the
emission of donor is absorbed.
No peak in emission. Hence output = “0”. 17 Slide 18: This is the second method.
DNA is a charged molecule. Consequently they move on application of external electric field.
In a gel, DNA of various sizes move with different speeds and finally segregate into different bands.
Bands coloured with radioactive dye for visibility.
Length of the new strand formed by chemical combination of two inputs can be precisely measured. Thus providing DNA computer’s answer.eg: A final DNA sequence as long as the input strands linked together indicates an AND operation.
Output can also be read by adding labeled strands to a DNA chip
consisting of hundreds of squares containing known strands of DNA.
Output DNA would bind to the strand in the square containing its
complementary DNA sequence. Gel Electrophorosis 18 STEGANOGRAPHY : STEGANOGRAPHY Simple code to convert messages into combination of 4 bases of which DNA is made of.
Creation of DNA with short marker sequence at each end.
DNA strands mixed with other DNA strands of similar length.
Dried on a paper and cut into tiny dots. 19 Steganography contd. : Steganography contd. Deciphering requires knowledge of marker sequence.
Polymerase chain reaction to multiply only that DNA which contains message.
Sequencing of DNA gives the original message.
In other words secret messages can be written in “Code of Life”. 20 Slide 21: Cryptography RSA and DES are the two algorithms used in Cryptography. Out of these, DES has been broken using DNA computers.
Tremendous parallel processing and enormous data storage capabilities are the key to breaking cryptographic algorithm.
Generate all possible 64 bit keys(DES) using DNA memory strand.For each of the 264 possible keys, compute the ciphertext using the current key.
Compare the given ciphertext with all the ciphertext generated .
Actual key is the one for which the two ciphertext match.
DNA can be used for making cryptographic system based on “one-time DNA pads”. 21 Slide 22: Limitations Poor at solving simple mathematical problems.
Requires human assistance.
Replicate in uncontrolled way.
Application softwares cannot be run.
DNA has a tendency to decay , hence cannot be kept in labs for a long time. 22 Slide 23: Conclusion DNA computer has many advantages over today’s silicon based computer in terms of computational speed, compactness, memory size etc .
This has a great potential to replace present day processors.
However, there are a few areas in which developmental activities are to be taken up for research. 23 THE FUTURE! : THE FUTURE! 24 Algorithm used by Adleman for the traveling salesman problem was simple. As technology becomes more refined, more efficient algorithms may be discovered.
DNA Manipulation technology has rapidly improved in recent years, and future advances may make DNA computers more efficient.
The University of Wisconsin is experimenting with chip-based DNA computers.
DNA computers are unlikely to feature word processing, emailing and solitaire programs.
Instead, their powerful computing power will be used for areas of encryption, genetic programming, language systems, and algorithms or by airlines wanting to map more efficient routes. Hence better applicable in only some promising areas. THANK YOU! : THANK YOU! 25 It will take years to develop a practical, workable DNA computer.
But…Let’s all hope that this DREAM comes true!!! References : References The papers in this volume were presented at the 6th International Meeting on
DNA Based Computers, organized by the Leiden Cewnter for Natural Compu-
ting and held from June 13 to June 17, 2000 at The Lorenz Center, University
of Leiden, Leiden, The Netherlands. 26 FOR MORE INFO... http://www.scribd.com