[PDF] Strict Self-Assembly of Discrete Sierpinski Triangles

View - Download Strict Self-Assembly of Discrete Sierpinski Triangles

Previous PDF

Next PDF

Strict Self-Assembly of Discrete Sierpinski Triangles

James I. Lathrop

, Jack H. Lutzy, and Scott M. Summers.z

June 28, 2018

Abstract

Winfree (1998) showed that discrete Sierpinski triangles can self-assemble in the Tile Assembly Model.

A striking molecular realization of this self-assembly, using DNA tiles a few nanometers long and verifying

the results by atomic-force microscopy, was achieved by Rothemund, Papadakis, and Winfree (2004).

Precisely speaking, the above self-assemblies tile completely lled-in, two-dimensional regions of the

plane, with labeled subsets of these tiles representing discrete Sierpinski triangles. This paper addresses

the more challenging problem of thestrict self-assemblyof discrete Sierpinski triangles, i.e., the task of

tiling a discrete Sierpinski triangle and nothing else. We rst prove that the standard discrete Sierpinski trianglecannotstrictly self-assemble in the Tile Assembly Model. We then dene thebered Sierpinski triangle, a discrete Sierpinski triangle with the same fractal dimension as the standard one but with thin bers that can carry data, and show that

the bered Sierpinski triangle strictly self-assembles in the Tile Assembly Model. In contrast with the

simple XOR algorithm of the earlier, non-strict self-assemblies, our strict self-assembly algorithm makes

extensive, recursive use of optimal counters, coupled with measured delay and corner-turning operations.

We verify our strict self-assembly using the local determinism method of Soloveichik and Winfree (2007).

1 Introduction

Structures that self-assemble in naturally occurring biological systems are often fractals of low dimension,

by which we mean that they are usefully modeled as fractals and that their fractal dimensions are less

than the dimension of the space or surface that they occupy. The advantages of such fractal geometries for

materials transport, heat exchange, information processing, and robustness imply that structures engineered

by nanoscale self-assembly in the near future will also often be fractals of low dimension. The simplest mathematical model of nanoscale self-assembly is the Tile Assembly Model (TAM), an

extension of Wang tiling [17, 18] that was introduced by Winfree [20] and rened by Rothemund and Winfree

[13, 12]. (See also [1, 11, 16].) This elegant model, which is described in section 2, uses tiles with various

types and strengths of \glue" on their edges as abstractions of molecules adsorbing to a growing structure.

(The tiles are squares in the two-dimensional TAM, which is most widely used, cubes in the three-dimensional

TAM, etc.) Despite the model's deliberate oversimplication of molecular geometry and binding, Winfree

[20] proved that the TAM is computationally universal in two or more dimensions. Self-assembly in the TAM

can thus be directed algorithmically. This paper concerns the self-assembly of fractal structures in the Tile Assembly Model. The typical

test bed for a new research topic involving fractals is the Sierpinski triangle, and this is certainly the case

for fractal self-assembly. Specically, Winfree [20] showed that thestandard discrete Sierpinski triangleS,

Department of Computer Science, Iowa State University, Ames, IA 50011, USA. jil@cs.iastate.edu.

yDepartment of Computer Science, Iowa State University, Ames, IA 50011, USA. lutz@cs.iastate.edu. This author's re-

search was supported in part by National Science Foundation Grants 0344187, 0652569, and 0728806 and in part by Spanish

Government MEC Project TIN 2005-08832-C03-02.

zDepartment of Computer Science, Iowa State University, Ames, IA 50011, USA. summers@cs.iastate.edu. This author's

research was supported in part by NSF-IGERT Training Project in Computational Molecular Biology Grant number DGE-

0504304

1arXiv:0903.1818v1 [cs.DM] 10 Mar 2009

which is illustrated in Figure 1, self-assembles from a set of seven tile types in the Tile Assembly Model.

Formally,Sis a set of points in the discrete Euclidean planeZ2. The obvious and well-known resemblance

betweenSand the Sierpinski triangle inR2that is studied in fractal geometry [8] is a special case of a

general correspondence between \discrete fractals" and \continuous fractals" [19]. Continuous fractals are

typically bounded (in fact, compact) and have intricate structure at arbitrarily small scales, while discrete

fractals likeSare unbounded and have intricate structure at arbitrarily large scales.

A striking molecular realization of Winfree's self-assembly ofSwas reported in 2004. Using DNA double-

crossover molecules (which were rst synthesized in pioneering work of Seeman and his co-workers [15]) to

construct tiles only a few nanometers long, Rothemund, Papadakis and Winfree [14] implemented the molecu-

lar self-assembly ofSwith low enough error rates to achieve correct placement of 100 to 200 tiles, conrmed

by atomic force microscopy (AFM). This gives strong evidence that self-assembly can be algorithmically

directed at the nanoscale.

The abstract and laboratory self-assemblies ofSdescribed above are impressive, but they are not (nor were

they intended or claimed to be) true fractal self-assemblies. Winfree's abstract self-assembly ofSactually tiles

anentire quadrantof the plane in such a way that ve of the seven tile types occupy positions corresponding

to points inS. Similarly, the laboratory self-assemblies tile completely lled-in, two-dimensional regions,

with DNA tiles at positions corresponding to points ofSmarked by inserting hairpin sequences for AFM

contrast. To put the matter guratively, what self-assembles in these assemblies is not the fractalSbut

rather a two-dimensional canvas on whichShas been painted.

In order to achieve the advantages of fractal geometries mentioned in the rst paragraph of this paper, we

need self-assemblies that construct fractal shapesand nothing more. Accordingly, we say that a setFZ2

strictly self-assemblesin the Tile Assembly Model if there is a (nite) tile system that eventually places a

tile on each point ofFand never places a tile on any point of the complement,Z2F. (This condition is dened precisely in section 2.)

The specic topic of this paper is the strict self-assembly of discrete Sierpinski triangles in the Tile

Assembly Model. We present two main results on this topic, one negative and one positive.

Our negative result is that the standard discrete Sierpinski triangleScannotstrictly self-assemble in the

Tile Assembly Model. That is, there is no tile assembly system that places tiles on all the points ofSand

on none of the points ofZ2S. This theorem appears in section 3. The key to its proof is an extension of the theorem of Adleman, Cheng, Goel, Huang, Kempe, Moisset de Espanes, and Rothemund [2] on the number of tile types required for a nite tree to self-assemble from a single seed tile at its root. Our positive result is that a slight modication ofS, thebered Sierpinski triangleTillustrated in

Figure 2, strictly self-assembles in the Tile Assembly Model. Intuitively, the bered Sierpinski triangleT

(dened precisely in section 4) is constructed by following the recursive construction ofSbut also adding

a thinberto the left and bottom edges of each stage in the construction. These bers, which carry data

in an algorithmically directed self-assembly ofT, have thicknesses that are logarithmic in the sizes of the

corresponding stages ofT. This means thatTis visually indistinguishable fromSat suciently large scales.

Mathematically, it implies thatThas the same fractal dimension asS.

Since our strict self-assembly must tile the setT\from within," the algorithm that directs it is perforce

more involved than the simple XOR algorithm that directs Winfree's seven-tile-type, non-strict self-assembly

ofS. Our algorithm, which is described in section 5, makes extensive, recursive use of optimal counters [5],

coupled with measured delay and corner-turning operations. It uses 51 tile types, but these are naturally

partitioned into small functional groups, so that we can use Soloveichik and Winfree's local determinism

method [16] to prove thatTstrictly self-assembles.

2 Preliminaries

2.1 Notation and Terminology

We work in the discrete Euclidean planeZ2=ZZ. We writeU2for the set of allunit vectors, i.e., vectors

of length 1, inZ2. We regard the four elements ofU2as (names of the cardinal)directionsinZ2. 2

We write [X]2for the set of all 2-element subsets of a setX. Allgraphshere are undirected graphs, i.e.,

ordered pairsG= (V;E), whereVis the set ofverticesandE[V]2is the set ofedges. Acutof a graph G= (V;E) is a partitionC= (C0;C1) ofVinto two nonempty, disjoint subsetsC0andC1. Abinding functionon a graphG= (V;E) is a function:E!N. (Intuitively, iffu;vg 2E, then (fu;vg) is the strength with whichuis bound tovbyfu;vgaccording to. Ifis a binding function on a graphG= (V;E) andC= (C0;C1) is a cut ofG, then thebinding strengthofonCis

C=f(e)je2E;e\C06=;;ande\C16=;g:

Thebinding strengthofon the graphGis then

(G) = minfCjCis a cut ofGg: Abinding graphis an ordered tripleG= (V;E;), where (V;E) is a graph andis a binding function on (V;E). If2N, then a binding graphG= (V;E;) is-stableif(V;E). Agrid graphis a graphG= (V;E) in whichVZ2and every edgef~m;~ng 2Ehas the property that ~m~n2U2. Thefull grid graphon a setVZ2is the graphG#

V= (V;E) in whichEcontainsevery

f~m;~ng 2[V]2such that~m~n2U2. We say thatfis apartial functionfrom a setXto a setY, and we writef:X99KY, iff:D!Yfor some setDX. In this case,Dis thedomainoff, and we writeD= domf.

All logarithms here are base-2.

2.2 The Tile Assembly Model

We review the basic ideas of the Tile Assembly Model. Our development largely follows that of [13, 12], but

some of our terminology and notation are specically tailored to our objectives. In particular, our version

of the model only uses nonnegative \glue strengths", and it bestows equal status on nite and innite

assemblies. We emphasize that the results in this section have been known for years, e.g., they appear, with

proofs, in [12]. Denition 1.Atile typeover an alphabet is a functiont:U2!N. We writet= (colt;strt), where col t:U2!, and strt:U2!Nare dened byt(~u) = (colt(~u);strt(~u)) for all~u2U2.

Intuitively, a tile of typetis a unit square. It can be translated but not rotated, so it has a well-dened

\side~u" for each~u2U2. Each side~uof the tile is covered with a \glue" ofcolorcolt(~u) andstrength str t(~u). If tiles of typestandt0are placed with their centers at~mand~m+~u, respectively, where~m2Z2

and~u2U2, then they willbindwith strength strt(~u)[[t(~u) =t0(~u)]] where [[]] is theBooleanvalue of the

statement. Note that this binding strength is 0 unless the adjoining sides have glues of both the same

color and the same strength.

For the remainder of this section, unless otherwise specied,Tis an arbitrary set of tile types, and2N

is the \temperature." Denition 2.A T-congurationis a partial function:Z299KT. Intuitively, a conguration is an assignmentin which a tile of type(~m) has been placed (with its center) at each point~m2dom. The following data structure characterizes how these tiles are bound to one another. Denition 3.Thebinding graph ofaT-conguration:Z299KTis the binding graphG= (V;E;), where (V;E) is the grid graph given byV= dom, andf~m;~ng 2Eif and only if

1.~m~n2Un,

2. col

(~m)(~n~m) = col(~n)(~m~n), and

3. str

(~m)(~n~m)>0. 3

The binding function:E!Z+is given by

(f~m;~ng) = str(~m)(~n~m) for allf~m;~ng 2E.

Denition 4.

1. AT-congurationis-stableif its binding graphGis-stable.

2. A-T-assemblyis aT-conguration that is-stable. We writeATfor the set of all-T-assemblies.

Denition 5.Letand0beT-congurations.

1.is asubcongurationof0, and we writev0, if domdom0and, for all~m2dom,

(~m) =0(~m):

2.0is asingle-tile extensionofifv0and dom0domis a singleton set. In this case, we write

0=+ (~m7!t), wheref~mg= dom0domandt=0(~m).

Note that the expression+ (~m7!t) is only dened when~m2Z2dom. We next dene the \-t-frontier" of a-T-assemblyto be the set of all positions at which a tile of type tcan be \-stably added" to the assembly.

Denition 6.Let2 AT.

1. For eacht2T, the-t-frontierofis the set

t=8 ~m2Z2dom X ~u2U2str t(~u)[[(~m+~u)(~u) =t(~u)]]9

2. The-frontierofis the set

t2T@ t: The following lemma shows that the denition of@tachieves the desired eect. Lemma 2.1.Let2 AT,~m2Z2dom, andt2T. Then+ (~m7!t)2 ATif and only if~m2@t. Notation 1.We write1!;T0(or, whenandTare clear from context,1!0) to indicate that

02 ATand0is a single-tile extension of.

In general, self-assembly occurs with tiles adsorbing nondeterministically and asynchronously to a growing

assembly. We now dene assembly sequences, which are particular \execution traces" of how this might occur.

Denition 7.A-T-assembly sequenceis a sequence~= (ij0i < k) inAT, wherek2Z+[f1gand, for eachiwith 1i+ 1< k,i1!;Ti+1. Note that assembly sequences may be nite or innite in length. Note also that, in any-T-assembly sequence~= (ij0i < k), we haveivjfor all 0ij < k. Denition 8.Theresultof a-T-assembly sequence~= (ij0i < k) is the uniqueT-conguration = res(~) satisfying dom=S

0i It is clear that res(~)2 ATfor every-T-assembly sequence~.

Denition 9.Let;02 AT.

4

1. A-T-assembly sequence fromto0is a-T-assembly sequence~= (ij0i < k) such that

0=and res(~) =0.

2. We write!;T0(or, whenandTare clear from context,!0) to indicate that there exists a

-T-assembly sequence fromto0.

A routine dovetailing argument extends the following observation of [12] to assembly sequences that may

have innite length. Theorem 2.2.The binary relation!;Tis a partial ordering ofAT. Denition 10.An assembly2 ATisterminalif it is a!;T-maximal element ofAT. It is clear that an assemblyis terminal if and only if@=;. We now note that every assembly is!;T-bounded by (i.e., can lead to) a terminal assembly. Lemma 2.3.For each2 AT, there exists02 ATsuch that!;T0and0is terminal.

We now dene tile assembly systems.

Denition 11.

1. Ageneralized tile assembly system(GTAS) is an ordered triple

T= (T;;);

whereTis a set of tile types,2 ATis theseed assembly, and2Nis thetemperature.

2. Atile assembly system(TAS) is a GTAST= (T;;) in which the setsTand domare nite.

Intuitively, a \run" of a GTAST= (T;;) is any-T-assembly sequence~= (ij0i < k) that begins with0=. Accordingly, we dene the following sets.

Denition 12.LetT= (T;;) be a GTAS.

1. Theset of assemblies produced byTis

A[T] =

2 AT !;T

2. Theset of terminal assemblies produced byTis

A [T] =f2 A[T]jis terminalg: Denition 13.A GTAST= (T;;) isdirectedif the partial ordering!;Tdirects the setA[T], i.e., if for each;02 A[T] there exists ^2 A[T] such that!;T^and0!;T^.

We are using the terminology of the mathematical theory of relations here. The reader is cautioned that

the term "directed" has also been used for a dierent, more specialized notion in self-assembly [3].

Directed tile assembly systems are interesting because they are precisely those tile assembly systems that

produce unique terminal assemblies. Theorem 2.4.A GTASTis directed if and only ifjA[T]j= 1. In the present paper, we are primarily interested in the self-assembly of sets. 5

Denition 14.LetT= (T;;) be a GTAS, and letXZ2.

1. The setXweakly self-assemblesinTif there is a setBTsuch that, for all2 A[T],1(B) =X.

2. The setXstrictly self-assemblesinTif, for all2 A[T], dom=X.

Intuitively, a setXweakly self-assembles inTif there is a designated setBof \black" tile types such that every terminal assembly ofT\paints the setX- and only the setX- black". In contrast, a setX strictly self-assembles inTif every terminal assembly ofThas tiles on the setXand only on the setX. Clearly, every set that strictly self-assembles in a GTASTalso weakly self-assembles inT.

We now have the machinery to say what it means for a set in the discrete Euclidean plane to self-assemble

in either the weak or the strict sense.

Denition 15.LetXZ2.

1. The setXweakly self-assemblesif there is a TASTsuch thatXweakly self-assembles inT.

2. The setXstrictly self-assemblesif there is a TASTsuch thatXstrictly self-assembles inT.

Note thatTis required to be a TAS, i.e., nite, in both parts of the above denition.

2.3 Local Determinism

The proof of our second main theorem uses the local determinism method of Soloveichik and Winfree [16],

which we now review. Notation 2.For eachT-conguration, each~m2Z2, and each~u2U2, str (~m;~u) = str(~m)(~u)[[(~m)(~u) =(~m+~u)(~u)]]: (The Boolean value on the right is 0 iff~m; ~m+~ug*dom.) Notation 3.If~= (ij0i < k) is a-T-assembly sequence and~m2Z2, then the~-indexof~mis i ~(~m) = minfi2Nj~m2domig:

Observation 2.5.~m2dom res(~),i~(~m)<1.

Notation 4.If~= (ij0i < k) is a-T-assembly sequence, then, for~m; ~m02Z2, ~m~~m0,i~(~m)< i~(~m0): Denition 16.(Soloveichik and Winfree [16]) Let~= (ij0i < k) be a-T-assembly sequence, and let = res(~). For each location~m2dom, dene the following sets of directions. 1. IN ~(~m) =n ~u2U2~m+~u~~mand stri~(~m)(~m;~u)>0o

2. OUT

~(~m) =n ~u2U2~u2IN~(~m+~u)o

Intuitively, IN

~(~m) is the set of sides on which the tile at~minitially binds in the assembly sequence~, and OUT ~(~m) is the set of sides on which this tile propagates information to future tiles.

Note that IN

~(~m) =;for all~m20. Notation 5.If~= (ij0i < k) is a-T-assembly sequence,= res(~), and~m2domdom0, then ~n~m= dom f~mg ~m+ OUT~(~m) 6 (Note that~n~mis aT-conguration that may or may not be a-T-assembly. Denition 17.(Soloveichik and Winfree [16]). A-T-assembly sequence~= (ij0i < k) with result islocally deterministicif it has the following three properties.quotesdbs_dbs46.pdfusesText_46

[PDF] le triangle de sierpinski exercice corrigé 5eme

[PDF] Le triangle équilatéral

[PDF] Le triangle est-il rectangle

[PDF] le triangle et ces paralleles

[PDF] Le triangle et son périmètre ( exercice très court)

[PDF] Le triangle isocèle

[PDF] Le triangle rectangle

[PDF] Le triangle rectangle AHC

[PDF] Le Triathlon

[PDF] Le tricercle de MOHR

[PDF] le trident

[PDF] le trident de newton

[PDF] Le trinôme

[PDF] Le triomphe de Bel-Ami

[PDF] le triomphe de la volonté