DNA计算在二次分配问题中的应用研究

DNA计算在二次分配问题中的应用研究吕聪颖赵刚彬邵艳玲郑珂吕冠廷（吉林大学计算机科学与技术学院，长春130012）E-mail:[e-mail]摘要：DNA计算（DNAcomputing）是一种新的计算方法，其高度并行性和巨大的信息存储能力为NP－完全问题的解决提供了一种全新的方法。本文采用了该算法去解决二次分配问题（QAP），构造了该问题的表达方法，建立了该问题的算法模型。本文应用DNA计算的方法去解决QAP问题是一种崭新的尝试，它对于我们将DNA计算的方法应用于组合优化问题无疑具有启发性，并为我们进一步深入研究奠定了基础。关键字：DNA计算、二次分配问题、凝胶电泳、聚合酶链式反应、亲和纯化中图分类号：TP31文献标识码：A文章编号：TheResearchofDNAAlgorithmforQAPCongyingLV，ZhezhouYU，ChunguangZhou，KangpingWang，WeiPang(InstituteofComputerScienceandTechnology,JilinUniversity,Changchun130012,P.R.China)Abstract：Inthispaper，wegiveabriefdescriptionoftherealizationmethodsofDNAcomputing,andthenuseaDNAcomputingtosolvethequadraticassignmentproblem，andproposeanovelpresentationfortheproblemandfoundamodelofthecomputing.It’sakindofbrand-newtrythatthepaperusesDNAcomputingtosolveQAPproblem.ItisundoubtedlyenlighteningtoapplytheDNAcomputingtotheothercombinationoptimizationproblems，anditwillestablishthefoundationoffurtherinvestigation。Keywords：DNAcomputing、quadraticassignmentproblem、GelElectrophoresis、polymerasechainreaction、affinityseparation1．引言二次分配问题[1]（quadraticassignmentproblem,简称QAP）是一种典型的组合优化问题，已被归入NP－hard问题。该问题的描述如下：给定n个设施和n个地点，要求给每个设施分配一个位置；定义两个n*n矩阵，即A=（fij）和B＝(dij),其中fij表示设施i和设施j之间的流量，dij表示地点i和地点j之间的距离。目标是找到一个排序P=(P1,P2,…Pn)使其：Minimize()()11()nnijLiLjijCpfd其中L(i)表示设施i被分配的地点，P∈∏(n)。目前，该问题已经得到深入的研究，进化策略(evolutionstrategies)、遗传算法(geneticalgorithms)、遗传规划(geneticprogramming)、进化规划(evolutionaryprogramming)等统称为进化计算[2](evolutionarycomputation)的方法以及蚂蚁算法等为该问题的求解提供了独特的思路。DNA计算[2]是一门新的学科。这门学科主要研究如何利用DNA分子根据Watson-Crick互补配对原则进行极度并行计算的特点去解决人类数学中的问题。目前已验证有大量的问题可以通过DNA计算来解决。最早的，也是最著名的是1994年Science上发表的美国科学家Adleman的七节点Hamilton路径问题的DNA计算解决办法。此外，2001年11月22日Nature杂志上关于威兹曼实验室制造出自动DNA计算机的报道，再一次向世人证明了DNA分子具有强大的计算能力。在先前的研究启示下，本文尝试着用DNA计算的方法去解决QAP问题，它对于我们将DNA计算方法应用于其它的组合优化问题无疑具有启发性，并为我们进一步深入研究奠定了基础。2．DNA计算概述2．1DNA计算的关键过程DNA计算解决问题的基本思想[2]：利用DNA特殊的双螺旋结构和碱基互补配对原则对问题进行编码，将所要处理的对象映射成DNA分子链，在DNA溶液的试管里，在生物酶的作用下，通过可控的生化反应生成问题的解空间。最后，利用分子生物技术如：聚合酶链式反应PCR、亲和纯化、凝胶电泳和磁珠分离等，破获运算结果。2．2DNA计算的数学机理DNA的单链可看作由4个不同符号A、G、C和T组成的串，不难发现，如果给这四个元素分配一个如下所述的二进制编码：T：＝00，A＝11，C＝01，G＝10能够很容易地实现DNA编码与二进制编码之间的相互转换并维持编码之间的互补性。在本实验构造的模型中，我们按照二进制的乘法（*）运算和加法（＋）运算规则对流量和距离进行了权值转换运算。3．DNA计算在二次分配问题中的应用研究基于DNA计算的突出优点，许多研究者都试图用它去解决大量的难题，尤其是NP问题。2004年，JiYounLee等人采用用DNA分子编码数值的方法成功地解决了7个城市的TSP问题[3]，在该方法的启示下，本文尝试着用DNA计算的方法来解决二次分配问题。本文采用的QAP实例为典型的Tail10b，来自。3．1编码策略LocationiCostlocationj5’-ACCCCAGTATCCCCTATATCATGATAGATATGTAGATTCCCCTGTCAACATTGACCCTCA-3’3’-GGGGATATAGTACTATCTATACATCTAAGGGGACAGTTGT-5’PartApartCpartBPermutationi→j图1：地点0到地点1之间的排序序列编码方案其中，权值Cost表示的是：地点i和地点j之间的距离与放在地点i和地点j的设施之间的流量的乘积,该过程采用了二进制的乘法（*）运算和加法(+)运算。排序序列包括了三个部分：地点i的序列(部分A),权值序列(部分C),地点j的序列(部分B)；排序序列的第一部分(3’-CCCCATATAG-5’)和地点i的序列（部分A）的第二部分(5’-GGGGTATATC-3’)是Watson-Crick互补的。排序序列的最后部分(3’-GGACAGTTGT-5’)和地点j的序列（部分B）的第一部分(5’-CCTGTCAACA-3’)是Watson-Crick互补的。排序序列的中间部分是权值信息，部分A和部分B作为地点i和j之间的连接器.3．2距离与流量的乘积到权值的映射由于本文设计的Cost序列表示的是流量和距离和乘积，因此，应根据具体实例给出的流量和距离值来决定每两个地点之间的Cost序列长度，本文假定：表示流量和距离的DNA序列长度不低于10个核苷酸，如果不足10，则补0。对它们进行二进制的乘法和加法运算来确定Cost序列。由于对两个10位的DNA序列进行二进制乘法操作，其乘积不大于20位。加上QAP标准问题的流量和距离的值均低于100，因此，我们可以设定Cost序列的长度为20个核苷酸。经过上述映射，QAP问题就被转化为TSP问题。我们可以采用解决TSP问题的方法来解决QAP问题。3．3算法的实现过程解决QAP的DNA计算的算法的步骤如下图所示：3．4相关的生物技术3．4．1聚合酶链式反应（PCR）反应的物质和条件：在反应液中含有模板DNA、人工合成的目的片段的5′端和3′端PCR引物、合成DNA的四种脱氧核苷酸底物（dNTP）、一种耐热的DNA聚合酶（Taq酶），以及含各种离子的缓冲液。Step1：产生初始池产生方法：在DNA和低聚核苷酸(表示城市,路径和权值)之间进行杂交和连接反应Step2：迭代过程判断当前迭代次数I是否大于iterations,若是，转step7ForI=0toiterations实现选择的方法：通过一系列生化反应：例如PCR、凝胶电泳和亲和纯化。对那些经过权值较小的路径通过PCR进行有选择性的增强。然后判断是否经过所有地点可以通过凝胶电泳和亲和纯化来检验。凝胶电泳检查开始路径的长度，亲和纯化检查是否所有的点都被访问到。Step3：选择那些满足能够成为候选解条件的路径Step4：更多的经济路径通过DTG-PCR被增强Step5：根据温度渐变凝胶电泳(TGGE)把最经济的路径分离出来Step6：一次迭代完毕，如果本次迭代产生的局部最好解优于当前的全局最好解，则用此局部最好解更新当前的全局最好解Step7：通过克隆和排序分离的DNA链把最终解读出标准的PCR过程：1.DNA变性（90℃-96℃）：双链DNA模板在热作用下，氢键断裂，形成单链DNA。2.退火（25℃-65℃）：系统温度降低，引物与DNA模板结合，形成局部双链。3.延伸（70℃-75℃）：在72℃时Taq酶（在72℃左右最佳的活性）可将dNTP从引物3′端开始掺入，沿模板DNA5′→3′方向延伸，合成与模板互补的DNA链。3．4．2凝胶电泳(GelElectrophoresis)将DNA序列放入凝胶溶液中并在凝胶的两端施加电场。在电场的作用下，带负电的DNA序列将向阳极移动，而较短的DNA序列将比较长的DNA序列移动得快，因为长度大的分子链受到凝胶的阻力大。因此，可用此技术去获取一定长度的DNA分子链，也可区分不同长度的DNA分子。使用特殊的化学物质和紫外光，可以看到各种不同长度的DNA序列停下来以后在凝胶溶液中形成得条带。3．4．3亲和纯化(affinityseparation)这种技术用来使某种含有特定的一小段序列的DNA单链从含有各种各样DNA单链的溶液中分离出来。具体做法是，首先合成这一特定小段序列的互补序列，让其附着在一个磁球上。接着将磁球放在溶液中，那些含有特定序列的DNA单链将退火结合到磁球上。然后把磁球取出后放入另一试管溶液中并加热，DNA单链就会与磁球分离，从而在试管中得到要求的DNA单链。3．4．4变性温度渐变（DTG－PCR）变性温度渐变PCR[3]是PCR方法的修改，该变性温度周期性地改变。在PCR的循环阶段初期，变性温度为70度。然后，该变性温度每周期增加1度，直到增加到95度，在剩下的循环中保持95度。其他的PCR条件与上面所述的一般的PCR条件相同。3．4．5温度渐变凝胶电泳（TGGE）对于温度渐变凝胶电泳[3]，它使用了包括百分之二甲酰胺和4.2M尿素的百分之八的变性聚丙烯酰酸凝胶。该过程在一个定制容器里进行，其条件为：温度大于55-70度，电压为200V，电泳现象进行3小时。电泳现象之后，凝胶被银污染。在主带中的DNA链被PCR切除、洗提和增强。该PCR产物被直接克隆。4．结论本文首次建立了DNA计算解决QAP问题的模型，无疑这是一次崭新的尝试，同时在DNA计算的编码理论方面获得了一些创新性的工作，这对于我们将DNA计算的方法应用于组合优化问题无疑具有启发性，并为我们进一步深入研究奠定了基础。在今后的工作中，我们应该对该模型进一步优化；另外，由于在实际的ＤＮＡ计算中，编码问题和模型设计经常联系在一起，编码问题是ＤＮＡ计算中的一个值得研究的重要问题，影响编码的因素很多。本文的编码是在忽略了某些因素的情况下所做，不能完全消除各种错误情况的发生。因此，在优化模型设计的同时，还应将编码方法不断的改进。参考文献[1].E.-G.Talbi,O.Roux,C.Fonlupt.ParallelAntColoniesforthequadraticassignmentproblem[J].FutureGenerationComputerSystems,2001,17:441~449.[2].殷志祥、董亚