Abstract
Self-assembly is a process in which small building blocks interact autonomously to form larger structures. A recently studied model of self-assembly is the Accretive Graph Assembly Model whereby an edge-weighted graph is assembled one vertex at a time starting from a designated seed vertex. The weight of an edge specifies the magnitude of attraction (positive weight) or repulsion (negative weight) between adjacent vertices. It is feasible to add a vertex to the assembly if the total attraction minus repulsion of the already built neighbors exceeds a certain threshold, called the assembly temperature. This model naturally generalizes the extensively studied Tile Assembly Model.
A natural question in graph self-assembly is to determine whether or not there exists a sequence of feasible vertex additions to realize the entire graph. However, even when it is feasible to realize the assembly, not much can be inferred about its likelihood of realization in practice due to the uncontrolled nature of the self-assembly process. Motivated by this, we introduce the robust self-assembly problem where the goal is to determine if every possible sequence of feasible vertex additions leads to the completion of the assembly. We show that the robust self-assembly problem is co-NP–complete even on planar graphs with two distinct edge weights. We then examine the tractability of the robust self-assembly problem on a natural subclass of planar graphs, namely grid graphs. We identify structural conditions that determine whether or not a grid graph can be robustly self-assembled, and give poly-time algorithms to determine this for several interesting cases of the problem. Finally, we also show that the problem of counting the number of feasible orderings that lead to the completion of an assembly is #P-complete.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Winfree, E., Liu, F., Wenzler, L.A., Seeman, N.C.: Design and self-assembly of two-dimensional DNA crystals. Nature 394, 539–544 (1998)
Rothemund, P.: Using lateral capillary forces to compute by self-assembly. Proc. Nat. Acad. Sci. U.S.A. 97, 984–989 (2000)
LaBean, T.H., Yan, H., Kopatsch, J., Liu, F., Winfree, E., Reif, J.H., Seeman, N.C.: Construction, analysis, ligation, and self-assembly of DNA triple crossover complexes. J. Amer. Chem. Soc. 122, 1848–1860 (2000)
Yan, H., LaBean, T.H., Feng, L., Reif, J.H.: Directed nucleation assembly of DNA tile complexes for barcode-patterned lattices. Proc. Nat. Acad. Sci. U.S.A. 100, 8103–8108 (2003)
Rothemund, P.W.K., Papadakis, N., Winfree, E.: Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biology 2, 2041–2053 (2004)
Chelyapov, N., Brun, Y., Gopalkrishnan, M., Reishus, D., Shaw, B., Adleman, L.M.: DNA triangles and self-assembled hexagonal tilings. J. Amer. Chem. Soc. 126, 13924–13925 (2004)
He, Y., Chen, Y., Liu, H., Ribbe, A.E., Mao, C.: Self-assembly of hexagonal DNA two-dimensional (2D) arrays. J. Amer. Chem. Soc. 127, 12202–12203 (2005)
Malo, J., Mitchell, J.C., Vénien-Bryan, C., Harris, J.R., Wille, H., Sherratt, D.J., Turberfield, A.J.: Engineering a 2D protein-DNA crystal. Angewandte Chemie International Edition 44, 3057–3061 (2005)
Rothemund, P.W.K., Winfree, E.: The program-size complexity of self-assembled squares (extended abstract). In: STOC, pp. 459–468 (2000)
Wang, H.: Proving theorems by pattern recognition II. Bell Systems Technical Journal 40, 1–41 (1961)
Reif, J.H., Sahu, S., Yin, P.: Complexity of graph self-assembly in accretive systems and self-destructible systems. In: Carbone, A., Pierce, N.A. (eds.) DNA 2005. LNCS, vol. 3892, pp. 257–274. Springer, Heidelberg (2006)
Winfree, E., Bekbolatov, R.: Proofreading tile sets: Error correction for algorithmic self-assembly. In: Chen, J., Reif, J.H. (eds.) DNA 2003. LNCS, vol. 2943, pp. 126–144. Springer, Heidelberg (2004)
Chen, H.-L., Goel, A.: Error free self-assembly using error prone tiles. In: Ferretti, C., Mauri, G., Zandron, C. (eds.) DNA 2004. LNCS, vol. 3384, pp. 62–75. Springer, Heidelberg (2005)
Angelov, S., Khanna, S., Visontai, M.: On the complexity of graph self-assembly in accretive systems. Natural Computing 7, 183–201 (2008)
Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11, 329–343 (1982)
Middleton, A.A.: Computational complexity of determining the barriers to interface motion in random systems. Phys. Rev. E 59, 2571–2577 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Angelov, S., Khanna, S., Visontai, M. (2009). Robust Self-assembly of Graphs. In: Goel, A., Simmel, F.C., Sosík, P. (eds) DNA Computing. DNA 2008. Lecture Notes in Computer Science, vol 5347. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03076-5_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-03076-5_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03075-8
Online ISBN: 978-3-642-03076-5
eBook Packages: Computer ScienceComputer Science (R0)