DNA COMPUTINGOutline of LectureIntroductionUniqueness of DNADense Information StorageHow Dense is the Information Storage?How enormous is the parallelism?How extraordinary is the energy efficiency?A Little More………Biochemistry BasicsExtractionAnnealingPolymerase Chain ReactionGel ElectrophoresisHow to fish for known molecules?Adleman’s solution of the Hamiltonian Directed Path Problem(HDPP).The ProblemExampleWhy not brute force algorithm?Adleman’s ExperimentAlgorithm(non-deterministic)Step 1.Random Path Generation.Slide 23Step1. Random Path Generation.Slide 25Slide 26Step1.Random Path GenerationSlide 28Examples of random paths formedFormation of Paths from Edges and compliments of verticesSlide 31Step 2 “keep only those that start at s and end at t.”Step 3 “keep only those that visit exactly n vertices”Step 3 “keep only those that visit exactly n vertices”Step 4 “keep only those that visit each vertex at least once”Slide 36Step 5:Obtaining the AnswerSlide 38Slide 39Discover magazine published an article in comic strip format about Leonard Adleman's discovery of DNA computation. Not only entertaining, but also the most understandable explanation of molecular computation I have Ever seen.Recap of HDPPDANGEROUS ERRORSDanger of Errors possibleThe operation of ExtractionUndesired AnnealingsLIMITATIONSDNA Vs Electronic computersSize restrictionsError RestrictionsHidden factors affecting complexitySome more……….THE FUTURE!THANK YOU!ReferencesDNA COMPUTINGDeepthi Bollu CSE 497:Computational issues in Molecular BiologyProfessor- Dr. LoprestiApril 13, 2004Deepthi Bollu 2Outline of LectureIntroduction.Biochemistry basics.Adleman’s Hamiltonian path problem.Danger of errors.Limitations.Deepthi Bollu 3IntroductionEver wondered where we would find the new material needed to build the next generation of microprocessors????HUMAN BODY (including yours!)…….DNA computing.“Computation using DNA” but not “computation on DNA”Initiated in 1994 by an article written by Dr. Adleman on solving HDPP using DNA.Deepthi Bollu 4Uniqueness of DNAWhy is DNA a Unique Computational Element???Extremely dense information storage.Enormous parallelism.Extraordinary energy efficiency.Deepthi Bollu 5Dense Information StorageThis image shows 1 gram of DNA on a CD. The CD can hold 800 MB of data. The 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.Deepthi Bollu 6How Dense is the Information Storage?with bases spaced at 0.35 nm along DNA, data density is over a million Gbits/inch compared to 7 Gbits/inch in typical high performance HDD.Check this out………..Deepthi Bollu 7How enormous is the parallelism?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 useDeepthi Bollu 8How extraordinary is the energy efficiency?Adleman figured his computer was running 2 x 1019 operations per joule.Deepthi Bollu 9A Little More………Basic suite of operations: AND,OR,NOT & NOR in CPU while cutting, linking, pasting, amplifying and many others in DNA.Complementarity makes DNA unique. Ex: in Error correction.Biochemistry BasicsDeepthi Bollu 11Extractiongiven a test tube T and a strand s, it is possible to extract all the strands in T that contain s as a subsequence, and to separate them from those that do not contain it.Formation of DNA strands. Precipitation of more DNA strands in alcoholSpooling the DNA with a metal hook or similar deviceDeepthi Bollu 12Annealing Curves represent single strands of DNA ogilonucleotides. The half arrow head represents the 3’ end of the strand. The dotted lines indicate the hydrogen bonding joining the strands. The hydrogen bonding between two complimentary sequences is weaker than the one that links nucleotides of the same sequence.It is possible to pair(anneal) and separate(melt) two antiparallel and complementary single strands.Deepthi Bollu 13Polymerase Chain ReactionPCR: One way to amplify DNA.PCR alternates between two phases: separate DNA into single strands using heat; convert into double strands using primer and polymerase reaction.PCR rapidly amplifies a single DNA molecule into billions of moleculesDeepthi Bollu 14Gel ElectrophoresisUsed to measure the length of a DNA molecule.Based on the fact that DNA molecules are –ve ly charged. Gel ElectrophoresisDeepthi Bollu 15How to fish for known molecules?Annealing of complimentary strands can be used for fishing out target molecules.Denature the double stranded molecules.The probe for s molecules would be s.We attach probe to a filter and pour the solution S through it.We get double stranded molecules fixed to filter and the solution S’ resulting from S by removing s molecules.Filter is then denatured and only target molecule remains.Adleman attached probes to magnetic beads.Adleman’s solution of the Hamiltonian Directed Path Problem(HDPP).I believe things like DNA computing will eventuallyI believe things like DNA computing will eventuallylead the way to a “molecular revolution,” which lead the way to a “molecular revolution,” which ultimately will have a very dramatic effect on the ultimately will have a very dramatic effect on the world. – L. Adlemanworld. – L. AdlemanDeepthi Bollu 17The ProblemA directed Graph G=(V,E)|V|=n, |E|=m and two distinguished vertices Vin = s and Vout= t.Verify whether there is a path (s,v1,v2,….,t)which is a sequence of “one-way” edges that begins in Vin and Voutwhose length (in no.of edges) is n-1 and (i.e. enters all vertices.)Whose vertices are all distinct (i.e. enters every vertex exactly once.)A CLASSIC NP-COMPLETE PROBLEM!!!Deepthi Bollu 18Examples 45362tA directed Graph. An st hamiltonian path is (s,2,4,6,3,5,t).Here Vin=s and Vout=t.What happens if some edge ex:24 is removed from the graph??What happens if the designated vertices are changed to Vin = 2 and Vout =4??Deepthi Bollu 19Why not brute force algorithm?Brute force algorithm is to Generate all possible paths with exactly n-1 edgesVerify whether one of them obeys the problem constraints.Problem: How many paths can there be???