最大匹配问题Tile自组装模型
2015-04-20周旭等
周旭等
摘要：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].
图的最大匹配的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元组
粘性末端存储信息，其中Value用来表示Tile分子代表的值（如图1）.
1.2相关生物操作
本文模型在自组装模型中的基本生物操作如退火，连接，荧光标记及凝胶电泳操作的基础上，引入了Adleman-Lipton模型中抽取，检测，读取等生物操作， 具体描述见文献[12].
1.3扩展的Tile自组装模型的抽象描述
对传统Tile自组装模型进行扩展[4].扩展后的Tile自组装模型定义为5元组
.
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自组装高效模型中，需要的Tile分子种类为O（m2）， 计算时间为O（m），计算空间为O（m2）.
证本文模型主要由初始配置子系统、选择子系统及检测系统3个部分组成.其中初始配置子系统中需要Tile分子种类为2m+4； 选择子系统中所需的Tile分子种类为2m+1；检测系统中所需的Tile分子种类数为共为8m2-2m+2.综上分析可知本模型中所需Tile分子种类数为O（m2）；其次计算时间即自组装体的深度，本文模型中自组装体的深度为m+2，因而计算时间复杂度为O（m）；最后空间复杂度即Tile自组装体的面积，本文模型中自组装体的最大面积为（m+2）×（m+2），因而计算空间复杂度为O（m2）.
证毕.
2.4实验模拟
为了验证算法的正确性，借鉴文献[7]中的实验方法.以图G为最大匹配问题的实例.
2.4.1Tile分子编码
以下将针对本文模型中的初始配置子系统，选择子系统及检测子系统3个部分，分别设计基本Tile分子：
2.4.2求解过程
本文模型中的算法步骤可以分为Tile分子生成阶段、初始配置生成阶段、选择阶段、检测阶段和解的获取5个部分，具体求解过程如下：
3结论
随着生物技术的进步， DNA计算中的Tile自组装模型凭借其自组装，可编程等特性而得到广泛关注.然而， 据我们所知，现今公开发表的刊物上还未有关于最大匹配问题的DNA Tile自组装模型的研究.为此，本文首先提出了一种最大匹配问题的Tile自组装有效模型，模型主要分为初始配置子系统，选择子系统及检测子系统3大部分；其次基于提出的模型，设计了相关算法，并分析了算法的性能，通过算法模拟证明算法的正确性及有效性.
参考文献
[1]ADLEMAN L M. Molecular computation of solutions to combinatorial problems [J]. Science， 1994， 266（11）： 1021- 1024.
[2]CHANG W L. Fast parallel DNAbased algorithm for molecular computation： Quadratic congruence and factoring integers [J]. IEEE Transaction on Nanobioscience，2012， 11（1）： 62-69.
[3]LI D F， LI X R， HUANG H T，et al. Scalability of the surfacebased DNA algorithm for 3SAT [J]. BioSystems， 2006， 85（2）： 95-98.
[4]WINFREE E. Algorithmic selfassembly of DNA [D]. Pasadena： California Institute of Technology， 1998.
[5]杨静， 张成. DNA自组装技术的研究进展及难点[J]. 计算机学报， 2008， 31（12）： 2138-2148.
YANG Jin， ZHANG Chen. Progress and difficulty in DNA selfassembly technology [J]. Chinese Journal of Computers， 2008， 31（12）：2138-2148. （In Chinese）
[6]ZHAO J， QIAN L L， LIU Q， et al. DNA addition using linear selfassembly[J]. Chinese Science Bulletin， 2007， 52（11）： 1462-1467.
[7]BRUN Y. Solving NPcomplete problems in the tile assembly model [J]. Theoretical Computer Scienee，2008， 395（l）： 31- 46.
[8]张勋才，牛莹，崔光照，等.基于自组装DNA计算的NTRU密码系统破译方案[J].计算机学报，2008， 31（12）：2129-2137.
ZHANG Xuncai， NIU Yin， CUI Guangzhao， et al. Breaking the NTRU public key cryptosystem using selfassembly of DNA tilings [J]. Chinese Journal of Computers， 2008， 31（12）：2129-2137. （In Chinese）
[9]方习文，来学嘉.基于线性自组装的DNA减法模运算[J].科学通报， 2010，55（10）：957-963.
FANG Xiwen， LAI Xuejia. DNA modular subtraction algorithm based on linear selfassembly[J]. Chinese Science Bull， 2010， 55（10）： 957-963. （In Chinese）
[10]周炎涛， 李肯立，罗兴，等.一种基于DNA自组装模型求解最大团问题的算法[J]. 湖南大学学报：自然科学版， 2012， 39（9）： 39-44.
ZHOU Yantao， LI Kenli，LUO Xing， et al.An algorithm for solving maximum clique problem based on selfassembly model of DNA[J]. Journal of Hunan University：Natural Sciences，2012， 39（9）： 39-44. （In Chinese）
[11]陈治平， 李小龙， 王雷，等. 最佳匹配问题的DNA表面计算模型[J].计算机研究与发展， 2005， 42（7）：1241-1246.
CHEN Zhiping， LI Xiaolong， WANG Lei， et al. A surfacebased DNA algorithm for the perfect matching problem[J]. Journal of Computer Research and Development， 2005， 42（7）：1241-1246.（In Chinese）
[12]周旭， 李肯立， 乐光学， 等.一种最大匹配问题的DNA计算算法[J].计算机研究与发展， 2011，48（11）：2147-2154.
