×

zbMATH — the first resource for mathematics

Synthesizing small and reliable tile sets for patterned DNA self-assembly. (English) Zbl 1347.68140
Cardelli, Luca (ed.) et al., DNA computing and molecular programming. 17th international conference, DNA 17, Pasadena, CA, USA, September 19–23, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-23637-2/pbk). Lecture Notes in Computer Science 6937, 145-159 (2011).
Summary: We consider the problem of finding, for a given 2D pattern of colored tiles, a minimal set of tile types self-assembling to this pattern in the abstract Tile Assembly Model of Winfree (1998). This Patterned self-Assembly Tile set Synthesis (PATS) problem was first introduced by Ma and Lombardi (2008), and subsequently studied by Göös and Orponen (2011), who presented an exhaustive partition-search branch-and-bound algorithm (briefly PS-BB) for it. However, finding the true minimal tile sets is very time consuming, and PS-BB is not well-suited for finding small but not necessarily minimal solutions. In this paper, we modify the basic partition-search framework by using a heuristic to optimize the order in which the algorithm traverses its search space. We find that by running several parallel instances of the modified algorithm PS-H, the search time for small tile sets can be shortened considerably. We also introduce a method for computing the reliability of a tile set, i.e. the probability of its error-free self-assembly to the target tiling, based on Winfree’s analysis of the kinetic Tile Assembly Model (1998). We present data on the reliability of tile sets found by the algorithms and find that also here PS-H constitutes a significant improvement over PS-BB.
For the entire collection see [Zbl 1222.68005].

MSC:
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
92D20 Protein sequences, DNA sequences
Software:
Smodels
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Czeizler, E., Lempiäinen, T., Orponen, P.: A design framework for carbon nanotube circuits affixed on DNA origami tiles. In: Proc. 8th Ann. Conf. Foundations of Nanoscience, pp. 186–187 (2011)
[2] Gomes, C.P., Selman, B.: Algorithm portfolios. Artif. Intell. 126, 43–62 (2001) · Zbl 0969.68047 · doi:10.1016/S0004-3702(00)00081-3
[3] Göös, M., Orponen, P.: Synthesizing minimal tile sets for patterned DNA self-assembly. In: Sakakibara, Y., Mi, Y. (eds.) DNA 16 2010. LNCS, vol. 6518, pp. 71–82. Springer, Heidelberg (2011) · Zbl 1309.68210 · doi:10.1007/978-3-642-18305-8_7
[4] Kim, K.N., Sarveswaran, K., Mark, L., Lieberman, M.: DNA origami as self-assembling circuit boards. In: Calude, C.S., Hagiya, M., Morita, K., Rozenberg, G., Timmis, J. (eds.) Unconventional Computation. LNCS, vol. 6079, pp. 56–68. Springer, Heidelberg (2010) · Zbl 05761565 · doi:10.1007/978-3-642-13523-1_9
[5] Lifschitz, V.: What is answer set programming? In: Proc. 23rd Natl. Conf. Artificial Intelligence, pp. 1594–1597 (2008)
[6] Liu, W., Zhong, H., Wang, R., Seeman, N.C.: Crystalline two-dimensional DNA-origami arrays. Angewandte Chemie International Edition 50(1), 264–267 (2011) · doi:10.1002/anie.201005911
[7] Luby, M., Sinclair, A., Zuckerman, D.: Optimal speedup of Las Vegas algorithms. Information Processing Letters 47(4), 173–180 (1993) · Zbl 0797.68139 · doi:10.1016/0020-0190(93)90029-9
[8] Ma, X., Lombardi, F.: Synthesis of tile sets for DNA self-assembly. IEEE Trans. CAD of Integrated Circuits and Systems 27, 963–967 (2008) · Zbl 05516000 · doi:10.1109/TCAD.2008.917973
[9] Maune, H.T., Han, S., Barish, R.D., Bockrath, M., Goddard III, W.A., Rothemund, P.W.K., Winfree, E.: Self-assembly of carbon nanotubes into two-dimensional geometries using DNA origami templates. Nature Nanotechnology 5, 61–66 (2010) · doi:10.1038/nnano.2009.311
[10] Rajendran, A., Endo, M., Katsuda, Y., Hidaka, K., Sugiyama, H.: Programmed two-dimensional self-assembly of multiple DNA origami jigsaw pieces. ACS Nano 5(1), 665–671 (2011) · doi:10.1021/nn1031627
[11] Rothemund, P.W.K., Winfree, E.: The program-size complexity of self-assembled squares. In: Proc. 32nd Ann. ACM Theory of Computing, pp. 459–468 (2000) · Zbl 1296.68051
[12] Rothemund, P.W.K.: Folding DNA to create nanoscale shapes and patterns. Nature 440, 297–302 (2006) · doi:10.1038/nature04586
[13] Syrjänen, T., Niemelä, I.: The Smodels system. In: Logic Programming and Nonmonotonic Reasoning, pp. 434–438. Springer, Heidelberg (2001) · Zbl 1010.68797
[14] Winfree, E., Liu, F., Wenzler, L.A., Seeman, N.C.: Design and self-assembly of two-dimensional DNA crystals. Nature 394 (1998)
[15] Winfree, E.: Simulations of Computing by Self-Assembly. Technical Report CSTR 1998.22, California Institute of Technology (1998)
[16] 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 (2003)
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.