最大匹配問題的三鏈DNA計算模型

摘要：三螺旋結(jié)構(gòu)的DNA鏈具有穩(wěn)定性，在一定條件下易分解等特點，因此得到的三鏈模型具有錯解率低的優(yōu)點。利用三鏈模型來討論最大匹配問題，拓展了DNA計算解決問題的方法和應用領(lǐng)域。

關(guān)鍵詞：DNA計算；三鏈DNA；最大匹配

中圖分類號：Q523∶TP301文獻標志碼：A

[WT]文章編號：1672-1098（2012）04-0047-03

作者簡介：楊靜（1980-），女，安徽濉溪人，講師，在讀博士，研究方向：DNA計算與組合優(yōu)化。

DNA計算是一種以DNA與相關(guān)某些生物酶等作為最基本材料的、基于某些生化反應原理的一種新型的分子生物計算方法。DNA計算的優(yōu)勢是利用DNA分子具有海量的存儲能力及生化反應的巨大并行性等特點進行計算。但DNA計算目前還在實驗室階段，研究的DNA計算模型還很不成熟。在已有的DNA計算模型中，大多數(shù)是應用于圖與組合優(yōu)化中的NP-完全問題[1-7]。建立DNA模型首先考慮的就是DNA分子結(jié)構(gòu)，開發(fā)和研究新的分子結(jié)構(gòu)也是目前研究的熱點。目前常用的有單鏈的、雙鏈的、單雙鏈混合的、環(huán)狀的、半環(huán)狀的及三螺旋等結(jié)構(gòu)的DNA分子結(jié)構(gòu)。本文將用三鏈DNA計算模型解決最大匹配問題。

1三鏈DNA

1957年，文獻[8]首次提出了三鏈核酸的概念，即在經(jīng)典的W-C雙螺旋中含有多聚嘌呤那條鏈，通過Hoogsteen或反Hoogsteen氫鍵與大溝中的第三條鏈結(jié)合，從而形成三螺旋結(jié)構(gòu)即三鏈DNA。2004年，文獻[9]發(fā)現(xiàn)寡聚脫氧核苷酸在RecA蛋白及ATP γS的存在下，與線性雙螺旋DNA可形成穩(wěn)定的三鏈結(jié)構(gòu)。在形成的過程中，首先寡聚脫氧核苷酸在ATP γS的存在下與RecA蛋白結(jié)合，然后在目標雙螺旋DNA上尋找同源序列，這一過程非常迅速并且不打開DNA雙鏈。同源的雙鏈找到后，寡聚脫氧核苷酸在RecA蛋白的介導下與目標雙螺旋DNA形成三鏈DNA。經(jīng)證實由RecA蛋白介導形成的三鏈DNA是相當穩(wěn)定的[10]。

利用三鏈模型解決最大匹配問題，需要用到下面幾種分子操作：①連接。將編碼好的DNA鏈通過連接酶連接成一條DNA鏈；②復制。將DNA鏈利用PCR擴增技術(shù)進行復制；③內(nèi)切。利用內(nèi)切酶在指定位置進行切割；④提取測序。對凝膠電泳中得到的最長的DNA鏈進行提取測序，已得到所求解。這里所需要的生物操作技術(shù)都已經(jīng)十分成熟，在生物實驗上是可行的。

2最大匹配問題

2.1問題描述

給定無向圖G=（V，E），對邊集E的任一子集ME，如果M中任意兩條邊在G中都沒有公共端點，則稱M是G的一個匹配。一般地，G的匹配不是惟一的。若G中沒有另外的|M′|≥|M|，則稱M為G的最大匹配。如果M是G的最佳匹配，顯然M是G的最大匹配；反過來不成立。但是G的最佳匹配也有可能不是惟一的（見圖2），M1={e2，e3，e7}、M2={e2，e6，e7}、M3={e1，e4，e7}和M4={e1，e6，e7}為該圖的最大匹配，并且均是最佳匹配。

2.2DNA算法

步驟1：將圖G的頂點和邊進行編碼，將所有邊的編碼兩端加上限制性內(nèi)切酶，然后把邊所對應的寡聚核苷酸片段與連接酶一起加入緩沖液，在特定溫度下使其連接成一條長鏈，根據(jù)W-C配對原則，在形成穩(wěn)定的雙鏈，把此時得到的結(jié)果進行提取、純化、PCR擴增放在一試管中，作為最初的數(shù)據(jù)池T0。

步驟2：將T0分為兩個試管T1、T2。選取圖G的一條邊e1（一般從e1開始），檢查與e1相關(guān)聯(lián)的邊。將邊e1、e2的補鏈分別制作成探針P1、P2。利用P1將含有邊e1的鏈分離出來，切掉e1從新連接起來，這時得到的T1試管不含有e1。同理利用P2得到不含有邊e2的試管T2。這時將得到的新的試管T1、T2再混合一起作為試管T0。

步驟3：檢查是否有兩邊關(guān)于頂點關(guān)聯(lián)，若有重復步驟1，直到任兩邊都沒有頂點關(guān)聯(lián)。這樣得到的試管中就含有需要的解。

步驟4：利用凝膠電泳技術(shù)測出最長的DNA片段（可能不止一條）讀出其解，既是所求的最大匹配。

2.3DNA編碼

步驟1：將圖G的頂點和邊進行編碼，頂點用含20個堿基對的DNA片段表示。邊的編碼可用20個堿基對的DNA片段表示，將所有邊的編碼兩端加上限制性內(nèi)切酶，然后把邊所對應的寡聚核苷酸片段與連接酶一起加入緩沖液，在特定溫度下使其連接成一條長鏈。加入聚合酶、引物，利用Watson-Crick互補原則，在3′端不斷地擴增DNA分子，從而使所有單鏈DNA鏈都以雙鏈的形式存在，以增加DNA鏈的穩(wěn)定性。在反應后的產(chǎn)物中加入底物DNA分子，適量的引物（圖G的頂點所對應的寡聚核苷酸片段的補鏈），DNA聚合酶及緩沖液進行PCR-擴增，對這些產(chǎn)物進行純化，然后對于純化后的產(chǎn)物進行分離。把這些雙鏈DNA作為最初的數(shù)據(jù)池T0。T0中含有DNA鏈{e1，e2，e3，e4，e5，e6，e7}。

步驟2：將T0分為兩個試管T1、T2。選取圖G的一條邊e1（一般從e1開始），檢測到e1與e2關(guān)于頂點v1關(guān)聯(lián)，將邊e1、e2的補鏈分別制作成探針P1、P2。在表示e1的寡聚核苷酸片段的補鏈DNA單鏈的5′端添加一個聚酯纖維A，在標記上生物素。使這些DNA單鏈和抗原蛋白質(zhì)在含有ATPγS溶液混合，在一定條件下生成核蛋白細狀體，把這些核蛋白細狀體的DNA鏈作為模板構(gòu)造探針P1。將第一個探針混合到數(shù)據(jù)池中，在一定條件下根據(jù)Hoogsteen配對原則，這個探針將與含有e1的雙鏈DNA結(jié)合生成三螺旋結(jié)構(gòu)的DNA，再利用生物操作中的分離操作將沒有生成三鏈的雙鏈DNA除去。利用內(nèi)切酶的作用將e1邊的編碼從鏈上連同探針一起切除。加熱解鏈，沖洗掉補鏈，得到的探針可以再用。這時得到的DNA鏈不再含有邊e1，還作為試管T1。利用同樣的方法可以得到不含有邊e2的DNA鏈，作為試管T2，將兩個試管混合作為試管T0。這時T0試管中含有DNA鏈{e1，e3，e4，e5，e6，e7}和{e2，e3，e4，e5，e6，e7}。

步驟3：檢測圖G中是否還有邊關(guān)聯(lián)，若有，重復上述步驟，得到最終的試管T0。必將含有所需的解。

步驟4：利用凝膠電泳技術(shù)測出最長的DNA片段，用PCR擴增和純化后，提取這些鏈。采用非放射性標記DNA測序的方法，進行測序，可得到最長的DNA鏈的堿基排序，也即知道了圖的最大匹配，M1={e2，e3，e7}、M2={e2，e6，e7}、M3={e1，e4，e7}和M4={e1，e6，e7}。

3結(jié)論

利用三鏈模型來解決最大匹配問題相對其他模型計算時錯解率要低一些，因為生成數(shù)據(jù)池時，存在的都是雙螺旋結(jié)構(gòu)的DNA鏈，而雙鏈DNA的穩(wěn)定性較單鏈DNA的穩(wěn)定性強，在數(shù)據(jù)池中就不會出現(xiàn)由于編碼問題而出現(xiàn)的“發(fā)夾”結(jié)構(gòu)，從而使生物化學反應更為充分，效率更高。而對于三鏈DNA的分離也相對雙鏈DNA的分離較容易些。當然對于實際問題的求解，還存在著一些生物技術(shù)上的問題，需進一步研究。另外，此模型的復雜度與頂點的度有關(guān)。作為有n個頂點和m條邊的無向圖，利用三鏈模型計算它的最大匹配。根據(jù)模型分析，編碼及生物操作的復雜度僅隨頂點和邊的增加而增加，且呈線性關(guān)系O（n）。模型中由于需要利用內(nèi)切酶把某條邊對應的DNA片段切除，可能會因為生物技術(shù)或是問題規(guī)模的擴大，而產(chǎn)生偽解或錯解。隨著生物技術(shù)的發(fā)展，這些問題會得到解決。目前，在理論上用三鏈模型已經(jīng)解決了不少問題，更加體現(xiàn)了這種模型得優(yōu)點。隨著分子生物學技術(shù)的發(fā)展，這種DNA計算模型的生物操作將會得以更好的實現(xiàn)，模型的通用性將進一步提升。

參考文獻：

[1]LIUQINGHUA，LIMANWANG，ANTHONYGFRUTOS，etal.DNAcomputingonsurfaces[J].Nature，2000，403（13）：175-178.

[2]GAOLIN，XUJIN.DNAsolutionofvertexcoverproblembasedonstickermodel[J].ChineseJoumalofElectronics，2002，11（2）：280-284.

[3]KARLHEINZZIMMERMANN.EfficientDNAstickeralgorithmsforNPcompletegraphproblems[J].ComputerPhysicsCommunications，2002，144：297-309.

[4]BRAICHRS，CHELYAPOVNJOHNSON，etal.Solutionofa20-varaiable3-SATproblemonaDNAcomputer[J].Science，2002，296：499-502.

[5]BENENSONY，TAMARP，ADARR，etal.Programmableandautonomouscomputingmachinemadeofbiomoleccules[J].Nature，2001，414（22）：430-434.

[6]許進，董亞非，魏小鵬.粘貼DNA計算機模型（I）：理論[J].科學通報，2004，49（3）：205-212.

[7]許進，李三平，董亞非，等.粘貼DNA計算機模型（Ⅱ）：應用[J].科學通報，2004，49（4）：299-307.

[8]STYAGI，F(xiàn)RKRAMER.Molecularbeacon：probesthatfluoresceuponhybridization[J].NatBiotechnol，1996，14：303-308.

[9]SHIGEMORIY，OISHIM.SpecificcleavageofDNAmoleculesatRecA-mediatedtriple-strandedstructure[J].NucleicAcidsResearch，2004，32（15）：4563-4575.

[10]RAOBJ，DUTREIXM，RADDINGCM.Stablethree-strandedDNAmadebyRecAprotein[J].ProNatlAcadSciUSA，1991，88（8）：2984-2988.

（責任編輯：何學華，吳曉紅）