Two lower bounds for self-assemblies at temperature 1

摘要：

Using the Tile Assembly Model proposed by Rothemund and Winfree, we give two lower bounds on the minimum number of tile types needed to uniquely assemble a shape at temperature 1 under a natural assumption that there are no binding domain mismatches (any two adjacent tiles either form a bond or else both touching sides of the tiles are without glues). Rothemund and Winfree showed that uniquely assembling a full N×N square (a square where there is a bond between any two adjacent tiles) at temperature 1 requires N2 distinct tile types, and conjectured that the minimum number of tile types needed to self-assemble an N×N square (not a full square) is 2N -1.Our lower bounds imply that a tile system that uniquely assembles an N×N square without binding domains mismatches, requires at least 2N-1 tile types.

作者: Jan Manuch Ladislav Stacho Christine Stoll

作者单位: School of Computing Science,Simon Fraser University,8888 University Drive,Burnaby BC V5A 1S6,Canada Department of Mathematics,Simon Fraser University,8888 University Drive,Burnaby BC V5A 1S6,Canada

会议类型: 国际会议

会议名称: The 3rd International Conference on Bioinformatics and Biomedical Engineering(iCBBE 2009)(第三届生物信息与生物医学工程国际会议)

会议地点: 北京

会议语种:英文

页码: 1-4

在线出版日期: 2009-06-11（万方平台首次上网日期，不代表论文的发表时间）