Hamilton圈問題的分子信標檢測模型

沙莎+殷志祥

摘要：為了利用DNA 計算求解圖論中經典問題和開發新的分子結構，根據分子信標中熒光分子-猝滅分對選擇的不同可構成多色分子信標的原理，給出Hamilton圈這一NP‐完全問題的解的檢測模型。該模型具有編碼簡單、低復雜度、易于檢測等優點。

關鍵詞：DNA 計算；分子信標；NP‐完全問題；Hamilton圈

中圖分類號：O157.5文獻標志碼：A文章編號：1672-1098（2016）01-0030-04

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

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所示，當有靶序列存在時，分子信標的環部即可與靶序列特異性結合，形成的雙鏈比分子信標的莖環結構更穩定，熒光分子與猝滅分子分開，熒光分子發出的熒光不能被猝滅分子吸收，這時可檢測到熒光，且所檢測到的熒光強度與溶液中靶標的量成正比。本模型利用金屬納米簇作猝滅劑，通過調節金屬簇的大小、形狀和組成而得到不同種的熒光，形成多色分子信標用于同時定量標記。

2） 由步驟1得到通過圖G中的所有頂點的可能路徑集，由于使用的分子信標探針P0，P1，P2，P3，P4，P5的熒光不同，可通過熒光檢測系統檢測出帶有（且僅帶有）這六種熒光的鏈，并保留。此時，便得到了通過圖G中的每個頂點（且一次）的路徑，即hamilton路。

32.3步驟3

以圖3a為例，根據步驟1的編碼規則，若步驟2所得片段構成hamilton圈，其產物的最后必定為v0編碼的前10 bp寡聚核苷酸片段。

制作以v0前10 bp寡聚核苷酸片段互補序列為環部的分子信標探針P（見圖4b），與步驟3的生成產物進行反應，通過檢測熒光發光點的位置，判斷是否為Hamilton圈。

324步驟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-＼based 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.

（責任編輯：何學華）第1期任芳芳，等： 時延情形下的分布式隨機無梯度優化算法安徽理工大學學報（自然科學版）第36卷第36卷第1期安徽理工大學學報（自然科學版）Vol.36No.1

2016年1月Journal of Anhui University of Science and Technology（Natural Science）Jan.2016