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

《DNA计算在二次分配问题中的应用研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DNA计算在二次分配问题中的应用研究吕聪颖赵刚彬邵艳玲郑珂吕冠廷（吉林大学计算机科学与技术学院，长春130012）E-mail:lvcongying0601@126.com摘要：DNA计算（DNAcomputing）是一种新的计算方法，其高度并行性和巨大的信息存储能力为NP－完全问题的解决提供了一种全新的方法。本文采用了该算法去解决二次分配问题（QAP），构造了该问题的表达方法，建立了该问题的算法模型。本文应用DNA计算的方法去解决QAP问题是一种崭新的尝试，它对于我们将DNA计算的方法应用于组合优化问题无疑具有启发性，并为我们进一步深入研究奠定了基础。

2、关键字：DNA计算、二次分配问题、凝胶电泳、聚合酶链式反应、亲和纯化中图分类号：TP31文献标识码：A文章编号：TheResearchofDNAAlgorithmforQAPCongyingLV，ZhezhouYU，ChunguangZhou，KangpingWang，WeiPang(InstituteofComputerScienceandTechnology,JilinUniversity,Changchun130012,P.R.China)Abstract：Inthispaper，wegiveabriefdescriptionoftherealiz

3、ationmethodsofDNAcomputing,andthenuseaDNAcomputingtosolvethequadraticassignmentproblem，andproposeanovelpresentationfortheproblemandfoundamodelofthecomputing.It’sakindofbrand-newtrythatthepaperusesDNAcomputingtosolveQAPproblem.ItisundoubtedlyenlighteningtoapplytheDNAcomputingtothe

4、othercombinationoptimizationproblems，anditwillestablishthefoundationoffurtherinvestigation。Keywords：DNAcomputing、quadraticassignmentproblem、GelElectrophoresis、polymerasechainreaction、affinityseparation1．引言二次分配问题[1]（quadraticassignmentproblem,简称QAP）是一种典型的组合优化问题，已被归入NP－hard问题。该问题的描

5、述如下：给定n个设施和n个地点，要求给每个设施分配一个位置；定义两个n*n矩阵，即A=（fij）和B＝(dij),其中fij表示设施i和设施j之间的流量，dij表示地点i和地点j之间的距离。目标是找到一个排序P=(P1,P2,…Pn)使其：Minimize其中L(i)表示设施i被分配的地点，P∈∏(n)。目前，该问题已经得到深入的研究，进化策略(evolutionstrategies)、遗传算法(geneticalgorithms)、遗传规划(geneticprogramming)、进化规划(evolutionaryprogramming)等统称为进化计

6、算[2](evolutionarycomputation)的方法以及蚂蚁算法等为该问题的求解提供了独特的思路。DNA计算[2]是一门新的学科。这门学科主要研究如何利用DNA分子根据Watson-Crick互补配对原则进行极度并行计算的特点去解决人类数学中的问题。目前已验证有大量的问题可以通过DNA计算来解决。最早的，也是最著名的是1994年Science上发表的美国科学家Adleman的七节点Hamilton路径问题的DNA计算解决办法。此外，2001年11月22日Nature杂志上关于威兹曼实验室制造出自动DNA计算机的报道，再一次向世人证明了DNA分

7、子具有强大的计算能力。在先前的研究启示下，本文尝试着用DNA计算的方法去解决QAP问题，它对于我们将DNA计算方法应用于其它的组合优化问题无疑具有启发性，并为我们进一步深入研究奠定了基础。1．DNA计算概述2．1DNA计算的关键过程DNA计算解决问题的基本思想[2]：利用DNA特殊的双螺旋结构和碱基互补配对原则对问题进行编码，将所要处理的对象映射成DNA分子链，在DNA溶液的试管里，在生物酶的作用下，通过可控的生化反应生成问题的解空间。最后，利用分子生物技术如：聚合酶链式反应PCR、亲和纯化、凝胶电泳和磁珠分离等，破获运算结果。2．2DNA计算的数学机理

8、DNA的单链可看作由4个不同符号A、G、C和T组成的串，不难发现，如果给这四个元