Synthesizing small and reliable tile sets for patterned DNA self-assembly

Tuomo Lempiäinen, Eugen Czeizler, Pekka Orponen

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

10 Citations (Scopus)
27 Downloads (Pure)


We consider the problem of finding, for a given 2D pattern of colored tiles, a minimal set of tile types self-assembling to this pattern in the abstract Tile Assembly Model of Winfree (1998). This Patterned self-Assembly Tile set Synthesis (PATS) problem was first introduced by Ma and Lombardi (2008), and subsequently studied by Goos and Orponen (2011), who presented an exhaustive partition-search branch-and-bound algorithm (briefly PS-BB) for it. However, finding the true minimal tile sets is very time consuming, and PS-BB is not well-suited for finding small but not necessarily minimal solutions. In this paper, we modify the basic partition-search framework by using a heuristic to optimize the order in which the algorithm traverses its search space. We find that by running several parallel instances of the modified algorithm PS-H, the search time for small tile sets can be shortened considerably. We also introduce a method for computing the reliability of a tile set, i.e. the probability of its error-free self-assembly to the target tiling, based on Winfree's analysis of the kinetic Tile Assembly Model (1998). We present data on the reliability of tile sets found by the algorithms and find that also here PS-H constitutes a significant improvement over PS-BB.

Original languageEnglish
Title of host publicationDNA Computing and Molecular Programming - 17 th International Conference, DNA 17, Pasadena, CA, USA, September 19-23, 2011. Proceedings
EditorsLuca Cardelli, William Shih
Place of PublicationBerlin Heidelberg
Number of pages15
Publication statusPublished - 2011
MoE publication typeA4 Article in a conference publication
EventInternational Conference on DNA Computing and Molecular Programming - Pasadena, United States
Duration: 19 Sep 201123 Sep 2011
Conference number: 17

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


ConferenceInternational Conference on DNA Computing and Molecular Programming
Abbreviated titleDNA
Country/TerritoryUnited States


  • branch-and-bound algorithm
  • DNA self-assembly
  • PATS problem
  • tilings


Dive into the research topics of 'Synthesizing small and reliable tile sets for patterned DNA self-assembly'. Together they form a unique fingerprint.

Cite this