基于分子信标的图的最小顶点覆盖问题.docx

基于分子信标的图的最小顶点覆盖问题摘要：生物芯片技术和DNA计算分别是近几年来生命科学与信息科学的新兴研究领域DNA计算在求解NP问题上存在着硅计算无法比拟的先天优越性。而图的最小顶点覆盖问题是图论中的一个重要问题目前还没有好的算法。在DNA计算和DNA计算芯片的基础上采用分子信标编码策略利用观察荧光来确定图的最小顶点覆盖问题的可行解。利用分子信标模型来解决图的最小顶点覆盖问题和其它DNA计算方法相比该方法操作起来更加方便。关键词：DNA计算；顶点覆盖；分子信标中图分类号：TP301文献标识码：A文章编号：16727800（2013）0030046030引言传统计算机的快速发展对解决一些问题起了很大的作用但是还存在不足之处如运算速度和存贮容量都不足以满足解决问题的需要。而且随着现代社会科学技术的不断进步和发展许多新的复杂疑难问题在不断出现如一些非线性问题和NP完全问题特别是在一些工程领域内电子计算机很难满足计算机发展的需要。为可以更好地解决这类问题科学界的人士努力寻找一种新型的计算方法。DNA分子存储遗传密码的能力非常强在生物酶的作用下可以呈现高度的并行性故以此为背景的DNA计算机也具有相应的特点。近些年来DNA计算很受科学领域的关注。它的进步之处不仅仅在于其存储量和运算速度的改善更重要的是它开发了本身潜在的计算能力。实践证明DNA计算机在计算速度和存储容量等方面确实有很大的进展。DNA计算的原理主要是在相应生物酶的作用下进行分离、结合、连接、测量、提取、扩增等一系列的操作来解决一些复杂疑难问题。使其运算时间达到多项式时间电子计算机却要达到指数时间。最早提出利用分子生物技术来解决NP完全问题的是美国加利福尼亚大学的Adleman教授突破了传统计算使分子生物计算方法得以问世。随后DNA计算领域的研究被科学家们高度重视。许多DNA计算模型被科学家们相继提出并用来解决了很多问题如图论中的可满足问题、邮递员问题、最小顶点覆盖问题、最大独立集问题等。国内关于DNA计算机的研究大体上经历了理论阶段和实践阶段。2001年我国对于DNA的研究还仅限于理论知识方面自2005年开始对DNA计算的研究开始进入实验阶段。为克服DNA计算中的一些不足一种将编码DNA序列固定在表面上进行操作的方法被广泛研究。最小顶点覆盖问题是图论中一个著名的NP完全问题。董亚飞等于2004年利用表面DNA计算的方法给出了最小顶点覆盖问题的DNA计算模型。此方法的优点是结合了图论中的基本结论增加了DNA计算的可操作性。2009年羊四清等利用基于表面的DNA计算采用荧光标记的策略将图的最小顶点覆盖问题转化为特殊的0-1规划问题有效地解决了图的最小顶点覆盖问题。由于分子信标作为生物芯片可以充分利用自身的优点：编码简单、耗材低、操作时间短、技术先进所以对于不同的组合优化问题可以将标有不同荧光分子的信标、不同识别区长度的分子信标、不同茎杆长度的分子信标通过生物素的形式固定到硅片的表面上制成分子信标片利用所构造的分子信标芯片实现问题的自动化求解过程。所谓分子信标是由圆形的识别区、茎杆和连接荧光剂与荧光淬灭分子的连接臂三个部分组成的其中识别区是由碱基序列组成。在分子信标茎杆的底部常常可以连接上荧光剂与荧光淬灭分子当茎杆被打开后会产生荧光。它是一种设计巧妙的核酸探针能将核酸序列结构信息转变为荧光信号具有很高的灵敏性与选择性。利用这一特性2007年殷志祥等人采用分子信标算法给出了0-1规划问题的一种新解法它具有编码简单、耗材低、操作时间短、技术先进等优点。本文在此基础上首先将图的最小顶点覆盖问题转化为特殊的0-1规划问题然后再结合求解0-1规划问题的最优解方法分子信标模型来解决图的最小顶点覆盖问题。分子信标技术的应用为图的最小顶点覆盖问题又提出了一个新的解决途径。1图的最小顶点覆盖问题下面给出图的最小顶点覆盖的基本定义：给定一个简单的无向图G=（VE）对于此图的一个子集K如果G的每一条边都至少有一个端点在K中那么K就是G的一个顶点覆盖；而且如果对于任何一个顶点V∈K则K-{V}就不可再构成一个顶点覆盖那么K就是G的一个极小顶点覆盖；进一步讨论如果在G中的任意子集K'都有|K'|≥|K|成立那么K就是G的最小顶点覆盖；G的顶点覆盖可以简称为G的覆盖。简而言之图的最小顶点覆盖也就是指对于一个具体的图找出一个最小顶点集使它可以覆盖图中的所有边。对于任意一个有n个顶点的图G可以用n位二进制数表示顶点的子集。用xi表示图中各顶点ei表示相对应的边。变量的下标对应于顶点的顺序。若二进制数的第i位值为1如xi=1i=12…n则表示vi存在于该最小顶点覆盖中；反之如果二进制数的第i