Synthesizing Minimal Tile Sets for Patterned DNA Self-assembly

DOI10.1007/978-3-642-18305-8_7MaRDI QIDQ3070963zbMATH OpenOpenAlexFDO

Authors Mika Göös, Pekka Orponen

Publication date 28 January 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0911.2924

Mathematics Subject Classification ID

Data structures (68P05) Combinatorics in computer science (68R05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Nonnumerical algorithms (68W05)

Abstract: 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.

Recommendations

• Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly
• Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly
• Synthesizing small and reliable tile sets for patterned DNA self-assembly
• Search methods for tile sets in patterned DNA self-assembly
• Programming Self-Assembly of DNA Tiles
• Design formalism for DNA self-assembly of polyhedral skeletons using rigid tiles
• scientific article; zbMATH DE number 7675553
• Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced tile assembly model
• Optimizing tile concentrations to minimize errors and time for DNA tile self-assembly systems

Cites work

• Combinatorial optimization problems in self-assembly
• Strict self-assembly of discrete Sierpinski triangles
• Synthesizing Minimal Tile Sets for Patterned DNA Self-assembly
• The program-size complexity of self-assembled squares (extended abstract)

Cited in

(17)

• On stoichiometry for the assembly of flexible tile DNA complexes
• 3-color bounded patterned self-assembly
• One-dimensional staged self-assembly
• An introduction to tile-based self-assembly and a survey of recent results
• Programming Self-Assembly of DNA Tiles
• Synthesizing Minimal Tile Sets for Patterned DNA Self-assembly
• One-dimensional staged self-assembly
• Synthesizing small and reliable tile sets for patterned DNA self-assembly
• Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly
• Search methods for tile sets in patterned DNA self-assembly
• Tile-Based DNA Nanostructures
• 3-color bounded patterned self-assembly (extended abstract)
• Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly
• Optimization of supply diversity for the self-assembly of simple objects in two and three dimensions
• Design automation of polyomino set that self-assembles into a desired shape
• Tile-based modeling of DNA self-assembly for two graph families with appended paths
• scientific article; zbMATH DE number 7714502 (Why is no real title available?)

This page was built for publication: Synthesizing Minimal Tile Sets for Patterned DNA Self-assembly

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3070963)