One-dimensional staged self-assembly
17th International Conference, DNA 17, Pasadena, CA, USA, September 19-23, 2011. Proceedings
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer Berlin / Heidelberg
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73835 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-3182-1675 |
| _version_ | 1826199338279239680 |
|---|---|
| author | Demaine, Erik D. Eisenstat, Sarah Charmian Ishaque, Mashhood Winslow, Andrew |
| 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. Eisenstat, Sarah Charmian Ishaque, Mashhood Winslow, Andrew |
| author_sort | Demaine, Erik D. |
| collection | MIT |
| description | 17th International Conference, DNA 17, Pasadena, CA, USA, September 19-23, 2011. Proceedings |
| first_indexed | 2024-09-23T11:18:37Z |
| format | Article |
| id | mit-1721.1/73835 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:18:37Z |
| publishDate | 2012 |
| publisher | Springer Berlin / Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/738352022-10-01T02:41:50Z One-dimensional staged self-assembly Demaine, Erik D. Eisenstat, Sarah Charmian Ishaque, Mashhood Winslow, Andrew Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Eisenstat, Sarah Charmian 17th International Conference, DNA 17, Pasadena, CA, USA, September 19-23, 2011. Proceedings We introduce the problem of staged self-assembly of one-dimensional nanostructures, which becomes interesting when the elements are labeled (e.g., representing functional units that must be placed at specific locations). In a restricted model in which each operation has a single terminal assembly, we prove that assembling a given string of labels with the fewest stages is equivalent, up to constant factors, to compressing the string to be uniquely derived from the smallest possible context-free grammar (a well-studied O(logn)-approximable problem). Without this restriction, we show that the optimal assembly can be substantially smaller than the optimal context-free grammar, by a factor of Ω √n/log n even for binary strings of length n. Fortunately, we can bound this separation in model power by a quadratic function in the number of distinct glues or tiles allowed in the assembly, which is typically small in practice. 2012-10-10T15:54:04Z 2012-10-10T15:54:04Z 2011-09 2011-09 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-23637-2 0302-9743 1611-3349 http://hdl.handle.net/1721.1/73835 Demaine, Erik D. et al. “One-Dimensional Staged Self-assembly.” DNA Computing and Molecular Programming. Ed. Luca Cardelli & William Shih. LNCS Vol. 6937. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. 100–114. https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-3182-1675 en_US http://dx.doi.org/10.1007/978-3-642-23638-9_10 DNA Computing and Molecular Programming Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer Berlin / Heidelberg MIT web domain |
| spellingShingle | Demaine, Erik D. Eisenstat, Sarah Charmian Ishaque, Mashhood Winslow, Andrew One-dimensional staged self-assembly |
| title | One-dimensional staged self-assembly |
| title_full | One-dimensional staged self-assembly |
| title_fullStr | One-dimensional staged self-assembly |
| title_full_unstemmed | One-dimensional staged self-assembly |
| title_short | One-dimensional staged self-assembly |
| title_sort | one dimensional staged self assembly |
| url | http://hdl.handle.net/1721.1/73835 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-3182-1675 |
| work_keys_str_mv | AT demaineerikd onedimensionalstagedselfassembly AT eisenstatsarahcharmian onedimensionalstagedselfassembly AT ishaquemashhood onedimensionalstagedselfassembly AT winslowandrew onedimensionalstagedselfassembly |