Dna Computing

Technical Seminar Presentation 2004

DNA COMPUTING Technical Seminar Report On

“DNA COMPUTING” Under the Guidance of

Mr. S.B Neelamani Submitted by Amit Kumar Mahapatra

CS200117108

Presented by - Amit Kumar Mahapatra CS200117108 [1]

Technical Seminar Presentation 2004

DNA COMPUTING Introduction Double-stranded molecule twisted into a helix Each strand, comprised of a sugar-phosphate backbone and attached bases, is connected to a complementary strand by non -covalent hydrogen bonding between paired bases Bases are: adenine (A)

guanine (G).

thymine (T)

cytosine (C)

A and T are connected by two hydrogen bonds. G and C are connected by three hydrogen bonds Presented by - Amit Kumar Mahapatra CS200117108 [2]

Technical Seminar Presentation 2004

DNA COMPUTING DNA As Computing Machine A DNA-based finite automaton computes via repeated cycles of self assembly and processing. DNA molecules serve as input, output, and software, and the hardware consists of DNA restriction and ligation Enzymes Using ATP as fuel The reversible self-assembly is driven by hybridization energy between input/software complementary sticky ends, followed by an irreversible processing step i.e. an irreversible software-directed cleavage (hydrolysis of the Input DNA backbone) of the input molecule, which drives the computation forward by increasing entropy and releasing heat and hence does not require ATP or heating. Presented by - Amit Kumar Mahapatra CS200117108 [3]

Technical Seminar Presentation 2004

DNA COMPUTING Continued… The cleavage uses the restriction enzyme FokI, which serves as the hardware, to operate on a non covalent software/input hybrid. This automaton use a fixed amount of software and hardware molecules to process any input molecule of any length without external energy supply. This automaton demonstrate 3× 1012 automata per µl 10 6 . 6 × 10 performing transitions per second per µl 29 dissipating about 5 × 10 W/µl as heat .

Presented by - Amit Kumar Mahapatra CS200117108 [4]

Technical Seminar Presentation 2004

DNA COMPUTING Energy Dissipation Calculation  A computation is a series of single symbol cleavages, which occur sequentially for each input molecule  if α i (t ) = the number of moles of each intermediate at a time t then n β i (t ) = ∑ α j (t ) j = i +1

Where β i (t ) = the number of moles of each cleaved symbol α i (t ) average energy dissipation between time point’s t1 and t2 is where V is the reaction volume. The ∆G has the units of J/mole

α i and β i = the average number of moles of each intermediate Presented by - Amit Kumar Mahapatra CS200117108 [5]

Technical Seminar Presentation 2004

DNA COMPUTING State Machines and Finite Automata A finite automaton is a unidirectional read-only Turing machine. Its input is a finite string of symbols. It is initially positioned on the leftmost input symbol in a default initial state, and in each transition moves one symbol to the right, possibly changing its internal state. Its software consists of transition rules, each specifying a next state based on the current state and current symbol. A computation terminates after the last input symbol is processed, the final state being its ‘‘output.’’ An automaton accepts an input if there is a computation with this input that ends in an accepting final state Presented by - Amit Kumar Mahapatra CS200117108 [6]

Technical Seminar Presentation 2004

DNA COMPUTING Molecular Finite Automaton Encoding of a, b, and terminator (sense strands) and the <state, symbol> Interpretation of exposed 4-nt sticky ends, the leftmost representing the current symbol and the state S1 ,similarly the rightmost for S0 (fig : A). Hardware: The FokI restriction enzyme, which recognizes the sequence GGATG and cleaves 9 and 13 nt apart (fig :B)

Software: Each DNA molecule realizes a different transition rule by detecting a current state and symbol and determining a next state. It consists of a<state, symbol> Detector (yellow), a FokI recognition site (blue), and a spacer (gray) of variable length that determines the FokI cleavage site inside the next symbol, which in turn defines the next state. Presented by - Amit Kumar Mahapatra CS200117108 [7]

Technical Seminar Presentation 2004

DNA COMPUTING

Presented by - Amit Kumar Mahapatra CS200117108 [8]

Technical Seminar Presentation 2004

DNA COMPUTING How it computes ??? Double-stranded DNA molecules with sticky ends realize both the software (Fig. C) and the input (Fig. D) The computation proceeds via a cascade of transition cycles, each cleaving and scattering one input symbol, Both hardware and software molecules are recycled Each computational step cleaves and scatters one input symbol. In the core computational step, the software molecule used in one step is not consumed as it dissociates spontaneously from the cleaved input symbol (Fig. E), rendering it reusable for subsequent transitions. The computation proceeds until no software molecule matches the state-symbol pair encoded by the exposed sticky end or until the special terminator symbol is cleaved Presented by - Amit Kumar Mahapatra CS200117108 [9]

Technical Seminar Presentation 2004

DNA COMPUTING Advantages of DNA Computers  Parallelism  Gigantic Memory Capacity

information density =1 bit per cubic nanometer data density = 18 Megabits per inch If assumed one base per square nanometer, the data density ≥ one million Gigabits per square inch but data density of a typical high performance hard driver, which is about 7 gigabits per square inch

 Low Power Dissipation  Clean, Cheap and Available

clean because people do not use any harmful material to produce it and also no pollution generates cheap and available because you can easily find DNA from nature while it’s not necessary to exploit mines

Presented by - Amit Kumar Mahapatra CS200117108 [10]

Technical Seminar Presentation 2004

DNA COMPUTING Disadvantages  Occasionally Slow  Hydrolysis The DNA molecules can fracture. Over the six months you're computing your DNA system is gradually turning to water

 Information Untransmittable

Current DNA algorithms compute successfully without passing any information from one processor to the next in a multiprocessor connection-bus

 Reliability Problems Errors in DNA Computers happen due to many factors Annealing (or hybridization) Errors while combine with the proper DNA complements Misincorporation errors while synthesizing the copies of the DNA strands in Polymerase Chain Reaction (PCR)

Presented by - Amit Kumar Mahapatra CS200117108 [11]

Technical Seminar Presentation 2004

DNA COMPUTING

Application of DNA Based Computation Massively Parallel Processing Solving NP-Complete and Hard Computational Problems Storage and Associative Memory DNA2DNA Applications Implications to Biology, Chemistry, and Medicine

Presented by - Amit Kumar Mahapatra CS200117108 [12]

Technical Seminar Presentation 2004

DNA COMPUTING Solution to Hamiltonian path problem The Hamilton path problem —commonly known as the traveling salesman problem —is a hard NP problem If there are N cities then , there are N! /2 possible paths and the goal is to find a path from the start city to the end city going through every city only once

STEP 1: Represent each city by a single DNA strand containing 20 randomly chosen amino acid bases STEP 2: Represent the route between any two cities by a single DNA strand where the 1st 10 amino acid bases are the complementary bases to the last 10 bases in City 1 and the 2nd 10 bases are the complementary bases to the first 10 bases in City 2. Presented by - Amit Kumar Mahapatra CS200117108 [13]

Technical Seminar Presentation 2004

DNA COMPUTING Continued…

STEP 3: Millions of stands of DNA representing every city and every possible route between any two cities are placed in a test tube where the strands combine. The end result is a large number of long strings of variable lengths formed by the strands combining. To determine the solution: Look only for strings that have City 1 at one end and City 7 at the other Among these strands look for only the strings that had seven cities Among what was left, look for a string with seven different cities and that is the solution Presented by - Amit Kumar Mahapatra CS200117108 [14]

Technical Seminar Presentation 2004

DNA COMPUTING Conclusion

I have described here: What is a DNA and how it is helpful in computing? What is a molecular finite automata and how it computes? What are the advantages and disadvantages of DNA computing? What are the applications and how it is helpful in solving the Hamiltonian path problem? But what ever I have given that is just a bird’s eye vision to this evolving computational field and I hope this paper will inspire readers to do further research in for removing the drawbacks like Self-assembly problems, Hydrolysis problems Stability problems etc. Presented by - Amit Kumar Mahapatra CS200117108 [15]

Technical Seminar Presentation 2004

DNA COMPUTING

Thank You !!!

Presented by - Amit Kumar Mahapatra CS200117108 [16]