Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published 2006 | Submitted
Book Section - Chapter Open

Complexity of compact proofreading for self-assembled patterns

Abstract

Fault-tolerance is a critical issue for biochemical computation. Recent theoretical work on algorithmic self-assembly has shown that error correcting tile sets are possible, and that they can achieve exponential decrease in error rates with a small increase in the number of tile types and the scale of the construction [24, 4]. Following [17], we consider the issue of applying similar schemes to achieve error correction without any increase in the scale of the assembled pattern. Using a new proofreading transformation, we show that compact proofreading can be performed for some patterns with a modest increase in the number of tile types. Other patterns appear to require an exponential number of tile types. A simple property of existing proofreading schemes - a strong kind of redundancy - is the culprit, suggesting that if general purpose compact proofreading schemes are to be found, this type of redundancy must be avoided.

Additional Information

© 2006 Springer-Verlag Berlin Heidelberg. We thank Ho-Lin Chen, Ashish Goel, Paul Rothemund, Matthew Cook, and Nataša Jonoska for discussions that greatly contributed to this work. This work was supported by NSF NANO Grant No. 0432193.

Attached Files

Submitted - fragile_patterns_preprint_1_.pdf

Files

fragile_patterns_preprint_1_.pdf
Files (223.1 kB)
Name Size Download all
md5:18b29d8d2917e13589e5c317361350ea
223.1 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
January 13, 2024