×

zbMATH — the first resource for mathematics

Synthesizing minimal tile sets for patterned DNA self-assembly. (English) Zbl 1309.68210
Sakakibara, Yasubumi (ed.) et al., DNA computing and molecular programming. 16th international conference, DNA 16, Hong Kong, China, June 14–17, 2010. Revised selected papers. Berlin: Springer (ISBN 978-3-642-18304-1/pbk). Lecture Notes in Computer Science 6518, 71-82 (2011).
Summary: The Pattern self-Assembly Tile set Synthesis (PATS) problem is to determine a set of coloured tiles that self-assemble to implement a given rectangular colour pattern. We give an exhaustive branch-and-bound algorithm to find tile sets of minimum cardinality for the PATS problem. Our algorithm makes use of a search tree in the lattice of partitions of the ambient rectangular grid, and an efficient bounding function to prune this search tree. Empirical data on the performance of the algorithm shows that it compares favourably to previously presented heuristic solutions to the problem.
For the entire collection see [Zbl 1205.68022].

MSC:
68W05 Nonnumerical algorithms
68P05 Data structures
68R05 Combinatorics in computer science
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adleman, L., Cheng, Q., Goel, A., Huang, M.-D., Kempe, D., de Espanés, P.M., Rothemund, P.W.K.: Combinatorial optimization problems in self-assembly. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC 2002), pp. 23–32. ACM, New York (2002) · Zbl 1192.90151
[2] Göös, M., Orponen, P.: Synthesizing minimal tile sets for patterned DNA self-assembly. A detailed version, arXiv:0911.2924 · Zbl 1309.68210
[3] Lathrop, J.I., Lutz, J.H., Summers, S.M.: Strict self-assembly of discrete Sierpinski triangles. Theoretical Computer Science 410(4-5), 384–405 (2009) · Zbl 1160.68012 · doi:10.1016/j.tcs.2008.09.062
[4] Lin, C., Liu, Y., Rinker, S., Yan, H.: DNA tile based self-assembly: building complex nanoarchitectures. Chem. Phys. Chem. 7(8), 1641–1647 (2006)
[5] Ma, X., Lombardi, F.: Synthesis of tile sets for DNA self-assembly. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27(5), 963–967 (2008) · Zbl 05516000 · doi:10.1109/TCAD.2008.917973
[6] Ma, X., Lombardi, F.: On the computational complexity of tile set synthesis for DNA self-assembly. IEEE Transactions on Circuits and Systems II: Express Briefs 56(1), 31–35 (2009) · doi:10.1109/TCSII.2008.2010161
[7] Park, S.H., Pistol, C., Ahn, S.J., Reif, J.H., Lebeck, A.R., Dwyer, C., LaBean, T.H.: Finite-size, fully addressable DNA tile lattices formed by hierarchical assembly procedures. Angewandte Chemie International Edition 45(5), 735–739 (2006) · doi:10.1002/anie.200503797
[8] Park, S.H., Yan, H., Reif, J.H., LaBean, T.H., Finkelstein, G.: Electronic nanostructures templated on self-assembled DNA scaffolds. Nanotechnology 15, S525–S527 (2004) · doi:10.1088/0957-4484/15/10/005
[9] Rothemund, P.W.K.: Theory and Experiments in Algorithmic Self-assembly. PhD thesis, University of Southern California (2001)
[10] Rothemund, P.W.K.: Folding DNA to create nanoscale shapes and patterns. Nature 440, 297–302 (2006) · doi:10.1038/nature04586
[11] Rothemund, P.W.K., Winfree, E.: The program-size complexity of self-assembled squares (extended abstract). In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC 2000), pp. 459–468. ACM, New York (2000) · Zbl 1296.68051
[12] Winfree, E.: Algorithmic Self-Assembly of DNA. PhD thesis, California Institute of Technology (1998)
[13] Yan, H., Park, S.H., Finkelstein, G., Reif, J.H., LaBean, T.H.: DNA-templated self-assembly of protein arrays and highly conducive nanowires. Science 301, 1882–1884 (2003) · doi:10.1126/science.1089389
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.