Combinatorial optimization problems in self-assembly

ABSTRACT

Self-assembly is the ubiquitous process by which simple objects autonomously assemble into intricate complexes. It has been suggested that intricate self-assembly processes will ultimately be used in circuit fabrication, nano-robotics, DNA computation, and amorphous computing. In this paper, we study two combinatorial optimization problems related to efficient self-assembly of shapes in the Tile Assembly Model of self-assembly proposed by Rothemund and Winfree [18]. The first is the Minimum Tile Set Problem, where the goal is to find the smallest tile system that uniquely produces a given shape. The second is the Tile Concentrations Problem, where the goal is to decide on the relative concentrations of different types of tiles so that a tile system assembles as quickly as possible. The first problem is akin to finding optimum program size, and the second to finding optimum running time for a "program" to assemble the shape.Self-assembly is the ubiquitous process by which simple objects autonomously assemble into intricate complexes. It has been suggested that intricate self-assembly processes will ultimately be used in circuit fabrication, nano-robotics, DNA computation, and amorphous computing. In this paper, we study two combinatorial optimization problems related to efficient self-assembly of shapes in the Tile Assembly Model of self-assembly proposed by Rothemund and Winfree [18]. The first is the Minimum Tile Set Problem, where the goal is to find the smallest tile system that uniquely produces a given shape. The second is the Tile Concentrations Problem, where the goal is to decide on the relative concentrations of different types of tiles so that a tile system assembles as quickly as possible. The first problem is akin to finding optimum program size, and the second to finding optimum running time for a "program" to assemble the shape.We prove that the first problem is NP-complete in general, and polynomial time solvable on trees and squares. In order to prove that the problem is in NP, we present a polynomial time algorithm to verify whether a given tile system uniquely produces a given shape. This algorithm is analogous to a program verifier for traditional computational systems, and may well be of independent interest. For the second problem, we present a polynomial time $O(\log n)$-approximation algorithm that works for a large class of tile systems that we call partial order systems.

REFERENCES

• 1: Harold Abelson , Don Allen , Daniel Coore , Chris Hanson , George Homsy , Thomas F. Knight, Jr. , Radhika Nagpal , Erik Rauch , Gerald Jay Sussman , Ron Weiss, Amorphous computing, Communications of the ACM, v.43 n.5, p.74-82, May 2000 [doi>10.1145/332833.332842]
• 2: L. Adleman. Towards a (MATH)ematical theory of self-assembly. Technical Report 00-722, Department of Computer Science, University of Southern California, (2000).
• 3: L. Adleman, Q. Cheng, A. Goel, M. Huang and Hal Wasserman. Linear Self-Assemblies: Equilibria, Entropy, and Convergence Rates. Unpublished.
• 4: Leonard Adleman , Qi Cheng , Ashish Goel , Ming-Deh Huang, Running time and program size for self-assembled squares, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.740-748, July 2001, Hersonissos, Greece [doi>10.1145/380752.380881]
• 5: M. Cook, D. Kempe, P. Rothemund, E. Winfree.
• 6: M. Cook, D. Kempe, P. Rothemund, E. Winfree. Personal communication.
• 7: M. Gomez-Lopez, J. Preece, and J. Stoddart, The art and science of self-assembling molecular machines, Nanotechnology, Vol. 7, No. 3, pp. 183--192, September 1996.
• 8: D. Gracias, J. Tien, T. Breen, C. Hsu and G. Whitesides, Forming Electrical Networks in Three Dimensions by Self-Assembly, Science 289, 5482, p 1170--1173 (2000).
• 9: M. Grotschel, L. Lovasz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, 1993 (2nd corrected edition).
• 10: L. Khachian, A Polynomial Algorithm in Linear Programming. Soviet (MATH)ematics Doklady 20, 191--194 (1979).
• 11: G. Lopinski, D. Wayner and R. Wolkow. Self-Directed Growth of Molecular Nano-Structures on Silicon. Nature 406, 48 (2000).
• 12: Graham Louth , Michael Mitzenmacher , Frank Kelly, Computational complexity of loss networks, Theoretical Computer Science, v.125 n.1, p.45-59, March 14, 1994 [doi>10.1016/0304-3975(94)90293-3]
• 13: C. Mao, T. LaBean, J. Reif and N. Seeman. Logical computation using algorithmic self-assembly of DNA triple-crossover molecules. Nature.407, 493--496. (2000).
• 14: Lagoudakis and T. LaBean. 2D DNA Self-Assembly for Satisfiability. in DIMACS Series in Discrete (MATH)ematics and Theoretical Computer Science 1999, Volume 54, Editors: E. Winfree and D.K. Gifford, Proceedings of the 5th DIMACS Workshop on DNA Based Computers; MIT: Cambridge. ISBN 0-8218-2053-2
• 15: J. Reif. Local Parallel Biomolecular Computation. Third Annual DIMACS Workshop on DNA Based Computers, University of Pennsylvania, June 23--26, 1997. Published in DNA Based Computers, III, DIMACS Series in Discrete (MATH)ematics and Theoretical Computer Science, Vol 48 (ed. H. Rubin), American (MATH)ematical Society, p 217--254, (1999).
• 16: P. Rothemund. Using lateral capillary forces to compute by self-assembly. Proceedings of the National Academy of Sciences, vol 9. p 984--989. (2000).
• 17: Paul Wilhelm Karl Rothemund , Leonard M. Adleman, Theory and experiments in algorithmic self-assembly, 2001
• 18: Paul W. K. Rothemund , Erik Winfree, The program-size complexity of self-assembled squares (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.459-468, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335358]
• 19: J.H. Schön, H. Meng and Z. Bao. Self-assembled monolayer organic field-effect transistors. Nature. 413, 713--715. (2001).
• 20: H. Wang. Proving theorems by pattern recognition. II. Bell Systems Technical Journal, 40:1--42, (1961).
• 21: E. Winfree, X. Yang and N. Seeman, Universal Computation via Self-assembly of DNA: Some Theory and Experiments, Proceedings of the Second Annual Meeting on DNA Based Computers, Princeton University, June 10--12, (1996).
• 22: E. Winfree, F. Liu, L. Wenzler, N. Seeman. Design and self-assembly of two-dimensional DNA crystals, 6 pages. (Nature 394, 539--544 (Aug. 6, 1998) Article).
• 23: Erik Winfree , John J. Hopfield, Algorithmic self-assembly of dna, 1998
• 24: G. Whitesides, J. (MATH)ias and Christopher T. Seto. Molecular self-assembly and nanochemistry: a chemical strategy for the synthesis of nanostructures, Science, vol 254, p 1312--1319. Nov 1991.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Spline and piecewise polynomial approximation
      G.1.6 Optimization
          Subjects: Constrained optimization

General Terms:
Algorithms, Experimentation, Performance, Theory