Synthesis of Tile Sets for DNA Self-Assembly
Synthesis of Tile Sets for DNA Self-Assembly
复制标题
DOI：
10.1109/tcad.2008.917973
复制
发表时间：
2008-05
影响因子：
2.9
通讯作者：
Xiaojun Ma;F. Lombardi
中科院分区：
文献类型：
--
作者：
Xiaojun Ma;F. Lombardi
本文讨论的问题围绕着瓷砖集的DNA自组装作为一个有前途的方法，在纳米IC制造的合成。对于有限图案，最小化瓦片或键类型的合成等价于最小图着色问题，提出了两种减少合成瓦片集的瓦片数（PATS_Tile）或键数（PATS_Bond）的贪婪算法，并对这两种算法进行了评价。对于维数为l的正方形模式，这两个算法都是O（l4）的。仿真结果表明，如果两种类型的约简都必须完成，PATS_Tile具有更好的平均性能。
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 O(l4) 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.