×

zbMATH — the first resource for mathematics

Search methods for tile sets in patterned DNA self-assembly. (English) Zbl 1311.68150
Summary: The pattern self-assembly tile set synthesis (PATS) problem, which arises in the theory of structured DNA self-assembly, is to determine a set of coloured tiles that, starting from a bordering seed structure, self-assembles to a given rectangular colour pattern. The task of finding minimum-size tile sets is known to be NP-hard. We explore several complete and incomplete search techniques for finding minimal, or at least small, tile sets and also assess the reliability of the solutions obtained according to the kinetic tile assembly model.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
52C20 Tilings in \(2\) dimensions (aspects of discrete geometry)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
92D20 Protein sequences, DNA sequences
Software:
Gringo; Smodels
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Göös, M.; Orponen, P., Synthesizing minimal tile sets for patterned DNA self-assembly, (Proc. 16th International Conference on DNA Computing and Molecular Programming, DNA 2010, Lect. Notes Comput. Sci., vol. 6518, (2011), Springer Berlin, Germany), 71-82 · Zbl 1309.68210
[2] Lempiäinen, T.; Czeizler, E.; Orponen, P., Synthesizing small and reliable tile sets for patterned DNA self-assembly, (Proc. 17th International Conference on DNA Computing and Molecular Programming, DNA 2011, Lect. Notes Comput. Sci., vol. 6937, (2011), Springer Berlin, Germany), 145-159 · Zbl 1347.68140
[3] Douglas, S. M.; Dietz, H.; Liedl, T.; Högberg, B.; Graf, F.; Shih, W. M., Self-assembly of DNA into nanoscale three-dimensional shapes, Nature, 459, 414-418, (2009)
[4] Kuzyk, A.; Laitinen, K. T.; Törmä, P., DNA origami as a nanoscale template for protein assembly, Nanotechnology, 20, 235305:1-235305:5, (2009)
[5] Lund, K.; Manzo, A. J.; Dabby, N.; Michelotti, N.; Johnson-Buck, A.; Nangreave, J.; Taylor, S.; Pei, R.; Stojanovic, M. N.; Walter, N. G.; Winfree, E.; Yan, H., Molecular robots guided by prescriptive landscapes, Nature, 465, 206-210, (2010)
[6] Zhang, Z.; Olsen, E. M.; Kryger, M.; Voigt, N. V.; Tørring, T.; Gültekin, E.; Nielsen, M.; MohammadZadegan, R.; Andersen, E. S.; Nielsen, M. M.; Kjems, J.; Birkedal, V.; Gothelf, K. V., A DNA tile actuator with eleven discrete states, Angew. Chem., Int. Ed., 50, 3983-3987, (2011)
[7] Qian, L.; Winfree, E., Scaling up digital circuit computation with DNA strand displacement cascades, Science, 332, 1196-1201, (2011)
[8] Qian, L.; Winfree, E.; Bruck, J., Neural network computation with DNA strand displacement cascades, Nature, 475, 368-372, (2011)
[9] Liu, J.; Cao, Z.; Lu, Y., Functional nucleic acid sensors, Chem. Rev., 109, 1948-1998, (2009)
[10] Li, J.; Pei, H.; Zhu, B.; Liang, L.; Wei, M.; He, Y.; Chen, N.; Li, D.; Huang, Q.; Fan, C., Self-assembled multivalent DNA nanostructures for noninvasive intracellular delivery of immunostimulatory cpg oligonucleotides, ACS Nano, 5, 8783-8789, (2011)
[11] Kim, K. N.; Sarveswaran, K.; Mark, L.; Lieberman, M., DNA origami as self-assembling circuit boards, (Proc. 9th International Conference on Unconventional Computation, UC 2010, Lect. Notes Comput. Sci., vol. 6079, (2010), Springer Berlin, Germany), 56-68
[12] Maune, H. T.; Han, S.; Barish, R. D.; Bockrath, M.; Goddard, W. A.; Rothemund, P. W.K.; Winfree, E., Self-assembly of carbon nanotubes into two-dimensional geometries using DNA origami templates, Nat. Nanotechnol., 5, 61-66, (2010)
[13] Winfree, E.; Liu, F.; Wenzler, L. A.; Seeman, N. C., Design and self-assembly of two-dimensional DNA crystals, Nature, 394, 539-544, (1998)
[14] Yan, H.; Park, S. H.; Finkelstein, G.; Reif, J. H.; LaBean, T. H., DNA-templated self-assembly of protein arrays and highly conductive nanowires, Science, 301, 1882-1884, (2003)
[15] Rothemund, P. W.K., Folding DNA to create nanoscale shapes and patterns, Nature, 440, 297-302, (2006)
[16] Liu, W.; Zhong, H.; Wang, R.; Seeman, N. C., Crystalline two-dimensional DNA-origami arrays, Angew. Chem., Int. Ed., 50, 264-267, (2011)
[17] Rajendran, A.; Endo, M.; Katsuda, Y.; Hidaka, K.; Sugiyama, H., Programmed two-dimensional self-assembly of multiple DNA origami jigsaw pieces, ACS Nano, 5, 665-671, (2011)
[18] Czeizler, E.; Lempiäinen, T.; Orponen, P., A design framework for carbon nanotube circuits affixed on DNA origami tiles, (Proc. 8th Annual Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices, FNANO 2011, (2011)), 186-187, Poster abstract
[19] Ma, X.; Lombardi, F., Synthesis of tile sets for DNA self-assembly, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 27, 963-967, (2008)
[20] Czeizler, E.; Popa, A., Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly, (Proc. 18th International Conference on DNA Computing and Molecular Programming, DNA 2012, Lect. Notes Comput. Sci., vol. 7433, (2012), Springer Berlin, Germany), 58-72 · Zbl 1372.68097
[21] Seki, S., Combinatorial optimization in pattern assembly, (Proc. 12th International Conference on Unconventional Computation and Natural Computation, UCNC 2013, Lect. Notes Comput. Sci., vol. 7956, (2013), Springer Berlin, Germany), 220-231, see also · Zbl 1381.68101
[22] Winfree, E., Simulations of computing by self-assembly, (1998), California Institute of Technology, Technical Report CaltechCSTR:1998.22
[23] Rothemund, P. W.K.; Winfree, E., The program-size complexity of self-assembled squares, (Proc. 32nd Annual ACM Symposium on Theory of Computing, STOC 2000, (2000), ACM New York, NY, USA), 459-468 · Zbl 1296.68051
[24] Gomes, C. P.; Selman, B., Algorithm portfolios, Artif. Intell., 126, 43-62, (2001) · Zbl 0969.68047
[25] Luby, M.; Sinclair, A.; Zuckerman, D., Optimal speedup of Las Vegas algorithms, Inf. Process. Lett., 47, 173-180, (1993) · Zbl 0797.68139
[26] Lifschitz, V., What is answer set programming?, (Proc. 23rd AAAI Conference on Artificial Intelligence, AAAI 2008, (2008), AAAI Press Menlo Park, CA, USA), 1594-1597
[27] Wang, H., Proving theorems by pattern recognition - II, Bell Syst. Tech. J., 40, 1-41, (1961)
[28] Grünbaum, B.; Shephard, G. C., Tilings and patterns, (1986), W.H. Freeman and Company New York, NY, USA · Zbl 0601.05001
[29] Fujibayashi, K.; Hariadi, R.; Park, S. H.; Winfree, E.; Murata, S., Toward reliable algorithmic self-assembly of DNA tiles: A fixed-width cellular automaton pattern, Nano Lett., 8, 1791-1797, (2008)
[30] 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)
[31] Clausen, J.; Perregaard, M., On the best search strategy in parallel branch-and-bound: best-first search versus lazy depth-first search, Ann. Oper. Res., 90, 1-17, (1999) · Zbl 0937.90089
[32] Syrjänen, T., Implementation of local grounding for logic programs with stable model semantics, (1998), Helsinki University of Technology, Digital Systems Laboratory, Technical Report B18
[33] Gebser, M.; Kaminski, R.; König, A.; Schaub, T., Advances in gringo series 3, (Proc. 11th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2011, Lect. Notes Comput. Sci., vol. 6645, (2011), Springer Berlin, Germany), 345-351
[34] Gebser, M.; Kaufmann, B.; Neumann, A.; Schaub, T., Conflict-driven answer set solving, (Proc. 20th International Joint Conference on Artificial Intelligence, IJCAI 2007, (2007), AAAI Press Menlo Park, CA, USA), 386-392
[35] Niemelä, I.; Simons, P., Smodels - an implementation of the stable model and well-founded semantics for normal logic programs, (Proc. 4th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 1997, Lect. Notes Comput. Sci., vol. 1265, (1997), Springer Berlin, Germany), 420-429
[36] Fujibayashi, K.; Murata, S., Precise simulation model for DNA tile self-assembly, IEEE Trans. Nanotechnol., 8, 361-368, (2009)
[37] Schulman, R.; Winfree, E., Programmable control of nucleation for algorithmic self-assembly, SIAM J. Comput., 39, 1581-1616, (2009) · Zbl 1205.68497
[38] SantaLucia, J.; Allawi, H. T.; Seneviratne, P. A., Improved nearest-neighbor parameters for predicting DNA duplex stability, Biochemistry, 35, 3555-3562, (1996)
[39] Endo, M.; Sugita, T.; Katsuda, Y.; Hidaka, K.; Sugiyama, H., Programmed-assembly system using DNA jigsaw pieces, Chemistry, 16, 5362-5368, (2010)
[40] Dwyer, C.; Johri, V.; Cheung, M.; Patwardhan, J.; Lebeck, A.; Sorin, D., Design tools for a DNA-guided self-assembling carbon nanotube technology, Nanotechnology, 15, 1240-1245, (2004)
[41] Lee, D. S.; Svensson, J.; Lee, S. W.; Park, Y. W.; Campbell, E. E.B., Fabrication of crossed junctions of semiconducting and metallic carbon nanotubes: A CNT-gated CNT-FET, J. Nanosci. Nanotechnol., 6, 1325-1330, (2006)
[42] Eskelinen, A.-P.; Kuzyk, A.; Kaltiaisenaho, T. K.; Timmermans, M. Y.; Nasibulin, A. G.; Kauppinen, E. I.; Törmä, P., Assembly of single-walled carbon nanotubes on DNA-origami templates through streptavidin-biotin interaction, Small, 7, 746-750, (2011)
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.