Synthesis of tile sets for DNA self-assembly
This paper addresses the issues revolving around the synthesis of tile sets for DNA self-assembly as a promising approach for IC manufacturing in the nanoscale. As for a finite pattern, synthesis for minimizing tile or bond types is equivalent to a minimum graph coloring problem, two greedy algorithms that reduce the number of tiles (PATS-Tile) or bonds (PATS-Bond) in synthesized tile sets are proposed and evaluated. Both algorithms are 0(14) for a square pattern of dimension l. It is shown by simulation that PATS-Tile has a better average performance if both types of reduction must be accomplished.
tile set dna self-assembly nanoscale manufacturing tile synthesis