Difference between revisions of "Shape Replication Through Self-Assembly and RNase Enzymes"
(Created page with "{{PaperTemplate |date=2010/01/05 |abstract=We introduce the problem of shape replication in the Wang tile self-assembly model. Given an input shape, we consider the problem of de...") |
|||
| Line 1: | Line 1: | ||
{{PaperTemplate | {{PaperTemplate | ||
|date=2010/01/05 | |date=2010/01/05 | ||
| − | |abstract=We introduce the problem of shape replication in the Wang tile self-assembly model. Given an input shape, we consider the problem of designing a self-assembly system which will replicate that shape into either a specific number of copies, or an unbounded number of copies. Motivated by practical DNA implementations of Wang tiles, we consider a model in which tiles consisting of DNA or RNA can be dynamically added in a sequence of stages. We further permit the addition of RNase enzymes capable of disintegrating RNA tiles. Under this model, we show that arbitrary genus-0 shapes can be replicated infinitely many times using only O(1) distinct tile types and O(1) stages. Further, we show how to replicate precisely n copies of a shape using O(log n) stages and O(1) tile types. | + | |abstract=We introduce the problem of shape replication in the Wang tile self-assembly model. Given an input shape, we consider the problem of designing a self-assembly system which will replicate that shape into either a specific number of copies, or an unbounded number of copies. Motivated by practical DNA implementations of Wang tiles, we consider a model in which tiles consisting of DNA or RNA can be dynamically added in a sequence of stages. We further permit the addition of RNase enzymes capable of disintegrating RNA tiles. Under this model, we show that arbitrary genus-0 shapes can be replicated infinitely many times using only $O(1)$ distinct tile types and $O(1)$ stages. Further, we show how to replicate precisely $n$ copies of a shape using $O(\log n)$ stages and $O(1)$ tile types. |
|authors=Zachary Abel, Nadia Benbernou, Mirela Damian, Erik Demaine, Martin Demaine, Robin Flatland, Scott Kominers, Robert Schweller | |authors=Zachary Abel, Nadia Benbernou, Mirela Damian, Erik Demaine, Martin Demaine, Robin Flatland, Scott Kominers, Robert Schweller | ||
| − | |file=Replicate.pdf | + | |file=[[media:Replicate.pdf]] |
}} | }} | ||
Revision as of 00:37, 29 February 2012
Published on: 2010/01/05
Abstract
We introduce the problem of shape replication in the Wang tile self-assembly model. Given an input shape, we consider the problem of designing a self-assembly system which will replicate that shape into either a specific number of copies, or an unbounded number of copies. Motivated by practical DNA implementations of Wang tiles, we consider a model in which tiles consisting of DNA or RNA can be dynamically added in a sequence of stages. We further permit the addition of RNase enzymes capable of disintegrating RNA tiles. Under this model, we show that arbitrary genus-0 shapes can be replicated infinitely many times using only \(O(1)\) distinct tile types and \(O(1)\) stages. Further, we show how to replicate precisely \(n\) copies of a shape using \(O(\log n)\) stages and \(O(1)\) tile types.
Authors
Zachary Abel, Nadia Benbernou, Mirela Damian, Erik Demaine, Martin Demaine, Robin Flatland, Scott Kominers, Robert Schweller
