Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract)
We consider a model of algorithmic self-assembly of geometric shapes out of square Wang tiles studied in SODA 2010, in which there are two types of tiles (e.g., constructed out of DNA and RNA material) and one operation that destroys all tiles of a particular type (e.g., an RNAse enzyme destroys all...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Schloss Dagstuhl Publishing
2014
|
| Online Access: | http://hdl.handle.net/1721.1/87549 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1826188241618862080 |
|---|---|
| author | Demaine, Erik D. Patitz, Matthew J. Schweller, Robert T. Summers, Scott M. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Demaine, Erik D. Patitz, Matthew J. Schweller, Robert T. Summers, Scott M. |
| author_sort | Demaine, Erik D. |
| collection | MIT |
| description | We consider a model of algorithmic self-assembly of geometric shapes out of square Wang tiles studied in SODA 2010, in which there are two types of tiles (e.g., constructed out of DNA and RNA material) and one operation that destroys all tiles of a particular type (e.g., an RNAse enzyme destroys all RNA tiles). We show that a single use of this destruction operation enables much more efficient construction of arbitrary shapes. In particular, an arbitrary shape can be constructed using an asymptotically optimal number of distinct tile type (related to the shape's Kolmogorov complexity), after scaling the shape by only a logarithmic factor. By contrast, without the destruction operation, the best such result has a scale factor at least linear in the size of the shape and is connected only by a spanning tree of the scaled tiles. We also characterize a large collection of shapes that can be constructed efficiently without any scaling. |
| first_indexed | 2024-09-23T07:56:41Z |
| format | Article |
| id | mit-1721.1/87549 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T07:56:41Z |
| publishDate | 2014 |
| publisher | Schloss Dagstuhl Publishing |
| record_format | dspace |
| spelling | mit-1721.1/875492022-09-23T09:46:43Z Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract) Demaine, Erik D. Patitz, Matthew J. Schweller, Robert T. Summers, Scott M. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. We consider a model of algorithmic self-assembly of geometric shapes out of square Wang tiles studied in SODA 2010, in which there are two types of tiles (e.g., constructed out of DNA and RNA material) and one operation that destroys all tiles of a particular type (e.g., an RNAse enzyme destroys all RNA tiles). We show that a single use of this destruction operation enables much more efficient construction of arbitrary shapes. In particular, an arbitrary shape can be constructed using an asymptotically optimal number of distinct tile type (related to the shape's Kolmogorov complexity), after scaling the shape by only a logarithmic factor. By contrast, without the destruction operation, the best such result has a scale factor at least linear in the size of the shape and is connected only by a spanning tree of the scaled tiles. We also characterize a large collection of shapes that can be constructed efficiently without any scaling. National Science Foundation (U.S.) (NSF grant CDI-0941538) 2014-05-28T13:45:57Z 2014-05-28T13:45:57Z 2011-03 Article http://purl.org/eprint/type/ConferencePaper 9783939897255 1868-8969 http://hdl.handle.net/1721.1/87549 Demaine, Erik, D., Matthew J. Patitz, Robert T. Schweller, and Scott M. Summers. "Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract)." in 28th Symposium on Theoretical Aspects of Computer Science (STACS’11). March 10-12, 2011, Technische Universität, Dortmund, Germany. Editors: Thomas Schwentick, Christoph Dürr. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. pp. 201–212. https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.4230/LIPIcs.STACS.2011.201 Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) Creative Commons Attribution-NonCommercial-No Derivative Works 3.0 http://creativecommons.org/licenses/by-nc-nd/3.0 application/pdf Schloss Dagstuhl Publishing International Symposium on Theoretical Aspects of Computer Science |
| spellingShingle | Demaine, Erik D. Patitz, Matthew J. Schweller, Robert T. Summers, Scott M. Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract) |
| title | Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract) |
| title_full | Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract) |
| title_fullStr | Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract) |
| title_full_unstemmed | Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract) |
| title_short | Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract) |
| title_sort | self assembly of arbitrary shapes using rnase enzymes meeting the kolmogorov bound with small scale factor extended abstract |
| url | http://hdl.handle.net/1721.1/87549 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT demaineerikd selfassemblyofarbitraryshapesusingrnaseenzymesmeetingthekolmogorovboundwithsmallscalefactorextendedabstract AT patitzmatthewj selfassemblyofarbitraryshapesusingrnaseenzymesmeetingthekolmogorovboundwithsmallscalefactorextendedabstract AT schwellerrobertt selfassemblyofarbitraryshapesusingrnaseenzymesmeetingthekolmogorovboundwithsmallscalefactorextendedabstract AT summersscottm selfassemblyofarbitraryshapesusingrnaseenzymesmeetingthekolmogorovboundwithsmallscalefactorextendedabstract |