Optimizing tile concentrations to minimize errors and time for DNA tile self-assembly systems

Ho Lin Chen*, Ming-Yang Kao

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Citations (Scopus)

Abstract

DNA tile self-assembly has emerged as a rich and promising primitive for nano-technology. This paper studies the problems of minimizing assembly time and error rate by changing the tile concentrations because changing the tile concentrations is easy to implement in actual lab experiments. We prove that setting the concentration of tile T i proportional to the square root of N i where N i is the number of times T i appears outside the seed structure in the final assembled shape minimizes the rate of growth errors for rectilinear tile systems. We also show that the same concentrations minimize the expected assembly time for a feasible class of tile systems. Moreover, for general tile systems, given tile concentrations, we can approximate the expected assembly time with high accuracy and probability by running only a polynomial number of simulations in the size of the target shape.

Original languageEnglish (US)
Title of host publicationDNA Computing and Molecular Programming - 16th International Conference, DNA 16, Revised Selected Papers
Pages13-24
Number of pages12
DOIs
StatePublished - Feb 1 2011
Event16th International Conference on DNA Computing and Molecular Programming, DNA 16 - Hong Kong, China
Duration: Jun 14 2010Jun 17 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6518 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other16th International Conference on DNA Computing and Molecular Programming, DNA 16
CountryChina
CityHong Kong
Period6/14/106/17/10

Fingerprint

Assembly Systems
Self-assembly
Tile
Self assembly
DNA
Minimise
Nanotechnology
Square root
Seed
Error Rate
High Accuracy
Directly proportional
Polynomials
Target
Polynomial

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Chen, H. L., & Kao, M-Y. (2011). Optimizing tile concentrations to minimize errors and time for DNA tile self-assembly systems. In DNA Computing and Molecular Programming - 16th International Conference, DNA 16, Revised Selected Papers (pp. 13-24). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6518 LNCS). https://doi.org/10.1007/978-3-642-18305-8_2
Chen, Ho Lin ; Kao, Ming-Yang. / Optimizing tile concentrations to minimize errors and time for DNA tile self-assembly systems. DNA Computing and Molecular Programming - 16th International Conference, DNA 16, Revised Selected Papers. 2011. pp. 13-24 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{442c73e0c81548d6964d7cc2a3a24644,
title = "Optimizing tile concentrations to minimize errors and time for DNA tile self-assembly systems",
abstract = "DNA tile self-assembly has emerged as a rich and promising primitive for nano-technology. This paper studies the problems of minimizing assembly time and error rate by changing the tile concentrations because changing the tile concentrations is easy to implement in actual lab experiments. We prove that setting the concentration of tile T i proportional to the square root of N i where N i is the number of times T i appears outside the seed structure in the final assembled shape minimizes the rate of growth errors for rectilinear tile systems. We also show that the same concentrations minimize the expected assembly time for a feasible class of tile systems. Moreover, for general tile systems, given tile concentrations, we can approximate the expected assembly time with high accuracy and probability by running only a polynomial number of simulations in the size of the target shape.",
author = "Chen, {Ho Lin} and Ming-Yang Kao",
year = "2011",
month = "2",
day = "1",
doi = "10.1007/978-3-642-18305-8_2",
language = "English (US)",
isbn = "9783642183041",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "13--24",
booktitle = "DNA Computing and Molecular Programming - 16th International Conference, DNA 16, Revised Selected Papers",

}

Chen, HL & Kao, M-Y 2011, Optimizing tile concentrations to minimize errors and time for DNA tile self-assembly systems. in DNA Computing and Molecular Programming - 16th International Conference, DNA 16, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6518 LNCS, pp. 13-24, 16th International Conference on DNA Computing and Molecular Programming, DNA 16, Hong Kong, China, 6/14/10. https://doi.org/10.1007/978-3-642-18305-8_2

Optimizing tile concentrations to minimize errors and time for DNA tile self-assembly systems. / Chen, Ho Lin; Kao, Ming-Yang.

DNA Computing and Molecular Programming - 16th International Conference, DNA 16, Revised Selected Papers. 2011. p. 13-24 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6518 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Optimizing tile concentrations to minimize errors and time for DNA tile self-assembly systems

AU - Chen, Ho Lin

AU - Kao, Ming-Yang

PY - 2011/2/1

Y1 - 2011/2/1

N2 - DNA tile self-assembly has emerged as a rich and promising primitive for nano-technology. This paper studies the problems of minimizing assembly time and error rate by changing the tile concentrations because changing the tile concentrations is easy to implement in actual lab experiments. We prove that setting the concentration of tile T i proportional to the square root of N i where N i is the number of times T i appears outside the seed structure in the final assembled shape minimizes the rate of growth errors for rectilinear tile systems. We also show that the same concentrations minimize the expected assembly time for a feasible class of tile systems. Moreover, for general tile systems, given tile concentrations, we can approximate the expected assembly time with high accuracy and probability by running only a polynomial number of simulations in the size of the target shape.

AB - DNA tile self-assembly has emerged as a rich and promising primitive for nano-technology. This paper studies the problems of minimizing assembly time and error rate by changing the tile concentrations because changing the tile concentrations is easy to implement in actual lab experiments. We prove that setting the concentration of tile T i proportional to the square root of N i where N i is the number of times T i appears outside the seed structure in the final assembled shape minimizes the rate of growth errors for rectilinear tile systems. We also show that the same concentrations minimize the expected assembly time for a feasible class of tile systems. Moreover, for general tile systems, given tile concentrations, we can approximate the expected assembly time with high accuracy and probability by running only a polynomial number of simulations in the size of the target shape.

UR - http://www.scopus.com/inward/record.url?scp=79251552523&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79251552523&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-18305-8_2

DO - 10.1007/978-3-642-18305-8_2

M3 - Conference contribution

AN - SCOPUS:79251552523

SN - 9783642183041

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 13

EP - 24

BT - DNA Computing and Molecular Programming - 16th International Conference, DNA 16, Revised Selected Papers

ER -

Chen HL, Kao M-Y. Optimizing tile concentrations to minimize errors and time for DNA tile self-assembly systems. In DNA Computing and Molecular Programming - 16th International Conference, DNA 16, Revised Selected Papers. 2011. p. 13-24. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-18305-8_2