Hamilton圈问题的分子信标检测模型

沙　莎，殷志祥

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



Hamilton圈问题的分子信标检测模型

沙莎，殷志祥

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

摘要：为了利用DNA 计算求解图论中经典问题和开发新的分子结构，根据分子信标中荧光分子-猝灭分对选择的不同可构成多色分子信标的原理，给出Hamilton圈这一NP‐完全问题的解的检测模型。该模型具有编码简单、低复杂度、易于检测等优点。

关键词：DNA 计算；分子信标；NP‐完全问题；Hamilton圈

1994年，文献[1]首次在实验室用DNA分子解决了一个含有7个城市的Hmilton有向路问题，自此，诞生了一个新的研究领域——DNA计算。1996年，文献[2]首次建立分子信标(molecularbeacon，MBs)探针，其作为一种新型的荧光探针在近年来得到广泛的应用和发展[3-6]。

继Adleman博士的著名实验之后，有关Hmilton路的一些其他问题的DNA计算也取得了一些进展[7-8]。除了在电子计算机和DNA计算机上的算法研究外，部分学者还在理论上对Hmilton问题进行了一定的讨论[9]。通过选择不同的荧光分子-猝灭分子对可以设计出不同荧光的分子信标(称多色分子信标)，每个分子信标与其各自的靶标序列杂交后，会释放不同颜色的荧光，此时，通过荧光检测系统检测不同的颜色来解决问题，这样可以使多个靶核苷酸同时定量测定且加以区别，本文基于上述原理设计了一个Hmilton圈问题解的检测模型。

关于Hmilton问题的部分数学描述如下：包含图G的每个顶点的路称为G的Hmilton路；包含图G的每个顶点的圈称为G的Hmilton圈；一个图包含HaInilton圈，则称这个图是Hmilton图。对于n阶图G，如果G含长度是n的圈，则称G是Hamilton图[10]。Hmilton圈问题是图论最古老的研究课题之一，是至今未解决的世界难题，在许多领域有着重要应用，同时，它也是一个典型的NP-完全问题。

1分子信标原理

分子信标是一种设计巧妙的新型荧光探针，主要由环和茎杆部分组成。环上的寡聚核苷酸序列是分子信标的基因识别区，它能与靶基因自发地进行杂交；茎部是一段5～8mer序列互补的发夹结构。在分子信标的5’端和3’端通过连接臂连接上荧光素和猝灭剂。一般用EDANS(1一氨基萘一8一羧酸)为荧光素，用DABCYL(二甲氨基偶氮苯甲酰)为猝灭剂(见图1)。当茎杆部分解链后“发夹”就会打开从而变成单链分子。在原始状态下，分子信标呈茎环结构，当荧光分子与猝灭分子靠近(约为7～10 nm)，即可发生荧光共振能量转移，此时，荧光分子发出的荧光被猝灭分子吸收并以热的形式散发，检测不到荧光信号。分子信标的工作原理如图2所示，当有靶序列存在时，分子信标的环部即可与靶序列特异性结合，形成的双链比分子信标的茎环结构更稳定，荧光分子与猝灭分子分开，荧光分子发出的荧光不能被猝灭分子吸收，这时可检测到荧光，且所检测到的荧光强度与溶液中靶标的量成正比。本模型利用金属纳米簇作猝灭剂，通过调节金属簇的大小、形状和组成而得到不同种的荧光，形成多色分子信标用于同时定量标记。

图1　典型分子信标结构

图2　分子信标工作原理

2问题描述

设无向图G=(V，E)，其中V是顶点集，E是边集。V={v0，v1，v2，…，vn-1}，E={eij|vi，vj∈V∧vi与vj相连(0≤i，j≤n-1，i≠j)}。目标是寻找以v0为起始点的Hamilton圈。假设以v0为起点，vn-1为终点。

例如，图G=(V，E)(见图3a)，其中

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

E={e01，e04，e12，e23，e25，e34，e35，e45，e10，e40，

e21，e32，e52，e43，e53，e54}

两个6-阶圈为图3a的所有Hamilton圈(见图3b)。

(a)n-6的无向图G

(b)6-阶hamilton圈图3　6阶无向图及其hamilton圈

3Hamilton圈的分子信标检测模型

3.1算法设计

步骤1随机生成通过图G的所有路径；

步骤2利用多色分子信标检测并保留通过图G中每个顶点的路径；

步骤3利用分子信标探针删选出满足圈的条件的路径；

步骤4检测。若路径满足上述条件，则说明存在Hamilton圈，给出确定答案YES，结束；否则为NO。

3.2模型实现

3.2.1步骤1

1) 编码。分别用20bp的寡聚核苷酸片段构造图G的每一顶点vi(i=1，2，…，6)，则用vi的前10个寡聚核苷酸片段与vj的后10个寡聚核苷酸片段构成任意边eij，且应保证各编码是可识别和唯一的。例如在图3a中部分顶点与边的表示：

v0AACCTGGTACCATAGCAGAT

v1CTGCAGTACGTGTAGACCTG

v2ATCACGATCTGAACGTAGCT

e01CACCTGGTACCTGCAGTACG

e02AACCTGGTACATCATGATCT

e12GCTGCAGTACGATCATGATC

2) 用上述方法编码顶点及边后，将带顶点、边补的DNA分子以及生化反应所需的连接酶、缓冲溶液等放入反应试管，因而经过充分的生化反应后，就会形成通过图G中的所有顶点的可能路径集。3.2.2步骤2

1) 用金属纳米簇作猝灭剂，通过调节，得到6种不同荧光的分子信标(见图3a)，记作P0，P1，P2，P3，P4，P5。其环部编码为图G中每个顶点补的编码。以P0编码为例，其余同理(见图4a)。

(a)P0编码　　　(b) 分子信标探针P的编码图4　探针的编码

2) 由步骤1得到通过图G中的所有顶点的可能路径集，由于使用的分子信标探针P0，P1，P2，P3，P4，P5的荧光不同，可通过荧光检测系统检测出带有(且仅带有)这六种荧光的链，并保留。此时，便得到了通过图G中的每个顶点(且一次)的路径，即hamilton路。

3.2.3步骤3

以图3a为例，根据步骤1的编码规则，若步骤2所得片段构成hamilton圈，其产物的最后必定为v0编码的前10 bp寡聚核苷酸片段。

制作以v0前10 bp寡聚核苷酸片段互补序列为环部的分子信标探针P(见图4b)，与步骤3的生成产物进行反应，通过检测荧光发光点的位置，判断是否为Hamilton圈。

3.2.4步骤4

若路径满足上述条件，则说明存在Hamilton圈，对步骤4的结果采用非放射性标记DNA测序的方法，进行测序，读出结果，否则，不存在Hamilton圈。

4结束语

分子信标具有结构简单、灵敏度高及易观测等优点，此技术在特定情况下能够把核酸序列转化为荧光信息。本文基于分子信标的这些特性建立了Hamilton圈问题的分子信标检测模型。通过多色分子信标同时标记，大大减少了DNA计算的过程，具有一定的学术研究意义。此模型的复杂程度与顶点数和顶点的度有关。当然，并非由此模型生成的混合物都是问题的解，还需要通过删选、检测过程进行判断。如果一个图中不存在Hamilton圈，那么最后溶液中就不会生成可以表示Hamilton圈的分子。此外，DNA计算所应用的各种生物技术自身也存在着一定误差，尤其是PCR技术。但随着分子生物学技术的不断发展，这些问题将会得到完善与解决。

参考文献：

[1]ADLEMAN L.Molecular computation of solutions to combinatorial Problems[J].Science，1994，266(11)：

1 021-1 024.

[2]TYAGI S，KZAMER F R.Molecular beacons：Probes that fluoresce upon Hybridization[J].Nat.Biotechnol.1996，14(3)：303-308.

[3]殷志祥，张风月，许进.基于分子信标的DNA计算[J].生物数学学报，2003，18(4)：497-501.

[4]殷志祥，许进.分子信标芯片计算在0-1整数规划问题中的应用[J].生物数学学报，2007，22(3)：1-6.

[5]HUANG XIAOHUI，YIN ZHIXIANG，ZHI LINGYING，et al.Molecularbeacon based on DNA computing model for 0-1 programming problem[C]//Bio-inspired Computing，2009：1-5.

[6]YIN ZHIXIANG，SONG BOSHENG，HEN CHENG，et al.Molecularbeacon-ased DNA computing model for maximum independent set problem[C]//International Computation Technologyand Automation，2010：732-735.

[7]LIU WENBIN，XU JIN.A DNA solution to weighted Hamilton path problem[J].Systems Engineering and Electronics，2002，24(6)：99-102.

[8]GAO LIN，MA RUINIAN，XU JIN.DNA algorithm to the directed shortest hamilton path problem[J].Systems Engineering and Electronics，2002，24(8)：102-105.

[9]LEOBL M，MATAMALA M.Some remarks on cycles in graphs and digraphs[J].Discrete mathematics，2001，23(3)：175-182.

[10]JA BONGDY.Graph theory with applications[M].Macmillan London Press Ltd，1976：57-65.

(责任编辑：何学华)

Molecular Beacon Testing Model of Hamilton Circle Problem

SHA Sha,YIN Zhi-xiang

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

Abstract:In order to solve the classical problems in graph theory and develop a new molecular structure by using DNA, based on the principle that different forms of fluorescent molecular-quenching molecular in the molecular beacon constitutes multi color molecular beacon, the detection model for the solution of Hamilton circle, the NP‐complete problem, was given. The model has the advantages of simple encoding, low complexity, easy to detect and so on.

Key words:DNA computing; molecular beacon; NP‐complete problem; Hamilton circle

收稿日期：2015-04-11

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

作者简介：沙莎(1988-)，女，安徽淮南人，在读硕士，研究方向：DNA计算、图论等。

中图分类号：O157.5

文献标志码：A

文章编号：1672-1098(2016)01-0030-04