資源描述：
《最大匹配問題的三鏈dna計算模型》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、最大匹配問題的三鏈DNA計算模型摘要：三螺旋結(jié)構(gòu)的DNA鏈具有穩(wěn)定性，在一定條件下易分解等特點(diǎn)，因此得到的三鏈模型具有錯解率低的優(yōu)點(diǎn)。利用三鏈模型來討論最大匹配問題，拓展了DNA計算解決問題的方法和應(yīng)用領(lǐng)域。關(guān)鍵詞：DNA計算；三鏈DNA;最大匹配中圖分類號：Q523:TP301文獻(xiàn)標(biāo)志碼：A［WT］文章編號：1672-1098(2012)04-0047-03作者簡介：楊靜(1980-)，女，安徽濉溪人，講師，在讀博士，研究方向：DNA計算與組合優(yōu)化。DNA計算是一種以DNA與相關(guān)某些生物酶等作為最基本材料的、基于某些生化反應(yīng)原理的一種新型的
2、分子生物計算方法。DNA計算的優(yōu)勢是利用DNA分子具有海量的存儲能力及生化反應(yīng)的巨大并行性等特點(diǎn)進(jìn)行計算。但DNA計算目前還在實驗室階段，研究的DNA計算模型還很不成熟。在已有的DNA計算模型中，大多數(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計算模型解決最大匹配問題。1三鏈DNA1957年，文獻(xiàn)［8］首次提出了三鏈核酸的概念，即在經(jīng)典的W-C
3、雙螺旋中含有多聚p票呤那條鏈，通過Hoogsteen或反Hoogsteen氫鍵與大溝中的第三條鏈結(jié)合，從而形成三螺旋結(jié)構(gòu)即三鏈DNAO2004年，文獻(xiàn)［9］發(fā)現(xiàn)寡聚脫氧核苷酸在RecA蛋白及ATPYS的存在下，與線性雙螺旋DNA可形成穩(wěn)定的三鏈結(jié)構(gòu)。在形成的過程中，首先寡聚脫氧核苷酸在ATPYS的存在下與RecA蛋白結(jié)合，然后在目標(biāo)雙螺旋DNA上尋找同源序列，這一過程非常迅速并且不打開DNA雙鏈。同源的雙鏈找到后，寡聚脫氧核苷酸在RecA蛋白的介導(dǎo)下與目標(biāo)雙螺旋DNA形成三鏈DNA。經(jīng)證實由RecA蛋白介導(dǎo)形成的三鏈DNA是相當(dāng)穩(wěn)定的［10］
4、。利用三鏈模型解決最大匹配問題，需要用到下面幾種分子操作：①連接。將編碼好的DNA鏈通過連接酶連接成一條DNA鏈；②復(fù)制。將DNA鏈利用PCR擴(kuò)增技術(shù)進(jìn)行復(fù)制；③內(nèi)切。利用內(nèi)切酶在指定位置進(jìn)行切割；④提取測序。對凝膠電泳中得到的最長的DNA鏈進(jìn)行提取測序，已得到所求解。這里所需要的生物操作技術(shù)都已經(jīng)十分成熟，在生物實驗上是可行的。2最大匹配問題2.1問題描述給定無向圖G=（V，E），對邊集E的任一子集ME,如果M中任意兩條邊在G中都沒有公共端點(diǎn)，則稱M是G的一個匹配。一般地，G的匹配不是惟一的。若G中沒有另外的M'
5、^
6、M
7、,則稱M為G的最大
8、匹配。如果M是G的最佳匹配，顯然M是G的最大匹配；反過來不成立。但是G的最佳匹配也有可能不是惟一的（見圖2），Ml={e2，e3，e7}、M2={e2,e6，e7}、M3={el,e4,e7}和M4={el，e6，e7}為該圖的最大匹配，并且均是最佳匹配。2.2DNA算法步驟1:將圖G的頂點(diǎn)和邊進(jìn)行編碼，將所有邊的編碼兩端加上限制性內(nèi)切酶，然后把邊所對應(yīng)的寡聚核苷酸片段與連接酶一起加入緩沖液，在特定溫度下使其連接成一條長鏈，根據(jù)W-C配對原則，在形成穩(wěn)定的雙鏈，把此時得到的結(jié)果進(jìn)行提取、純化、PCR擴(kuò)增放在一試管中，作為最初的數(shù)據(jù)池TO。步驟
9、2:將TO分為兩個試管Tl、T2。選取圖G的一條邊el（—般從el開始），檢查與el相關(guān)聯(lián)的邊。將邊el、e2的補(bǔ)鏈分別制作成探針Pl、P2。利用Pl將含有邊el的鏈分離出來，切掉el從新連接起來，這時得到的T1試管不含有el。同理利用P2得到不含有邊e2的試管T2。這時將得到的新的試管Tl、T2再混合一起作為試管TO。步驟3:檢查是否有兩邊關(guān)于頂點(diǎn)關(guān)聯(lián)，若有重復(fù)步驟1，直到任兩邊都沒有頂點(diǎn)關(guān)聯(lián)。這樣得到的試管中就含有需要的解。步驟4:利用凝膠電泳技術(shù)測出最長的DNA片段（可能不止一條）讀出其解，既是所求的最大匹配。2.3DNA編碼步驟1:將
10、圖G的頂點(diǎn)和邊進(jìn)行編碼，頂點(diǎn)用含20個堿基對的DNA片段表示。邊的編碼可用20個堿基對的DNA片段表示，將所有邊的編碼兩端加上限制性內(nèi)切酶，然后把邊所對應(yīng)的寡聚核苷酸片段與連接酶一起加入緩沖液，在特定溫度下使其連接成一條長鏈。加入聚合酶、引物，利用Watson-Crick互補(bǔ)原則，在3'端不斷地擴(kuò)增DNA分子，從而使所有單鏈DNA鏈都以雙鏈的形式存在，以增加DNA鏈的穩(wěn)定性。在反應(yīng)后的產(chǎn)物中加入底物DNA分子，適量的引物G的頂點(diǎn)所對應(yīng)的寡聚核苷酸片段的補(bǔ)鏈），DNA聚合酶及緩沖液進(jìn)行PCR-擴(kuò)增，對這些產(chǎn)物進(jìn)行純化，然后對于純化后的產(chǎn)物進(jìn)行分
11、離。把這些雙鏈DNA作為最初的數(shù)據(jù)池T0。TO中含有DNA鏈｛el,e2，e3，e4，e5，e6,e7｝。步驟2:將TO分為兩個試管Tl、T2。選取圖G的一條邊el
