基于DNA计算的最大权团问题设计

张喆++殷志祥

摘要：介绍了最大团和最大权团的概念和国内外学者运用DNA计算解决最大团的研究成果；结合前人运用质粒、二进制、粘贴模型等方式进行DNA计算操作的原理，设计了新的用于解决最大权团问题的算法步骤，大大提高了算法效率，实现了最大团和最大权团的同步求解，对市场分析、方案选择等领域有一定的意义。

关键词：DNA计算；质粒；粘贴模型；最大权团；凝胶电泳

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

文章编号：1672-1098（2015）01-0075-03

对于给定的无向图G=（V，E）。如果UV，且对任意u，v∈U有（u，v）∈E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。而最大权团，就是指权值最大的最大团。

1994年，文献[1]提出了用DNA分子解决7节点的Hamilton路径问题，这是有关DNA计算的开山之作。之后文献[2]在Adleman思想的启发下，通过构造一个接触网络图G，将可满足性问题（SAT）的解空间，映射成通过接触网络G的始点到终点的所有Hamilton路径，然后对有向图中的顶点和边进行编码，用DNA计算解决了3—变量的可满足性问题。1997年，文献[3]提出了用DNA计算求解最大环问题的方法，为DNA计算解决NP问题提供了又一佐证。2000年，文献[4]提出了在固体表面进行DNA计算的方法，改变了过去在试管溶液中进行DNA计算的生物操作的方法，进一步提高了DNA计算的可靠性和效率，近些年，文献[5]2009年解决了闭环求解最大团问题的算法；文献[6]于2010年解决了基于粘贴模型的最大团问题算法；文献[7]于2011年结合Aunp自组装聚合色变与DNA计算相结合，构建了系列基本逻辑计算模型；……