DNA tile self-assembly for 3D-surfaces Towards genus identification Florent Becker and Shahrzad Heydarshahi

2025-05-03 0 0 3.15MB 37 页 10玖币

侵权投诉

DNA tile self-assembly for 3D-surfaces: Towards genus

identiﬁcation

Florent Becker and Shahrzad Heydarshahi

2023-06-19

Abstract

We introduce a new DNA tile self-assembly model: the Surface Flexible Tile Assembly Model

(SFTAM), where 2D tiles are placed on host 3D surfaces made of axis-parallel unit cubes glued

together by their faces, called polycubes. The bonds are ﬂexible, so that the assembly can bind on

the edges of the polycube. We are interested in the study of SFTAM self-assemblies on 3D surfaces

which are not always embeddable in the Euclidean plane, in order to compare their diﬀerent behaviors

and to compute the topological properties of the host surfaces.

We focus on a family of polycubes called order-1 cuboids.Order-0 cuboids are polycubes that have

six rectangular faces, and order-1 cuboids are made from two order-0 cuboids by substracting one

from the other. Thus, order-1 cuboids can be of genus 0 or of genus 1 (then they contain a tunnel).

We are interested in the genus of these structures, and we present a SFTAM tile assembly system

that determines the genus of a given order-1 cuboid. The SFTAM tile assembly system which we

design, contains a speciﬁc set Yof tile types with the following properties. If the assembly is made

on a host order-1 cuboid Cof genus 0, no tile of Yappears in any producible assembly, but if Chas

genus 1, every terminal assembly contains at least one tile of Y.

Thus, for order-1 cuboids our system is able to distinguish the host surfaces according to their

genus, by the tiles used in the assembly. This system is speciﬁc to order-1 cuboids but we can expect

that the techniques we use to be generalizable to other families of shapes.

1 Introduction

In this paper, we introduce a new tile self-assembly model in order to perform self-assembly on 3-

dimensional surfaces. The ﬁeld of tile self-assemby originates in the work of Wang [14], who introduced in

1961 Wang tiles, that is, equally sized 2-dimensional unit squares with labels/colors on each edge (later

called glues) and designed a Turing universal computation model based on these tiles. In 1998, inspired by

Wang tiles and DNA complexes from Seeman’s laboratory [6], Winfree introduced in his PhD thesis [15]

the abstract Tile Assembly Model (aTAM). This model uses Wang tiling with an extra information: he

associated a non-negative integer strength for each glue label. The power of DNA self-assembly enables

to compute using this model. We refer to the survey [9] for more details on the literature, and to the

online bibliography of Seeman’s laboratory [13].

Most of the early work in the DNA tile self-assembly literature deals with rigid assemblies in the

Euclidean plane [9, 10] (since the assemblies are discrete, the Euclidean plane is usually seen as the

lattice Z2), which is a natural and simple setting for this model. However, it can be interesting to use

self-assembly in richer settings. This has been investigated experimentally for instance in [12, 16, 17]

where the assembly takes place on a preexisting surface and changes according to the surface. On the

theoretical side, there have been some recent works on DNA tile self-assembly outside the Euclidean

plane, such as tile self-assembly in mazes [4], where the tile placement is done on the walls of a certain

maze. Other types of self-assembly exist that also do not use the Euclidean plane, for example a model

of cross-shaped origami tiles [18]. Another type of self-assembly not in the plane is 3D assemblies of

complex molecules like crystals [3, 8]. Inspired by this, a recent model called Flexible Tile Assembly

Model (FTAM) was introduced by Durand-Lose et al. in 2020 [5], as an extension of earlier work [7].

Here, we have Wang tiles but they self-assemble (without an input surface) in 3D space (modeled by the

lattice Z3) as they can have, in addition to standard rigid bonds, ﬂexible bonds that allow tiles to bind

arXiv:2210.13094v3 [cs.DM] 15 Jun 2023

1 INTRODUCTION 2

at any angle along the tile edges. The goal of the FTAM model is to construct complex 3D structures

called polycubes (3D shapes made of unit cubes) [2].

In 2010, Abel et al. [1] used a variant of the aTAM to implement shape replication, where tiles react

to the shape of a preexisting pattern to reproduce it. However, this setting is on the 1 dimensional border

of a 2D pattern instead of the 2D surface of 3D objects in our setting. In this setting (like in the current

work), the main challenge is that the system must react to the shape of the space around, rather than to

an external input it can read as it wants.

We are interested in studying what happens if we put the tiles on a given 3D surface that is not

necessarily topologically equivalent to the Euclidean plane. The intuition is that this could modify the

computational behaviour of the tile self-assembly model, and we believe it will be interesting for practical

systems, as in some practical settings, self-assembly could be performed on complex surfaces.

Inspired by the FTAM, we introduce a new model, called Surface Flexible Tile Assembly Model

(SFTAM). In the SFTAM, we are given a 3D surface, on which the tiles of the self-assembly get placed.

The SFTAM is an intermediate between aTAM and FTAM. Unlike in the FTAM, our aim for introducing

the SFTAM is not for building 3D structures or surfaces: we assume that the host surface already exists.

In the SFTAM, tile bonds are all ﬂexible and the tiles can bind along the edges of the surface.

This model enables to use self-assembly on surfaces other than Z2. The aim of this article is to

introduce the SFTAM model, and to demonstrate its usefulness by showing how it can be used on various

types of surfaces. One of the most important properties of a surface is its genus, which, intuitively, is

the number of “holes” in the surface. The Euclidean plane has genus 0. We are interested in using the

SFTAM on surfaces with diﬀerent values of genus. For that, we study the problem of characterizing the

surface of the assembly, according to its genus, using the SFTAM. It is quit easy to devise a system which

can behave in some way only on the torus, but it is harder to make sure that it has always this behavior

when it is in fact on a torus.

We focus on a family of 3D surfaces called cuboids, which are special types of polycubes. Polycubes

can form complex surfaces, and their genus can be high. We focus on a simple family of polycubes that

can have genus 0 or genus 1. More speciﬁcally, we deﬁne an order-0 cuboid C0as a polycube which has

only six faces. An order-1 cuboid C1=C0\C′

0is a polycube that is made from the diﬀerence of two

order-0 cuboids C0and C′

0. Thus, an order-0 cuboid is a simple surface with genus 0, but an order-1

cuboid can either have genus 0 (potentially with a pit or concavities) or genus 1, if it has a tunnel.

In this paper, we will suppose that the SFTAM self-assembly is performed on the surface of an order-1

cuboid C. We design an SFTAM system whose assemblies diﬀer when Cis of genus 0 and of genus 1

and thus, can be used to detect the genus of the surface Cof the assembly it is used on. The goal of

this study is to show that performing self-assembly on surfaces of higher genus can be helpful. We also

demonstrate some techniques which may prove useful in characterizing the topological properties of a

wide range of surfaces.

Atile assembly system (TAS) in the SFTAM is deﬁned in a natural way as an extension of the aTAM:

tile types are made of four glue labels, each has a strength, there is a seed assembly and a temperature

(more formal deﬁnitions will be given later). An assembly is a placement of tiles on facets of the surface

of the cuboid C. Two tiles bind if they are adjacent (i.e. their placements on the surface share an edge)

and their glue labels are the same. In particular, edges are ﬂexible and as a result the tiles can be placed

on the border of orthogonal faces of C. The assembly is producible if it can be obtained by successfully

binding tiles, starting from a seed. It is terminal if no additional tile can be bound to an existing tile.

Let C=C0\C′

0be an order-1 cuboid with its three dimensions at least 10 for C′

0. Our main result

is to describe an SFTAM (TAS) SGwith a subset Yof its tile types such that the following holds:

•if the order-1 cuboid Chas genus 0, then no tile of Yappears in any producible assembly of SGon

C, and

•if Chas genus 1, every terminal assembly of SGon Ccontains at least one tile of Y.

In other words, the genus of Ccan be determined using the assemblies of SGon C. The assemblies of

SGconsist of two phases: a skeleton forms on the cuboid and separates it into several regions, then the

regions are partially ﬁlled by inner tiles. For a sketch of the skeleton and its inner ﬁlling for an order-0

cuboid see Fig. 1. The skeleton of the assembly forms in 3 steps RX(in red), RY(in green) and RZ(in

blue). After the formation of the skeleton the tiles of type teven and todd partially ﬁll inside the skeleton.

1 INTRODUCTION 3

teven

todd

Seed

Figure 1: The skeleton of a SGassembly on an order-0 cuboid is showed in color. It is started from a seed

in yellow and after the formation of the skeleton, the regions partially ﬁll by todd and teven tile types.

When the cuboid has genus 1, we show that there must be some parts of the skeleton or the inner

ﬁlling which intersect in a way that is not possible on a genus-0 cuboid. The tile types of Ystick at the

place where this happens. See Fig. 2.

We start with basic deﬁnitions and notations in Section 2, where we introduce and formalize our

SFTAM model. Next, we introduce the family of order-1 cuboids and we show how SFTAM behaves on

the family of order-1 cuboids as an assembly model in three dimensions. In Section 3 we develop technical

lemmas that will be necessary for the proof of our main result. In Section 4 we present our main result:

a SFTAM tile assembly system that identiﬁes the genus of order-1 cuboids using speciﬁc tiles from that

system. We conclude in Section 5.

treg

Seed

(a) The case where the skeleton

does not meet the tunnel. In this

case, the tile types todd and teven

of regions where the entrances of

the tunnel is located, pass inside

the tunnel. In their collision a tile

of type treg appears in the assem-

bly.

tibc

Seed

(b) The tunnel intersects along

the width of plane PXand length

of plane PY. The tibc is a tile type

from Tibc

tmfs

Seed

an order-1 cuboid is shown by a

tile of type tmf s , located at the

intersection of the skeleton.

Figure 2: According to the relative position of the seed and the tunnel, the detection of the tunnel is

done by diﬀerent tile types of SGin the assembly. The seed in indicated in yellow and the skeleton is in

color.

2 DEFINITIONS AND NOTATIONS 4

2 Deﬁnitions and notations

In this section, we present the notions and deﬁnitions that are used throughout this paper. First, we

explain what we mean by a tile assembly model for 3D surfaces in Z3and we present our model: the

Surface Flexible Tile assembly model or SFTAM. Then we present the family of surfaces that we work

on: order-1 cuboids.

2.1 The tile assembly model on surfaces in Z3: SFTAM

We now deﬁne the Surface Flexible Tile assembly Model, SFTAM. We work in 3-dimensional space, on

the integer lattice Z3.

Deﬁnition 1 (Tile type in SFTAM).Let Σbe a ﬁnite label alphabet and ϵrepresent the null label. A

tile type tis a 4-tuple t= (t1, t2, t3, t4)with ti∈Σ∪ {ϵ}for each i={1,2,3,4}. Each copy of a tile type

is a tile and t1, t2, t3, t4are the glues of t.

Tiles are 2Dunit squares whose sides are assigned the labels of the tile type. These squares are

allowed to translate and rotate (unlike in aTAM), but they can not be mirrored (unlike in FTAM). In

fact, since the tiles stick to a given surface, we can assume that they have an inner face and an outer

face and that they always attach with the inner face in contact with the surface. In the deﬁnition of tile

types, we show labels by numbers rather than cardinal directions. However, often, the orientation of a

tile dictates the orientation of the tiles around it. Then, we use the expression “northern label” to refer

to the label which will end up on the northern side (and similarly for east, west, south).

Deﬁnition 2 (Facet).Afacet is a face of the lattice Z3, i.e. a unit square whose vertices have integer

coordinates.

Deﬁnition 3 (Polycube).Apolycube is a 3D structure that is a subset of Z3and is formed by the union

of unit cubes that are attached by their faces.

For a facet of a polycube, there are four possibilities for placing a tile. We formalize this as follows.

Deﬁnition 4 (Placement).Let Cbe a polycube. A placement p= (f, o)on Cconsists of a facet fon

the surface of C, and a side oof f, called its orientation.

We denote the set of all placements in Cby P l(C).

Given a tile type t= (t1, t2, t3, t4)and a placement p= (f, o),placing tat the placement pdeﬁnes a

mapping from the edges of fto the label alphabet Σ. The i-th side of f(starting from the orientation o

and going in clockwise direction, looking from the exterior of the surface of C) is associated with ti.

Notice that the normal vector nof the placement in the FTAM is not needed in the SFTAM. Indeed,

in the SFTAM, the tiles do not reﬂect. The reason is that we ﬁx that the normal vector (as used in the

FTAM) always starts inside of the polycube and points to the outside of the structure. So, the order of

the tiles’ sides is uniquely determined by the orientation of its placement.

Now we can deﬁne a tile assembly system in the SFTAM.

Deﬁnition 5 (Tile assembly system (TAS) on a polycube in SFTAM).Atile assembly system, or TAS,

over the surface of a given polycube Cis a quintuple S= (Σ, T, σ, str, τ ), where :

•Σis a ﬁnite label alphabet,

•Tis a ﬁnite set of tile types on Σ,

•σis called the seed and can be a single tile or several tiles

•str is a function from Σ∪{ϵ}to non-negative integers called strength function such that str(ϵ)=0,

and

•τ∈Nis called the temperature.

2 DEFINITIONS AND NOTATIONS 5

While the System SFTAM is a theoretical system, its components have an analogy with elements of

practical DNA settings. The labels are the single strands of DNA, the function str show the strength of

their connections and the τis the temperature.

We present the deﬁnitions and notations of SFTAM assemblies that we will use throughout the article.

They deﬁne similar to the ones for the aTAM [9].

Deﬁnition 6. An assembly αof a SFTAM TAS Son a polycube Cis a partial function α: Pl(C) 99K T

deﬁned on at least one placement such that for each facet fof C, there is at most one placement (f, o)

where αis deﬁned.

For placements p= (f, o),p′= (f′, o′)of Pl(C) with α(p) = tand α(p′) = t′such that fand f′are

distinct but have a common side s, we say that tand t′bind together with the strength st if the glues of

tand t′placed on sare equal and have the strength st.

The assembly graph Gαassociated to αhas as its vertices, the placements of Pl(C) that have an

image by α, and two placements pand p′are adjacent in Gαif the tiles α(p)and α(p′)bind.

An assembly αis τ-stable if for breaking Gαto any smaller assemblies, the sum of the strengths of

disconnected edges of Gαneeds to be at least τ.

We start with a seed and then we add tiles one by one. This is formally described as follows.

Deﬁnition 7. Let Cbe a polycube and S= (Σ, T, σ, str, τ )a SFTAM TAS with σpositioned on a

placement of C. An assembly αof Sis producible on Cif either dom(α) = {(p}and α(p) = σwhere

p∈Pl(C), or if αcan be obtained from a producible assembly βby adding a single tile from T\σon

C, such that αis τ−stable. We denote the set of producible assemblies of Sby AC[S]. An assembly

is terminal if no tile can be τ-stably attached on C. The set of producible, terminal assemblies of Sis

denoted by AC

□[S].

2.2 Cuboids

In this part, we introduce the structures that we work on: order-1 cuboids, which are sepcial types of

polycubes. We work in 3-dimensional space, on the integer lattice Z3. We start with some deﬁnitions.

Deﬁnition 8 (Order-0 cuboid).An order-0 cuboid C= (sC, xC, yC, zC)where sC= (sx, sy, sz)∈Z3

is the point of Cwith smallest coordinates and xC, yC, zCare integers representing the length, width

and height of Cis a 3D structure containing all points (x, y, z)of Z3such that sx≤x≤sx+xC,

sy≤y≤sy+yCand sz≤z≤sz+zC. We denote the set of all cuboids by O0.

Note that we work on the boundary surface of cuboids.

We are interested in 3D structures that are more complicated than order-0 cuboids, in particular 3D

structures that can have tunnels, that is, “holes”. To this aim, we introduce a family of polycubes called

order-1 cuboids.

Deﬁnition 9 (Order-1 cuboid).An order-1 cuboid C1is the diﬀerence between two elements of O0.

Given C0= (sC0, xC0, yC0, zC0)and C′

0= (sC′

0, xC′

0, yC′

0, zC′

0)in O0.C1=C0\C′

0is an order-1 cuboid

if there is a i∈ {x, y, z}such that iC0≤iC′

0. We note O1the set of all order-1 cuboids.

Note that an order-0 cuboid is a classic “cuboid”, i.e. it has six rectangular faces. An order-1 cuboid

can have an asymmetric surface, including a hole or a concavity. Moreover, the condition on the dimension

of C0and C′

0ensure that the surface of C1is connected.

The genus of an order-1 cuboid is at most 1. Note that the set of order-0 cuboids is a subset of the

set of order-1 cuboids, that is, O0⊆O1. An order-1 cuboid C1=C0\C′

0can be of three diﬀerent types,

depending on how C0and C′

0interact: (i) C0and C′

0have no intersection, and C1is an order-0 cuboid,

(ii) C′

0cuts a hole in C0, and C1is named as an order-1 cuboid with a tunnel and has genus 1; and (iii)

C0and C′

0intersect but C′

0does not cut a hole in C0. If the cut is in the inner face of C0,C1is an order-1

cuboid with a pit and if the cut is in the side of a face of C0,C1is an order-1 cuboid with a concavity.

In both cases of order-1 cuboid with a pit or with a concavity, the genus is 0.

We denote by O∗

1the set of order-1 cuboids that are not order-0 cuboids, that is, the ones from items

(ii) and (iii) above.

The set of cuboids of O∗

1with a pit are denoted by Op

1, the ones with a tunnel, by Ot

1, and the ones

with a concavity, by Oc

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

DNAtileself-assemblyfor3D-surfaces:TowardsgenusidentificationFlorentBeckerandShahrzadHeydarshahi2023-06-19AbstractWeintroduceanewDNAtileself-assemblymodel:theSurfaceFlexibleTileAssemblyModel(SFTAM),where2Dtilesareplacedonhost3Dsurfacesmadeofaxis-parallelunitcubesgluedtogetherbytheirfaces,calledpolyc...

展开>> 收起<<

DNA tile self-assembly for 3D-surfaces Towards genus identification Florent Becker and Shahrzad Heydarshahi.pdf

共37页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

DNA tile self-assembly for 3D-surfaces Towards genus identification Florent Becker and Shahrzad Heydarshahi

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: