基于DNA 自组装模型解决图的最小顶点覆盖问题

郭洪敏，殷志祥

(安徽理工大学理学院，安徽 淮南 232001)

基于DNA 自组装模型解决图的最小顶点覆盖问题

郭洪敏，殷志祥

(安徽理工大学理学院，安徽 淮南 232001)

在分析最小顶点覆盖问题特点的基础上，以5 个顶点的图为例，将最小顶点覆盖问题转化为可满足性问题，简化问题的操作难度。再根据DNA 自组装的自发性和并行性等优势，通过建立DNA 自组装模型解决可满足性问题，从而解决图的最小顶点覆盖问题。相对于传统算法，本算法只应用了凝胶电泳技术，大大的降低了操作难度和误差。

最小顶点覆盖；DNA 自组装模型；可满足性问题

在图论中，最小顶点覆盖(Minimum Vertex Cover Problem，MVCP)是一个著名的NP完全问题，在研究的各个方面都有着举足轻重的地位。然而，对于最小顶点覆盖问题的研究一直困扰着人们，近几年，人们仍然不断探索MVCP的求解方法。2004年，最小顶点覆盖问题的DNA分子算法[1]；2006年，最小顶点问题的闭环DNA算法[2]；2008年，最小顶点覆盖快速降阶算法[3]；2010年，最小顶点覆盖的竞争决策算法[4]等。这些方法使得对最小顶点覆盖问题的研究取得了一定的进展，但仍存在一定的不足。

1 DNA自组装模型

1994年，文献[5]首次利用DNA分子组装，成功的解决了7个节点的有向Hamilton问题，开创了DNA计算的新领域，产生了巨大的作用和影响。由于DNA计算具有强大的数据存储能力和并行计算能力等优点，得到了广大学者的关注和利用，并以此为基础创造了各种生物计算模型，其中DNA自组装模型就是其中一种。

DNA自组装是指在一定的温度，浓度，酶等条件下，一些带有输入信息的DNA分子，根据Watson-Crik互补配对原则，自组装生成新的带有输出信息的DNA分子的过程，具有高度的并行性。DNA自组装结构分为一维，二维，三维结构。1960年，文献[6]提出的瓦片理论开启了自组装DNA的大门。1990年，文献[7-8]运用改良的瓦片理论解决了很多复杂问题。此后，一维DNA自组装模型得到了广泛应用。1998年，文献[9]利用文献[6]的瓦片理论形成二维晶体结构。2008年，文献[10]利用DNA单链进一步自组装得到了不同的多面体结构。

2 DNA自组装模型的算法

2.1 最小顶点覆盖问题

在简单无向图G={V，E}中，V是图G的顶点集，E是图G的边集。设K是V(G) 的一个子集，若G的每条边都至少有一个顶点在K中，则称K是图G的一个覆盖。一个覆盖K是图G的最小顶点覆盖，是指如果图G中没有覆盖K′，使得|K′|<|K|(见图1)。

V={v1，v2，v3，v4，v5}

E={e1，e2，e3，e4，e5，e6，e7}

G的最小顶点覆盖为{v2，v5}，覆盖有：

K1={v1，v2，v5}

K2={v1，v2，v3，v5}

K3={v1，v2，v4，v5}

K4={v1，v2，v3，v4，v5}

K5={v2，v3，v5}

K6={v2，v4，v5}

K7={v2，v3，v4，v5}

2.2 最小顶点覆盖的基本解法

2.2.1 图的最小顶点覆盖问题的转化

当v2=v5=1，v1=v3=v5=0时，F=1；当v2=v5=1且∃vi=1(i=1，3，5)时，亦得F=1。由此可以把图的覆盖问题转化为可满足性问题，这样就大大的简化了问题的复杂程度。

2.2.2DNA自组装模型算法

不断重复上述步骤，找出析取范式中所有子句为真的组合。通过凝胶电泳，选择组合中最短的DNA链，最后检测读取问题的解，即可得到最小顶点覆盖。

3 实例分析

为了方便，以三个顶点的完全图为例(见图2)。

其析取范式为

F=(v1∨v2)∧(v1∨v3)∧(v2∨v3)。

表1 所有变量及其特殊补链编码

4 结论

利用DNA自组装模型解决最小顶点覆盖问题，整个过程最大的创新点在于将最小顶点覆盖问题转化为可满足性问题。在算法实现过程中，只用到了凝胶电泳技术，大大的简化了操作过程，降低了操作误差。

DNA自组装模型因其实现了实验过程的自发性和操作的简便性等特征，备受广大学者的青睐，并以此为基础解决了许多小规模的NP问题，例如最大团问题，图的着色问题，SAT问题等。随之研究的不断深入，DNA自组装模型在更广泛的领域的应用需要进一步被发现。

[1] 高琳，许进.最小顶点覆盖问题的DNA分子算法[J].系统工程与电子技术，2004，26(4)： 543-548.

[2] 周康，许进.最小顶点覆盖问题的闭环DNA算法[J].计算机工程与应用，2006，20(7)：7-9.

[3] 宁爱兵，马良，熊小华.最小顶点覆盖快速降阶算法[J].小型微型计算机系统，2008，29(7)：1 282-1 285.

[4] 金婷婷，王波，宁爱兵.最小顶点覆盖文体的竞争决策算法[J].计算机工程与应用，2011，47(1)：32-34.

[5]LMADLEMAN.Molecularcomputationofsolutiontocombinatorialproblems[J].Science， 1994，266(11)：1 021-1 024.

[6]WANGH.DominoesandtheAEAcaseofthedecisionprob1em[C]//ProceedingsoftheSymposiumintheMathematicalTheoryofAutomata.Brooklyn，1962.NY：Polytechnic.

[7]FUTJ，SEEMANNC.Biochem，DNAdoublecrossovermolecules[J].Biochemistry，1993，32(13)：3 211-3 220.

[8]SEEMANNC.DNAnanotethnology：NovelDNAconstruetions[J].AnnualReviewofBiophysicsandBiomohicularStrucure，1998，27：225-248.

[9]WINFREEERIKETAL.Designandself-assemblyoftwo-dimensionalDNAcrystals[J].Nature，1998，394：539-544.

[10]HEYU，MAOCHENG-DEETAL.Hierachicalself-assemblyofDNAintosymmetricsupramolecularpolyhedra[J].Nature，2008，452：198-202.

[11]YOUWEIFU，LEIWU.ThreeKeyStepsinSolidPhasePeptideSynthesis[J].ChemicalIndustryandEngineering，2010，27(4)： 370-375.

(责任编辑：何学华，吴晓红)

Minimum Vertex Cover Problem Solution Based On Self-assembly Model of DNA

GUO Hong-ming , YIN Zhi-xiang

(School of Science, Anhui University of Science and Technology, Huainan Anhui 232001, China)

On the basis of analysis of the characteristics of the minimum vertex cover problem, taking a graph with 5 vertices as an example the minimum vertex cover problem was transformed into a problem of satisfiability, to simplify the operation of the problem.Then according to spontaneity and parallelism of DNA self-assembly and other advantages, by establishing self-assembly model of DNA the satisfiability problem was solved. Thus the minimum vertex cover problem was solved. Compared with the traditional algorithm, in the studied algorithm only gel electrophoresis technology is applied, which greatly reduces the difficulty of the operation and error.

minimum vertex cover problem; DNA self-assembly model; satisfiability problem

2014-12-01

国家自然科学基金资助项目(61170172)

郭洪敏(1992-)，女，安徽合肥人，在读硕士，研究方向：DNA计算、图论等。

O157.5

A

1672-1098(2015)03-0017-04