Synthesizing minimal tile sets for patterned DNA self-assembly (2011)
AUTHORS:
Göös Mika,
Orponen Pekka
BOOKTITLE:
Proceedings of the 16th Conference on DNA Computing and Molecular Programming (DNA16, Hong Kong, China, June 2010)
SERIES:
Lecture Notes in Computer Science
VOLUME:
6518
PAGES:
71--82
URL:
http://dx.doi.org/10.1007/978-3-642-18305-8_7
@inproceedings{ GoOr11, editor = "Sakakibara, Y. and Mi, Y.", author = "Göös, Mika and Orponen, Pekka", volume = "6518", responsibleauthor = "Orponen, Pekka and Göös, Mika", language = "eng", title = "Synthesizing minimal tile sets for patterned {DNA} self-assembly", url = "http://dx.doi.org/10.1007/978-3-642-18305-8_7", series = "Lecture Notes in Computer Science", booktitle = "Proceedings of the 16th Conference on DNA Computing and Molecular Programming (DNA16, Hong Kong, China, June 2010)", publisher = "Springer-Verlag", corerank = "B", 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.", note = "", flags = "public HIIT", il = "no", year = "2011", keywords = "DNA self-assembly, tilings, PATS problem, branch-and-bound algorithm", unitcode = "T306=99, T312=1", impactfactor = "A4", pages = "71--82", address = "Berlin Heidelberg" }