最大匹配问题Tile自组装模型摘要：Tile自组装模型凭借其自组装、可编程等特性在解决NP问题方面具有巨大优势.文中提出了一种求解最大匹配问题的Tile自组装新模型，该模型主要由初始配置子系统、选择子系统及检测子系统3大部分构成.新模型中首先设计Tile分子存储问题信息，其次通过Tile分子自组装操作生成最大匹配问题解空间，最后通过Tile检测分子筛选得到最大匹配问题的解.对模型从所需Tile分子种类、计算时间和计算空间3个方面进行性能分析，并通过实验模拟论证了模型的有效性和正确性.关键词：DNA计算；Tile自组装模型；最大匹配问题；NP完全问题；并行计算：TP301.6文献标识码：A1994年，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].图的最大匹配的DNA计算算法已有相当研究[11-12].然而文献[11]中提出的算法基于表面模型、文献[12]中提出算法基于粘贴模型，此两种模型均很难克服实验操作难度较大，需要大量的人工干预的缺点.此外，从公开发表的刊物看，关于最大匹配问题Tile自组装模型的研究还比较少.为此，本文对最大匹配问题Tile自组装模型进行了较深入的探索.主要工作如下：1）提出了一种最大匹配问题Tile自组装模型，该模型主要由初始配置子系统、选择子系统及检测子系统3大部分构成.2）从所需Tile分子种类、计算时间和计算空间3个方面进行性能分析，并通过对算法进行实例模拟，进一步验证模型及算法的正确性和有效性.1Tile自组装模型1.1Tile分子的结构基于Wang的Tile理论，1998年Winfree提出了一种Tile自组装数学模型又称为Tile自组装模型[4].Tile自组装模型中的Tile分子可以通过不同的DNA编码来构建.如图1所示，每个Tile分子可以抽象成为带有标签的四边形，每个标签可以识别不同的粘性末端.若两个不同的Tile分子的两个粘性末端互补，两个互补的粘性末端通过碱基互补配对连接进行Tile分子的自组装.本文将Tile分子定义为5元组.Tile分子分别通过North，South，West，East4个粘性末端存储信息，其中Value用来表示Tile分子代表的值（如图1）.1.2相关生物操作本文模型在自组装模型中的基本生物操作如退火，连接，荧光标记及凝胶电泳操作的基础上，引入了Adleman-Lipton模型中抽取，检测，读取等生物操作，具体描述见文献[12].1.3扩展的Tile自组装模型的抽象描述对传统Tile自组装模型进行扩展[4].扩展后的Tile自组装模型定义为5元组，其中g，t及Configuratio定义见文献[9]，而TileSet及BioOperations定义如下：.2最大匹配问题Tile自组装模型2.1问题描述2.2最大匹配问题Tile自组装模型本文的最大匹配问题Tile自组装模型主要分为初始配置子系统，选择子系统和检测子系统3个部分.2.2.1初始配置子系统初始配置基本Tile分子抽象结构如图3所示.生成大量如图3所示的初始配置Tile分子后，将通过本节的初始配置子系统生成最大匹配问题的初始配置.2.2.2选择子系统基于2.2.1节中初始配置，通过本节的选择子系统基本Tile分子将生成最大匹配问题的初始解空间配置.选择子系统所需的基本Tile分子如图4所示.2.2.3检测子系统根据最大匹配问题的定义及Tile分子的基本生物特性，本节中设计了用于检测的Tile分子类型（如图5）.2.3性能分析本节将从所需Tile分子种类、计算时间及计算空间3个方面分析算法的性能.引理1Tile分子种类，计算时间和计算空间：本文提出的最大匹配问题Tile自组装高效模型中，...