Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Robust Self-Assembly of DNA Eduardo AbeliukDept. of Electrical EngineeringStanford UniversityNovember 30, 2006Agenda for todayRobust Self-Assembly: definitions and motivationBasic assembly model and examples“Complexity of Self-Assembled Shapes” D. Soloveichik, E.Winfree. DNA Computers 10, LNCS v.3384, 2005“Error Free Self-Assembly using Error Prone Tiles”, H. Chen, A. Goel. 10th Int. Meeting on DNA Based Computers, 2004. “Self-Healing Tile Sets” E. Winfree, Nanotechnolgy: Science and computation, p.55-78, 2006Self-Assembly TheorySelf-assembly: no precise general definitionBut roughly speaking:“ process by which an organized structure can spontaneously form from simpler parts”ProgrammingComplexityFault-toleranceSelf-healingSelf-reproduction and evolutionSchulman R., Winfree E., “Self-replication and evolution of DNA crystals” 2005.Self-assemblyAlready present in nature Inside cellsRobust self-assembly of organisms over 18 orders of magnitude in volume!Bottom-up fabrication of complex structures: Arbitrary shapes can be self-assembled (2D)Enabled by DNA nanotechnologyRothemund PWK, “Folding DNA to create nanoscale shapes and patterns”, Nature 2006Rothemund PWK, “Folding DNA to create nanoscale shapes and patterns”, Nature 2006Rothemund PWK, “Folding DNA to create nanoscale shapes and patterns”, Nature 2006Another MotivationCompute “along the way”The self-assembly of a crystal can resemble a program that leaves the traces of its operations embedded in it.The assembly of a 2D crystal can simulate a universal Turing machine!input:01001101011output:01001101011input:output:Robust self-assembly of DNADo we need robustness?"In theory, there is no difference between theory and practice. But, in practice, there is." -Jan L.A. van de SnepscheutComputing with DNA, and not transistors??DNA Current computerInformation density (bits/nm3)~1 ~10-11Parallelism (operations/sec)~1018~1012Energy expediture (J/operation)~10-19~10-9The tile assembly modelInfinite lattice:Z x ZEvery position in the grid has a relative position associated:N(i,j)=(i,j+1) S(i,j)=(i,j-1)E(i,j)=(i+1,j)W(i,j)=(i-1,j) (i,j)NW ESOur fundamental unit is a square tile with labelled edges, or bond types. We consider a set of bond types . (e.g., ={A,B,C,D,null}) A reflection or rotation gives a different tile.So a tile type is a quadruple:and we have unlimited supply of themTiles types with identical edges can pair with each other.We will represent tile types with different colors. All tile types for the set T. Bond types and Tile TypesWSNE4),,,(~WESNtAB CDDA CDBA BDAB CDDA CDBA BDAB CDBA BDTilesA tile is a pair , i.e., it corresponds to a tile with certain tile type located in a certain position in our gridA configuration is a set of tiles, such that there is exactly one tile in every location2)),(,~( ZTjit Configuration 1Configuration 2Interaction between tilesA strength function defines the interactions between two tiles.We say a tile t1 interacts with its neighbor t2 with strengthUsually, only diagonal strength functions are considered, and the range of g is {0,1,2}:g)',(),(21gtt A B CDBA BCA C CD g A B C D null A 1 0 0 0 0 B 0 1 0 0 0 C 0 0 2 0 0 D 0 0 0 1 0null 0 0 0 0 0The tile assembly model (aTAM)A tile system is a quadruple i.e., it consist of a set of tile typesa seed tilea strength functiona binding threshold or “temperature”Self-assembly is defined as a relation between configurations:),,,(gtTsA BBATExample of Tile SystemsSierpinski tile set7 types of tiles: 1 seed, 2 boundary (input) tiles, 4 rule tilesSeedBoundarytiles“Rule” tilesSierpinski tile setTilesSierpinski tile setBinary counterTyle types:Binary counterBegin with seedContinue with boundarytiles Then “rule” tilesCount upwards (binary) = 1 = 0Tiles15432768Square self-assemblyExample for 9x9 square41 Tile typesMore on assembliesTile additions are non-deterministic1. Several locations for adding tiles2. Several possible tiles could be added in one spotDefininitions: input sides propagation (output) sidesterminal sides.terminalinputoutputFrom binary counterFinal Assembly TheoremDefinition: an assembly is locally deterministic if:every tile addition has strength 2.if tile at (i,j) and all tiles touching its propagation sides are removed, then there is only one tile type that can be added at (i,j)Theorem: “If a tile set has one locally determinist assembly sequence, then the same final assembly is produced regardless of order of tile additions”.From theory to practice (biology)Tiles are “do-able” in practiceDNA Nano-technologyWinfree, E. et at. Design and self-assembly of two dimensional. DNA crystals. 1998.More on the technologyMore tiles from DNAHao Yan et al. “4x4 DNA Tile and Lattices: Characterization, Self-Assembly and Metallization of a Novel DNA Nanostructure Motif” 2003.Road ahead…1. First paper (complexity):Ties (Kolmogorov) computation of a shape with complexity of tile system that self-assembles itNote: the former has nothing to do with self-assemblyRobust self-assembly2. Second paper (fault-tolerance): how to avoid nucleation and growth errors3. Third paper (self-healing): how to avoid gross damageFirst paperD. Soloveichik, E.Winfree, “Complexity of Self-Assembled Shapes”Coordinated shapesLet S be a finite set of locations in Z2. S is a coordinated shape if it’s connectedCoordinated shape This is notTransforming coordinated shapesScalings:Translations:ShapesScale and translation equivalence relations on coordinated shapes define class of shapesS~coordinated shape 1
View Full Document
Unlocking...