More Web Proxy on the site http://driver.im/

article

Randomized Self-Assembly for Exact Shapes

Author:

David DotyAuthors Info & Claims

SIAM Journal on Computing, Volume 39, Issue 8

Pages 3521 - 3552

https://doi.org/10.1137/090779152

Published: 01 September 2010 Publication History

Abstract

Working in Winfree's abstract tile assembly model, we show that a constant-sized tile assembly system can be programmed through relative tile concentrations to build an $n\times n$ square with high probability for any sufficiently large $n$. This answers an open question of Kao and Schweller [Automata, Languages and Programming, Lecture Notes in Comput. Sci. 5125, Springer, Berlin, 2008, pp. 370-384], who showed how to build an approximately $n\times n$ square using tile concentration programming and asked whether the approximation could be made exact with high probability. We show how this technique can be modified to answer another question of Kao and Schweller by showing that a constant-sized tile assembly system can be programmed through tile concentrations to assemble arbitrary finite scaled shapes, which are shapes modified by replacing each point with a $c\times c$ block of points for some integer $c$. Furthermore, we exhibit a smooth trade-off between specifying bits of $n$ via tile concentrations versus specifying them via hard-coded tile types, which allows tile concentration programming to be employed for specifying a fraction of the bits of “input” to a tile assembly system, under the constraint that concentrations can be specified to only a limited precision. Finally, to account for some unrealistic aspects of the tile concentration programming model, we show how to modify the construction to use only concentrations that are arbitrarily close to uniform.

References

[1]

L. M. Adleman, Q. Cheng, A. Goel, and M.-D. Huang, Running time and program size for self-assembled squares, in Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, Hersonissos, Greece, 2001, pp. 740-748.

[2]

F. Becker, I. Rapaport, and E. Rémila, Self-assembling classes of shapes with a minimum number of tiles, and in optimal time, in Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Comput. Sci. 4337, Springer, Berlin, 2006, pp. 45-56.

[3]

C. H. Bennett, Logical depth and physical complexity, in The Universal Turing Machine: A Half-Century Survey, R. Herken, ed., Oxford University Press, London, 1988, pp. 227-257.

[4]

D. M. Bollag, Gel-filtration chromatography, Methods Mol. Biol., 36 (1994), pp. 1-9.

[5]

H. Chandran, N. Gopalkrishnan, and J. H. Reif, The tile complexity of linear assemblies, in Proceedings of the 36th International Colloquium on Automata, Languages and Programming 5555, Springer, New York, 2009, pp. 235-253.

[6]

H.-L. Chen and A. Goel, Error free self-assembly with error prone tiles, in DNA Computing, Lecture Notes in Comput. Sci. 3384, Springer, Berlin, 2004, pp. 62-75.

[7]

M. Cook, D. Soloveichik, E. Winfree, and J. Bruck, Programmability of chemical reaction networks, in Algorithmic Bioprocesses, A. Condon, D. Harel, J. N. Kok, A. Salomaa, and E. Winfree, eds., Springer, Berlin, 2009, pp. 543-584.

[8]

E. D. Demaine, M. L. Demaine, S. P. Fekete, M. Ishaque, E. Rafalin, R. T. Schweller, and D. L. Souvaine, Staged self-assembly: Nanomanufacture of arbitrary shapes with ${O}(1)$ glues, Nat. Comput., 7 (2008), pp. 347-370.

[9]

D. Doty, Randomized self-assembly for exact shapes, in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, Atlanta, GA, 2009, pp. 85-94.

[10]

M.-Y. Kao and R. T. Schweller, Reducing tile complexity for self-assembly through temperature programming, in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2006, pp. 571-580.

[11]

M.-Y. Kao and R. T. Schweller, Randomized self-assembly for approximate shapes, in Automata, Languages and Programming Lecture Notes in Comput. Sci. 5125, Springer, Berlin, 2008, pp. 370-384.

[12]

J. I. Lathrop, J. H. Lutz, and S. M. Summers, Strict self-assembly of discrete Sierpinski triangles, Theoret. Comput. Sci., 410 (2009), pp. 384-405.

[13]

M. Li and P. M. B. Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, 2nd ed., Springer, Berlin, 1997.

[14]

M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, Cambridge, 2005.

[15]

=-1 M. J. Patitz, Simulation of self-assembly in the abstract tile assembly model with ISU TAS, in Proceedings of the 6th Annual Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices, Snowbird, UT, Sciencetechnica, Durham, NC, 2009, pp. 209-219.

[16]

P. W. K. Rothemund, Theory and Experiments in Algorithmic Self-Assembly. Ph.D. thesis, University of Southern California, Los Angeles, CA, 2001.

[17]

P. W. K. Rothemund and E. Winfree, The program-size complexity of self-assembled squares, in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, Portland, OR, 2000, pp. 459-468.

[18]

P. W. K. Rothemund, N. Papadakis, and E. Winfree, Algorithmic self-assembly of DNA Sierpinski triangles, PLoS Biol., 2 (2004), pp. 2041-2053.

[19]

J. Sambrook and D. Russell, Molecular Cloning: A Laboratory Manual, Cold Spring Harbor Laboratory Press, New York, 2001.

[20]

N. C. Seeman, Nucleic-acid junctions and lattices, J. Theoret. Biol., 99 (1982), pp. 237-247.

[21]

A. L. Shapiro, E. Vi$\tilde{\text{n}}$uela, and J. V. Maizel Jr., Molecular weight estimation of polypeptide chains by electrophoresis in SDS-polyacrylamide gels, Biochem. Biophys. Res. Commun., 28 (1967), pp. 815-820.

[22]

D. Soloveichik, M. Cook, E. Winfree, and J. Bruck, Computation with finite stochastic chemical reaction networks, Nat. Comput., 7 (2008), pp. 615-633.

[23]

D. Soloveichik and E. Winfree, Complexity of self-assembled shapes, SIAM Journal on Computing, 36 (2007), pp. 1544-1569.

[24]

S. M. Summers, Reducing tile complexity for the self-assembly of scaled shapes through temperature programming, arXiv:0907.1307v1, 2009.

[25]

H. Wang, Proving theorems by pattern recognition II, Bell Syst. Tech. J., XL (1961), pp. 1-41.

[26]

H. Wang, Dominoes and the AEA case of the decision problem, in Proceedings of the Symposium on Mathematical Theory of Automata, New York, NY, Polytechnic Press of Polytechnic Institute of Brooklyn, Brooklyn, NY, 1963, pp. 23-55.

[27]

E. Winfree, Algorithmic Self-Assembly of DNA, Ph.D. thesis, California Institute of Technology, Pasadena, CA, 1998.

Cited By

Alseth APatitz M(2024)The Need for Seed (in the Abstract Tile Assembly Model)Algorithmica10.1007/s00453-023-01160-w86:1(218-280)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s00453-023-01160-w
Caballero DGomez TSchweller RWylie T(2021)The Complexity of Multiple Handed Self-assemblyUnconventional Computation and Natural Computation10.1007/978-3-030-87993-8_1(1-18)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-87993-8_1
Hou CChen H(2019)An Exponentially Growing Nubot System Without State ChangesUnconventional Computation and Natural Computation10.1007/978-3-030-19311-9_11(122-135)Online publication date: 3-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-19311-9_11
Show More Cited By

Recommendations

Randomized Self-Assembly for Exact Shapes
FOCS '09: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science

Working in Winfree's abstract tile assembly model, we show that a constant-size tile assembly system can be programmed through relative tile concentrations to build an n x n square with high probability, for any sufficiently large n. This answers an ...
Reflections on tiles (in self-assembly)

We define the Reflexive Tile Assembly Model (RTAM), which is obtained from the abstract Tile Assembly Model (aTAM) by allowing tiles to reflect across their horizontal and/or vertical axes. We show that the class of directed temperature-1 RTAM systems ...
Parallelism and Time in Hierarchical Self-Assembly

We study the role that parallelism plays in time complexity of variants of Winfree's abstract Tile Assembly Model (aTAM), a model of molecular algorithmic self-assembly. In the “hierarchical” aTAM, two assemblies, both consisting of multiple tiles, are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Computing

SIAM Journal on Computing Volume 39, Issue 8

August 2010

464 pages

ISSN:0097-5397

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 September 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Alseth APatitz M(2024)The Need for Seed (in the Abstract Tile Assembly Model)Algorithmica10.1007/s00453-023-01160-w86:1(218-280)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s00453-023-01160-w
Caballero DGomez TSchweller RWylie T(2021)The Complexity of Multiple Handed Self-assemblyUnconventional Computation and Natural Computation10.1007/978-3-030-87993-8_1(1-18)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-87993-8_1
Hou CChen H(2019)An Exponentially Growing Nubot System Without State ChangesUnconventional Computation and Natural Computation10.1007/978-3-030-19311-9_11(122-135)Online publication date: 3-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-19311-9_11
Chen H(2019)On the Complexity of Self-assembly TasksUnconventional Computation and Natural Computation10.1007/978-3-030-19311-9_1(1-4)Online publication date: 3-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-19311-9_1
Chin YTsai JChen H(2018)A minimal requirement for self-assembly of lines in polylogarithmic timeNatural Computing: an international journal10.1007/s11047-018-9695-917:4(743-757)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1007/s11047-018-9695-9
Chalk CFu BMartinez ESchweller RWylie T(2017)Concentration independent random number generation in tile self-assemblyTheoretical Computer Science10.1016/j.tcs.2016.12.021667:C(1-15)Online publication date: 8-Mar-2017
https://dl.acm.org/doi/10.1016/j.tcs.2016.12.021
Keenan ASchweller RSherman MZhong X(2016)Fast arithmetic in algorithmic self-assemblyNatural Computing: an international journal10.1007/s11047-015-9512-715:1(115-128)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1007/s11047-015-9512-7
Chen MXin DWoods D(2015)Parallel computation using active self-assemblyNatural Computing: an international journal10.1007/s11047-014-9432-y14:2(225-250)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1007/s11047-014-9432-y
Chen HDoty DSeki S(2015)Program Size and Temperature in Self-AssemblyAlgorithmica10.1007/s00453-014-9879-372:3(884-899)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1007/s00453-014-9879-3
Chalk CFu BHuerta AMaldonado MMartinez ESchweller RWylie T(2015)Flipping TilesProceedings of the 21st International Conference on DNA Computing and Molecular Programming - Volume 921110.1007/978-3-319-21999-8_6(87-103)Online publication date: 17-Aug-2015
https://dl.acm.org/doi/10.1007/978-3-319-21999-8_6
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents