周旭等

摘要：Tile自组装模型凭借其自组装、可编程等特性在解决NP问题方面具有巨大优势.文中提出了一种求解最大匹配问题的Tile自组装新模型，该模型主要由初始配置子系统、选择子系统及检测子系统3大部分构成.新模型中首先设计Tile分子存储问题信息，其次通过Tile分子自组装操作生成最大匹配问题解空间，最后通过Tile检测分子筛选得到最大匹配问题的解.对模型从所需Tile分子种类、计算时间和计算空间3个方面进行性能分析，并通过实验模拟论证了模型的有效性和正确性.

关键词：DNA计算； Tile自组装模型； 最大匹配问题； NP完全问题； 并行计算

中图分类号：TP301.6 文献标识码：A

1994年，Adleman提出了DNA计算模型[1].此后，DNA计算以其具有的海量存储能力，巨大并行性及低能耗等特点，得到科学界的广泛关注.随着DNA计算的发展， 众多DNA计算模型被提出，主要有：粘贴DNA计算模型[2]，表面计算模型[3]，自组装模型[4]等.以上模型中，自组装模型以其自治性及纳米特性等优势，成为当前最具应用潜力的DNA计算模型之一[5].

随着生物技术的不断进步，Tile自组装模型自提出以来，得到了飞速的发展.Winfree基于Wang的Tile理论提出Tile自组装模型[4]；Zhao等人提出了基于线性自组装的DNA加法算法[6]； Brun提出了基于Tile自组装的子集和问题算法[7]；张勋才等人提出了一种基于自组装DNA计算的NTRU密码系统破译方案[8]；方习文等人基于线性自组装模型提出了DNA减法模运算算法[9]；周炎涛等人基于DNA自组装模型提出了一种求解最大团问题的算法[10].

图……