CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20110309-104201054

[img]
Preview
PDF - Submitted Version
See Usage Policy.

217Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20110309-104201054

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1007/11753681_24DOIArticle
https://rdcu.be/b11JfPublisherFree ReadCube access
ORCID:
AuthorORCID
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.
Funders:
Funding AgencyGrant Number
NSFCCF-0432193
Series Name:Lecture Notes in Computer Science
Issue or Number:3892
Record Number:CaltechAUTHORS:20110309-104201054
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20110309-104201054
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:22756
Collection:CaltechAUTHORS
Deposited By: Lucinda Acosta
Deposited On:21 Oct 2011 17:08
Last Modified:21 Feb 2020 22:33

Repository Staff Only: item control page