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

Reference:

Tuomo Lempiäinen, Eugen Czeizler, and Pekka Orponen. Synthesizing small and reliable tile sets for patterned DNA self-assembly. In L. Cardelli and W. Shih, editors, Proceedings of the 17th Conference on DNA Computing and Molecular Programming (DNA17, Pasadena CA, September 2011), volume 6937 of Lecture Notes in Computer Science, pages 145–159, Berlin Heidelberg, 2011. Springer-Verlag.

Abstract:

We consider the problem of finding, for a given 2D pattern of coloured 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 Göös 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 the algorithm 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 optimise 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. Additionally, we suggest a new approach, answer set programmin (ASP), to the PATS problem. We also introduce a method for computing the reliability of a given tile set, i.e. the probability of its error-free self-assembly to the desired target tiling, based on Winfree's analysis of the kinetic Tile Assembly Model (1998). We present empirical data on the reliability of tile sets found by the PS-BB and PS-H algorithms and find that also here the PS-H algorithm constitutes a significant improvement over the PS-BB method.

Keywords:

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

Suggested BibTeX entry:

@inproceedings{LeCO11,
    address = {Berlin Heidelberg},
    author = {Tuomo Lempiäinen and Eugen Czeizler and Pekka Orponen},
    booktitle = {Proceedings of the 17th Conference on DNA Computing and Molecular Programming (DNA17, Pasadena CA, September 2011)},
    editor = {L. Cardelli and W. Shih},
    language = {eng},
    pages = {145--159},
    publisher = {Springer-Verlag},
    series = {Lecture Notes in Computer Science},
    title = {Synthesizing small and reliable tile sets for patterned {DNA} self-assembly},
    volume = {6937},
    year = {2011},
}