Synthesizing minimal tile sets for patterned DNA self-assembly

Reference:

Mika Göös and Pekka Orponen. Synthesizing minimal tile sets for patterned DNA self-assembly. In Y. Sakakibara and Y. Mi, editors, Proceedings of the 16th Conference on DNA Computing and Molecular Programming (DNA16, Hong Kong, China, June 2010), volume 6518 of Lecture Notes in Computer Science, pages 71–82, Berlin Heidelberg, 2011. Springer-Verlag.

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.

Keywords:

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

Suggested BibTeX entry:

@inproceedings{GoOr11,
    address = {Berlin Heidelberg},
    author = {Mika Göös and Pekka Orponen},
    booktitle = {Proceedings of the 16th Conference on DNA Computing and Molecular Programming (DNA16, Hong Kong, China, June 2010)},
    editor = {Y. Sakakibara and Y. Mi},
    language = {eng},
    pages = {71--82},
    publisher = {Springer-Verlag},
    series = {Lecture Notes in Computer Science},
    title = {Synthesizing minimal tile sets for patterned {DNA} self-assembly},
    volume = {6518},
    year = {2011},
}