最大匹配問題的三鏈DNA計(jì)算模型

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

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

中圖分類號(hào)：Q523∶TP301文獻(xiàn)標(biāo)志碼：A

[WT]文章編號(hào)：1672-1098（2012）04-0047-03

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

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

1三鏈DNA

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

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

2最大匹配問題

2.1問題描述

給定無向圖G=（V，E），對(duì)邊集E的任一子集ME，如果M中任意兩條邊在G中都沒有公共端點(diǎn)，則稱M是G的一個(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的頂點(diǎn)和邊進(jìn)行編碼，將所有邊的編碼兩端加上限制性內(nèi)切酶，然后把邊所對(duì)應(yīng)的寡聚核苷酸片段與連接酶一起加入緩沖液，在特定溫度下使其連接成一條長鏈，根據(jù)W-C配對(duì)原則，在形成穩(wěn)定的雙鏈，把此時(shí)得到的結(jié)果進(jìn)行提取、純化、PCR擴(kuò)增放在一試管中，作為最初的數(shù)據(jù)池T0。

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

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

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

2.3DNA編碼

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

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

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

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

3結(jié)論

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

參考文獻(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]許進(jìn)，董亞非，魏小鵬.粘貼DNA計(jì)算機(jī)模型（I）：理論[J].科學(xué)通報(bào)，2004，49（3）：205-212.

[7]許進(jìn)，李三平，董亞非，等.粘貼DNA計(jì)算機(jī)模型（Ⅱ）：應(yīng)用[J].科學(xué)通報(bào)，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.

（責(zé)任編輯：何學(xué)華，吳曉紅）