DNA Computing by Self AssemblySelf Assembly of a BoxInformation and AlgorithmsSelf Assembly ModelPurposesPrecursorsDNA ComputingHamiltonian PathSteps of processTiling TheoryDNA NanotechnologyDX Molecule = Wang tileSimplified Tile Assembly ModelBinary CounterExperimental DemonstrationsXOR PracticeXORingSierpinski TriangleSample Tile SolutionApplication 1: Solve NP hard problemsApply self assemblyCurrent resultsApplication 2: Programmable NanofabricationNanocircuitsDNA Circuit PictureSummary – AchievementsSummary – Current ProblemsYet more problemsFuture QuestionsFinal ThoughtsMore thoughtsInterested?DNA Computing by Self AssemblyErik Winfree, CaltechSelf Assembly of a BoxInformation and AlgorithmsElectronic microprocessors control electro-mechanical devicesBiochemical circuits control molecular/chemical eventsGeneral Goal: design biochemical algorithms/circuits that are programmable and can perform functionsSelf Assembly ModelModel we will investigate: molecular self assembly of heterogeneous crystalsIdea: use periodic order of crystals to perform arbitrarily complex computation What are purposes of self assembly?2 main schools of thoughtPurposes1. Use massive parallelism of chemistry and lots of DNA at a time to solve difficult combinatorial optimization problems, such as SAT/TSP2. Use self assembly algorithms to fabricate exact shapes / circuits/ patterns etc..PrecursorsIdea of self assembly arose from 3 ideas1. DNA computing (Adleman 1994)2. Tiling theory (Grun. & Shep. 1986)3. DNA nanotechnology (Seeman 1982)DNA ComputingAdleman 1994 – Solved 6 node Hamiltonian Path Problem Nodes labeled with random 20mer Edge(u, v) = last 10 BP of u + first 10 BP of vHamiltonian PathUsed DNA hybridization to generate random paths through graphAdded programmable binding to impose conditions (start city, end city, num cities, no repeats..)1st meaningful computation by DNAHeralded as a landmark achievementSteps of processGenerate random paths (DNA molecules) through graphUse PCR to amplify all paths that start at first city and end at last city (use primers)Test if path contains city 1. Amplify paths that pass test. Repeat tests for cities 2 through n.If anything left, return YES. Else return NO.Tiling TheoryTiling – arrangement of basic shapes to cover infinite planeWang 1963 – Showed infinite num of square tiles with 4 colored sides can create Turing machine historyWang Tiles are very powerful. Use DNA molecules to simulate Wang tiles in self assemblyDNA NanotechnologySeeman 1982 – use DNA as a building block for nanostructuresBlock: Four armed DNA double-crossover molecules (DX) Label 4 arms of DX molecules with labels like Wang tilesDX Molecule = Wang tileAdjacent tiles = sequences at sticky ends of 2 molecules go togetherUpper Right A = CATACLower Left B = GTATGSimplified Tile Assembly ModelGiven a set of possible tiles and possible bonds4 sides of tile have bonds, bond has strength (0, 1,2)2 tiles can bond together if their bonds fit, and if total strength (sums of bond strengths on common sides) is > thresholdGrowth starts with a seed tileBinary CounterUsing 3 border tiles, 2 ‘0-bit’ tiles, 2 ‘1-bit’ tiles, can simulate a binary counterPower: only 7 tiles requiredExperimental Demonstrations1d array – Adleman DNA Computing19942d array – Winfree 1998 3d array – Open Next: Example of Winfree constructionXOR PracticeEveryone try this out.Start with a 1 in a sea of 0’s. To generate next row, each tile checks its two neighbors, performs XOR and places the result below it in the next rowXOR 00 = 0 11=001 = 1 10=1XORing000000000010000000000000000000101000000000000000001000100000000 000000010101010000000000000100000001000000000001010000010100000000010001000100010000000101010101010101000001000000000000000100……..Sierpinski Triangle1st 2d process to be experimentally demonstrated = Sierpinski GasketBest result so far: 8 by 16 error-free trianglePoor results due to 1-10% tile binding errorSample Tile SolutionSlight variant of Sierpinski TriangleApplication 1: Solve NP hard problemsNP-complete problems: exponential number of solutions, hard to find correct solution, but easy to verifyIdea: Chemistry can generate all possible solutions and filter solutions quicklyHack: Push exponential dimension of problem into volume of DNA needed1 mL DNA = 260 bits of informationApply self assemblyLet massive parallelism solve problemIn self assembly, generate input as initial set of tilesSee if Yes or No tile is produced at endCurrent resultsProblems solved –Hamiltonian Path, Satisfiability, etc..Assuming no errors, 40-variable SAT needs 30 mL DNA and several hours1012 operations/second, inferior to computersWinfree: No “low hanging fruit” for self assembly hereApplication 2: Programmable NanofabricationFabricate molecular electronic circuitsCurrent technology hitting the limit soonSolution: create molecular structures like carbon nanotubes.How to arrange tiny chemical components into fixed patterns?Nanocircuits Solution: Use self assembly to create molecular components Small pieces such as NAND/OR gates can be createdHard to create large microprocessorsSelf assembly good to make circuits that have “concise” descriptions, eg recursive formulationsDNA Circuit PictureRAM Demultiplexer2 bands = earlier bit counter exampleSummary – AchievementsRobust, readily programmableDozens of crystals have been successfully used as DNA tilesSelf assembly has concrete experimental results, unlike other molecular computing technologiesSummary – Current ProblemsCurrent DNA tiles distorted, 1% positioning error in experiments.Size of tile is limited – all crystals < 10 microns. 1 – 10 % step error. eg tiles bond incorrectly quite often. Very big problem.=> New model: error correcting tiles in self assemblyYet more problemsUndesired nucleation – self assembly starts by itselfProblem occurs because biological system starts when it wants to minimize energySolution: Have programmable control of nucleation. Add energy barriers to force assembly to start with seed tile.Future QuestionsNatural question: What shapes can be made by self assembly?Has parallels to Computability / Chomsky Language TheoryMinimum number of steps to make a shape?Minimum number of tiles to make shape?Final ThoughtsAlthough bio systems
View Full Document
Unlocking...