DROPS

Document

Extended Abstract

Universal Shape Replication via Self-Assembly with Signal-Passing Tiles (Extended Abstract)

Authors: Andrew Alseth, Daniel Hader, and Matthew J. Patitz

Published in: LIPIcs, Volume 238, 28th International Conference on DNA Computing and Molecular Programming (DNA 28) (2022)

Abstract

In this paper, we investigate shape-assembling power of a tile-based model of self-assembly called the Signal-Passing Tile Assembly Model (STAM). In this model, the glues that bind tiles together can be turned on and off by the binding actions of other glues via "signals". In fact, we prove our positive results in a version of the model in which it is slightly more difficult to work (where tiles are allowed to rotate) but show that they also hold in the standard STAM. Specifically, the problem we investigate is "shape replication" wherein, given a set of input assemblies of arbitrary shape, a system must construct an arbitrary number of assemblies with the same shapes and, with the exception of size-bounded junk assemblies that result from the process, no others. We provide the first fully universal shape replication result, namely a single tile set capable of performing shape replication on arbitrary sets of any 3-dimensional shapes without requiring any scaling or pre-encoded information in the input assemblies. Our result requires the input assemblies to be composed of signal-passing tiles whose glues can be deactivated to allow deconstruction of those assemblies, which we also prove is necessary by showing that there are shapes whose geometry cannot be replicated without deconstruction. Additionally, we modularize our construction to create systems capable of creating binary encodings of arbitrary shapes, and building arbitrary shapes from their encodings. Because the STAM is capable of universal computation, this then allows for arbitrary programs to be run within an STAM system, using the shape encodings as input, so that any computable transformation can be performed on the shapes.

Cite as

Andrew Alseth, Daniel Hader, and Matthew J. Patitz. Universal Shape Replication via Self-Assembly with Signal-Passing Tiles (Extended Abstract). In 28th International Conference on DNA Computing and Molecular Programming (DNA 28). Leibniz International Proceedings in Informatics (LIPIcs), Volume 238, pp. 2:1-2:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{alseth_et_al:LIPIcs.DNA.28.2,
  author =	{Alseth, Andrew and Hader, Daniel and Patitz, Matthew J.},
  title =	{{Universal Shape Replication via Self-Assembly with Signal-Passing Tiles}},
  booktitle =	{28th International Conference on DNA Computing and Molecular Programming (DNA 28)},
  pages =	{2:1--2:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-253-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{238},
  editor =	{Ouldridge, Thomas E. and Wickham, Shelley F. J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.28.2},
  URN =		{urn:nbn:de:0030-drops-167876},
  doi =		{10.4230/LIPIcs.DNA.28.2},
  annote =	{Keywords: Algorithmic self-assembly, Tile Assembly Model, shape replication}
}

Document

DOI: 10.4230/LIPIcs.DNA.27.3

Self-Replication via Tile Self-Assembly (Extended Abstract)

Authors: Andrew Alseth, Daniel Hader, and Matthew J. Patitz

Published in: LIPIcs, Volume 205, 27th International Conference on DNA Computing and Molecular Programming (DNA 27) (2021)

Abstract

In this paper we present a model containing modifications to the Signal-passing Tile Assembly Model (STAM), a tile-based self-assembly model whose tiles are capable of activating and deactivating glues based on the binding of other glues. These modifications consist of an extension to 3D, the ability of tiles to form "flexible" bonds that allow bound tiles to rotate relative to each other, and allowing tiles of multiple shapes within the same system. We call this new model the STAM*, and we present a series of constructions within it that are capable of self-replicating behavior. Namely, the input seed assemblies to our STAM* systems can encode either "genomes" specifying the instructions for building a target shape, or can be copies of the target shape with instructions built in. A universal tile set exists for any target shape (at scale factor 2), and from a genome assembly creates infinite copies of the genome as well as the target shape. An input target structure, on the other hand, can be "deconstructed" by the universal tile set to form a genome encoding it, which will then replicate and also initiate the growth of copies of assemblies of the target shape. Since the lengths of the genomes for these constructions are proportional to the number of points in the target shape, we also present a replicator which utilizes hierarchical self-assembly to greatly reduce the size of the genomes required. The main goals of this work are to examine minimal requirements of self-assembling systems capable of self-replicating behavior, with the aim of better understanding self-replication in nature as well as understanding the complexity of mimicking it.

Cite as

Andrew Alseth, Daniel Hader, and Matthew J. Patitz. Self-Replication via Tile Self-Assembly (Extended Abstract). In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{alseth_et_al:LIPIcs.DNA.27.3,
  author =	{Alseth, Andrew and Hader, Daniel and Patitz, Matthew J.},
  title =	{{Self-Replication via Tile Self-Assembly (Extended Abstract)}},
  booktitle =	{27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
  pages =	{3:1--3:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-205-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{205},
  editor =	{Lakin, Matthew R. and \v{S}ulc, Petr},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.3},
  URN =		{urn:nbn:de:0030-drops-146707},
  doi =		{10.4230/LIPIcs.DNA.27.3},
  annote =	{Keywords: Algorithmic self-assembly, tile assembly model, self-replication}
}

Search Results

Documents authored by Alseth, Andrew

Universal Shape Replication via Self-Assembly with Signal-Passing Tiles (Extended Abstract)

Abstract

Cite as

Self-Replication via Tile Self-Assembly (Extended Abstract)

Abstract

Cite as

Thanks for your feedback!

Could not send message