DNA Self-AssemblySelf-AssemblySelf-Assembly & ComputationTile Assembly ModelGrid of unit square locationsDirections: d D = {N,E,S,W}Bond types: σ ΣTile types: t = (σN, σΕ, σS, σW) Σ4Tile (instance) t = (t, (i, j)) TZ2Helper functionsHelper functions (example)ConfigurationStrength functions (definition)Strength functions (example)Strength function propertiesTile system T = (T, ts, g, τ)Self-Assembly (definition)Self-Assembly (example)Transitive ClosureAssemblies for a tile system TThreshold τExample of T = (T, ts, g, τ)What does it assemble to?Slide 24Slide 25Slide 26Shape scalingShape equivalenceShape equivalence (example)Equivalence classTile complexityTile complexity (examples)Tile complexity (“S”)Tile complexity (“U”)Slide 35Binary CounterSlide 37Slide 38Slide 39Slide 40Time to flip?Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Variant of Sierpinski TriangleCompute the tile complexity?Turing MachineKolmogorov ComplexityComplexity theoremProof for first partSize of <T> = <(T, ts, g, τ)>Proof (cont)Compute the tile complexity? (v2)DNA Self-AssemblyThe complexity ofself-assembled shapesSelf-Assembly“The process by which an organized structure can spontaneously form from simple parts”Tile Assembly Model2-D self-assembly of square units called tiles.Promising applicationsNanofabricationSelf-Assembly & ComputationSelf-assembled “shape” = Output of computational process.We are interested in shape complexity (defined later on):Kolmogorov ComplexityTile ComplexityTile Assembly ModelGrid of unit square locationsi Zj Z(i, j)Directions: d D = {N,E,S,W}i Zj ZNSEWN (i, j) = (i, j+1)W (i, j) = (i-1, j)S (i, j) = (i, j-1)E (i, j) = (i+1, j)N = S-1, S = N-1W = E-1, E = W-1Bond types: σ ΣA bond type describes a ‘side’ of a tile (in terms of interaction with adjacent).Special bond type for no interaction: σ1 : σ2 : σ3 :null:Tile types: t = (σN, σΕ, σS, σW) Σ4Defined by its four bondsSpecial tile:t1 = (σ1, null, σ1, null) =t2 = (null, null, σ2, σ3) =empty = (null, null, null, null)t TTile (instance) t = (t, (i, j)) TZ2A tile t is defined by its type t and its position (i, j) in the grid.jExample:t = (t2, (2, 2))u = (t2, (3, 1))v = (t1, (1, 1))tuviHelper functionsLet t = (t, (i, j)) = ((σN, σE, σS, σW), (i, j))type(t) = tpos(t) = (i, j)bondd(t) = bondd(t) = σdadj(t,u) = true if dD: pos(t) = d(pos(u))Helper functions (example)type(t) = t2, pos(t) = (2, 2), bondS(t) = σ2S(W(pos(t)) = pos(v) = (1,1)jtuvt = (t2, (2, 2))u = (t2, (3, 1))v = (t1, (1, 1))σ1 : σ2 : σ3 :iConfigurationA configuration is a set of tiles, with exactly one tile in every location (i, j)For any configuration A, notation A(i, j) indicates the tile at location (i, j)Practically, specify a set of non-empty tiles; all other tiles are implicitly empty.Strength functions (definition)Bond strength function: g(σ, σ´) : Σ2 → ZDefined for all pairs of bonds (including null)Tile strength function: Γ(t, u)Defined for adjacent tiles t and uEquals to g(σ, σ´) where σ and σ´ are the bond types of the adjacent sides of t and u respectivelyStrength functions (example)σ1σ2σ3nullσ1σ2σ3null 1 0 0 0 0 7 0 0 0 0 2 0 0 0 0 0Example of gt uvΓ(t, u) = g(σ1, σ1) = 1Γ(u, v) = g(σ2, σ2) = 7Formally:otherwise0,d direction in u)adj(t, if (u)),bond(t),g(bondu)Γ(t,dd1Strength function propertiesg is symmetricg(σ, null) = 0g is non-negativeg is diagonalDiagonal means that only matching bond types can interact!Tile system T = (T, ts, g, τ) A tile system T is defined by:A set Τ of tile typesA seed tile ts, with type(ts) TA strength function gA threshold τt1t2 . . .Self-Assembly (definition)Self assembly is defined by a relation between configurationsSuppose A and B are identical configs, except for t, which exists in B but not in A:A(pos(t)) = empty, B(pos(t)) = tSelf assembly:A→B if ΣdDΓ(t, A(d(pos(t)))) ≥ τSelf-Assembly (example)σ1σ2σ3nullσ1σ2σ3null 1 0 0 0 0 7 0 0 0 0 2 0 0 0 0 0Contents of gxyx tyConfiguration A Configuration BA→B only if Γ(t,x) + Γ(t,y) = 1 + 7 ≥ τTransitive ClosureThe reflexive transitive closure of → is denoted as . (That is, we say that A B if we can keep adding tiles to A and reach B: A → A2 → A3 → ... → B).We are interested in self-assemblies from a single seed tile ts!Assemblies for a tile system TProd(T) = {A, such that {ts} A)All the configurations reachable from ts in T.Term(T) = {A Prod(T), B≠A: A B}All the terminal assemblies reachable from tsT uniquely produces A if Term(T) = {A}.Threshold τA common choice is τ = 2, where the strength function ranges over {0, 1, 2}.Systems with τ = 1 and a strength function ranging over {0, 1} are rather limited.Example of T = (T, ts, g, τ) Set T of tile types:ts = (ts, (2, 4))g = I = diag{1}τ = 1N E S Wts- - - σ1t1- σ1- σ2t2- σ2σ3-t3σ3- σ4-t4σ4σ5- -t5- σ6- σ5t6- - σ7σ6t7σ7- σ8-t8σ8- - σ9t9- σ9- σ10t10- σ10- -tsσ1t1σ2σ1t2σ2σ3What does it assemble to?N E S Wts- - - σ1t1- σ1- σ2t2- σ2σ3-t3σ3- σ4-t4σ4σ5- -t5- σ6- σ5t6- - σ7σ6t7σ7- σ8-t8σ8- - σ9t9- σ9- σ10t10- σ10- -tsσ1What does it assemble to?N E S Wts- - - σ1t1- σ1- σ2t2- σ2σ3-t3σ3- σ4-t4σ4σ5- -t5- σ6- σ5t6- - σ7σ6t7σ7- σ8-t8σ8- - σ9t9- σ9- σ10t10- σ10- -tsσ1t1σ2σ1What does it assemble to?N E S Wts- - - σ1t1- σ1- σ2t2- σ2σ3-t3σ3- σ4-t4σ4σ5- -t5- σ6- σ5t6- - σ7σ6t7σ7- σ8-t8σ8- - σ9t9- σ9- σ10t10- σ10- -tsσ1t1σ2σ1t2σ2σ3What does it assemble to?N E S Wts- - - σ1t1- σ1- σ2t2- σ2σ3-t3σ3- σ4-t4σ4σ5- -t5- σ6- σ5t6- - σ7σ6t7σ7- σ8-t8σ8- - σ9t9- σ9- σ10t10- σ10- -Shape scalingCoordinated* shape of assembly A:SA = {(i, j) such that A(i, j) ≠ empty}(This is a single connected component)For a set of locations S, and cZ+, define a c-scaling of S:Sc = {(i, j) such that }(This is a magnification of S by a factor of c) Sj/c,i/c *shape within a fixed coordinate systemShape
View Full Document
Unlocking...