A Caltech Library Service

Complexity of compact proofreading for self-assembled patterns

Soloveichik, David and Winfree, Erik (2006) Complexity of compact proofreading for self-assembled patterns. In: DNA Computing. Lecture Notes in Computer Science. No.3892. Springer , Berlin, pp. 305-324. ISBN 3-540-34161-7.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ReadCube access
Soloveichik, David0000-0002-2585-4120
Winfree, Erik0000-0002-5899-7523
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.
Funding AgencyGrant Number
Series Name:Lecture Notes in Computer Science
Issue or Number:3892
Record Number:CaltechAUTHORS:20110309-104201054
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:22756
Deposited By: Lucinda Acosta
Deposited On:21 Oct 2011 17:08
Last Modified:09 Nov 2021 16:07

Repository Staff Only: item control page