Search methods for tile sets in patterned DNA self-assembly

DOI10.1016/J.JCSS.2013.08.003MaRDI QIDQ395021zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Mika Göös, Tuomo Lempiäinen, Eugen Czeizler, Pekka Orponen

Publication date 28 January 2014

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

tile assembly modelDNA self-assemblytilingspattern assemblyreliable self-assemblytile set synthesis

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Protein sequences, DNA sequences (92D20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Tilings in (2) dimensions (aspects of discrete geometry) (52C20)

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

Recommendations

• Synthesizing Minimal Tile Sets for Patterned DNA 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
• Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly
• Computing minimum tile sets to self-assemble color patterns

Cites work

• scientific article; zbMATH DE number 3968590 (Why is no real title available?)
• Algorithm portfolios
• Combinatorial Optimization in Pattern Assembly
• On the best search strategy in parallel branch-and-bound: Best-first search versus lazy depth-first search
• Optimal speedup of Las Vegas algorithms
• Programmable control of nucleation for algorithmic self-assembly
• Synthesizing Minimal Tile Sets for 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
• The program-size complexity of self-assembled squares (extended abstract)

Cited in

(10)

• 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
• 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
• Design automation of polyomino set that self-assembles into a desired shape
• Synthesizing Minimal Tile Sets for Patterned DNA Self-assembly
• Computational modelling of the kinetic tile assembly model using a rule-based approach
• Tile-based modeling of DNA self-assembly for two graph families with appended paths
• A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis
• Tile-Based DNA Nanostructures

Describes a project that uses

Uses Software

• Smodels
• Gringo

This page was built for publication: Search methods for tile sets in patterned DNA self-assembly

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