Manuch Ján, Stacho Ladislav, Stoll Christine
Department of Computer Science, University of British Columbia, Vancouver, BC, Canada.
J Comput Biol. 2010 Jun;17(6):841-52. doi: 10.1089/cmb.2009.0067.
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 x N square (a square where there is a bond between any two adjacent tiles) at temperature 1 requires N(2) distinct tile types, and conjectured that the minimum number of tile types needed to self-assemble an N x N square (not a full square) is 2N - 1. Our lower bounds imply that a tile system that uniquely assembles an N x N square without binding domains mismatches, requires at least 2N - 1 tile types.
利用由罗特蒙德（Rothemund）和温弗里（Winfree）提出的瓦片组装模型，在不存在绑定域不匹配（任意两个相邻瓦片要么形成键合，要么两个瓦片接触的面都没有胶水）这一自然假设下，我们给出了在温度为1时唯一组装一个形状所需的最少瓦片类型数量的两个下限。罗特蒙德和温弗里表明，在温度为1时唯一组装一个完整的N×N正方形（任意两个相邻瓦片之间存在键合的正方形）需要N(2)种不同的瓦片类型，并推测自我组装一个N×N正方形（非完整正方形）所需的最少瓦片类型数量为2N - 1。我们的下限意味着，一个能唯一组装一个不存在绑定域不匹配的N×N正方形的瓦片系统，至少需要2N - 1种瓦片类型。
