鏈置換模型的若干問題研究.pdf

1、近幾年DNA計算作為一門新的交叉學(xué)科正逐漸發(fā)展起來，DNA計算是一種以模擬生物分子DNA的結(jié)構(gòu)為手法，通過相應(yīng)的生物技術(shù)來進行運算的一種新方法，利用DNA計算模型為背景和DNA的大量存儲能力和高度并行性設(shè)計新一代計算機。所以DNA計算機也是一種利用DNA建立的一種完整信息技術(shù)形式，以編碼后的DNA序列為運算對象，運用生物分子學(xué)的操作，獲得最后目標DNA鏈，解決所求問題的生物計算機。DNA計算的基本思想是:用分子生物技術(shù)解決計算機難題，使

2、運算過程可控操作。DNA計算模型包括粘貼模型、質(zhì)粒模型、雙鏈DNA模型等。目前作為研究熱點之一的DNA信息處理領(lǐng)域的DNA計算技術(shù)具有并行性好，能耗低，可保存性高等優(yōu)點，因此，它已被應(yīng)用于各種復(fù)雜的計算問題。DNA納米技術(shù)的新興領(lǐng)域也發(fā)展迅速，其中DNA鏈置換的方法因自誘導(dǎo)，靈敏，準確，操作簡單而備受關(guān)注。
　　本文介紹了一種基于DNA鏈置換的生物計算方法，它是一種無需人工干預(yù)的計算方法。該模型能夠使用邏輯公式在連接范式中執(zhí)行迭代

3、解析步驟。該方法的實現(xiàn)基于DNA鏈置換技術(shù)，每個子句編碼在一個單獨的DNA分子命題中，被編碼為每個命題和它的互補鏈對應(yīng)命題子句被編碼在同一條鏈中的不同命題。該模型允許通過級聯(lián)解析步驟運行由霍恩子句組成的邏輯程序。該模型的潛力也體現(xiàn)在其求解SAT的理論能力上，結(jié)果的SAT算法在求解步驟的數(shù)量上具有線性時間復(fù)雜度，而其空間復(fù)雜度在公式的變量數(shù)上是呈指數(shù)級增加的。本文總結(jié)了DNA計算中DNA鏈置換的最新發(fā)展的五個方面:(1)級聯(lián)電路;(2)催

4、化反應(yīng);(3)邏輯計算;(4)表面上的DNA計算;(5)基于由鏈置換引導(dǎo)的納米顆粒的邏輯計算。
　　本次研究首先介紹了幾種目前計算領(lǐng)域所涉及的新興生物技術(shù)，重點介紹了本研究涉及的技術(shù)，然后利用鏈置換技術(shù)解決最大匹配問題、小頂點覆蓋問題及郵遞員問題。
　　第一，以DNA計算為研究背景，討論DNA計算的研究意義和發(fā)展前景。
　　第二，對于已給圖形中所有的邊集，找出圖中任意兩條邊沒有共同頂點的最大邊集，這是一個是NP完全問題

5、，求解這種問題的算法模擬把數(shù)學(xué)問題轉(zhuǎn)換到DNA鏈上，對所給圖中的每一條邊采用DNA的特點進行編碼，而在相應(yīng)的生物操作中，利用鏈置換技術(shù)把目標鏈分離出來，這條鏈表示解。通過實驗操作，給出基于鏈置換的最大匹配問題的解決方式，驗證此算法有效可行。
　　第三，本文針對DNA計算解決最小頂點覆蓋覆蓋問題，采用對表示空解的數(shù)據(jù)池進行解的刪除操作，找出解的補集，重而獲得問題的最優(yōu)解。在鏈置換的基礎(chǔ)上，代替酶的作用，提高了實驗的效率，節(jié)省時間，此

6、算法獨特新穎，簡單可靠。
　　第四，組合優(yōu)化中典型的背包問題是非常重要的NP問題，針對0-1背包問題，本文采用把數(shù)學(xué)問題轉(zhuǎn)換到DNA鏈上的算法，對給定物品的體積和價值分別進行編碼，不加入連接酶的情況下，根據(jù)DNA鏈的W-C原理，將所需的DNA鏈分別用一條短鏈連接，并在反應(yīng)過程中，加入外源鏈，得到滿足約束條件的物品組合，利用鏈置換技術(shù)及相應(yīng)的生物操作刪除外源DNA鏈，以及最終鏈的分離，給出基于鏈置換的0-1背包問題的計算方式，提出的