資源描述：
《DNA計(jì)算模型及應(yīng)用綜述.doc》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。
1、DNA計(jì)算模型及應(yīng)用綜述摘要：自從Adieman博士最早利用DNA計(jì)算成功求解了7個(gè)頂點(diǎn)有向圖的Ham訂ton問(wèn)題以來(lái)，DNA計(jì)算［1］被引入多個(gè)研究領(lǐng)域，成為當(dāng)今科技發(fā)展的熱點(diǎn)之一。首先介紹DNA計(jì)算的基本原理及編碼方法，其次闡述了DNA計(jì)算的主要模型，再次總結(jié)了國(guó)內(nèi)外研究學(xué)者應(yīng)用DNA計(jì)算解決的實(shí)際問(wèn)題，最后列舉了DNA計(jì)算改進(jìn)的相關(guān)方向。關(guān)鍵詞：DNA計(jì)算；模型；NP完全問(wèn)題；智能算法中圖分類(lèi)號(hào)：TP301.4文獻(xiàn)標(biāo)識(shí)碼：ADoi：10.3969/j.issn.1003-6970.2012.05.056TheModelsandAppl
2、icationsofDNAComputingBalXue(ShandongNormalUniversityCollegeofmanagementscienceandEngineering,Jinan250014,China)[Abstrac]SinceDr.ad1emanusedDNacomputingtoachieveHPPwithsevenverticessuccessfully,DNacomputinghasbeenbroughtinvariousresearchareasandbecomeoneofthefocusesofscien
3、tificdevelopment.Firstly,thebasicprinciplesandcodingmethodsareintroduced,followingwiththemainmodelsofit.Inaddition,wesummeduptheapplicationsofDNacomputingtosolvepracticalproblems,finally,severalimproveddirectionsarelisted.[Keywords]DNacomputing；Model；theNP-completeproblem；
4、Intelligentalgorithm1DNA計(jì)算簡(jiǎn)介1.1DNA計(jì)算原理DNA是一種由許多脫氧核昔酸分子連接而成的高分子化合物，其中脫氧核昔酸由脫氧核糖、磷酸和含氮堿基三部分組成。因?yàn)閴A基有腺嗥吟A、鳥(niǎo)嗥吟G、胸腺13密噪T和胞13密喘C四種類(lèi)型，所以與之對(duì)應(yīng)的核昔酸也有四種表現(xiàn)形式。DNA計(jì)算的基本原理是把需要運(yùn)算的對(duì)象映射成DNA分子鏈,在生物酶的作用下生成初始數(shù)據(jù)池，然后按照一定的規(guī)則將原始問(wèn)題高度并行地映射成DNA分子鏈的可控的生化過(guò)程，最后利用現(xiàn)代分子生物技術(shù)[2-9]獲得最終運(yùn)算結(jié)果[10]o1.2DNA編碼方法Baum于1
5、996年提出了降低DNA序列間相似度的假設(shè)，隨后Garzon等人定義了DNA計(jì)算中的編碼問(wèn)題。DNA編碼方法主要包括模板-映射方法、最小長(zhǎng)度子串方法和隨機(jī)搜索方法，其中模板-映射方法是由Wisconsin大學(xué)的Frutos等人提出的，2003年，劉文斌在該方法的基礎(chǔ)上提出了模板框的概念；Feldkamp等人提出了一種最小長(zhǎng)度子串評(píng)價(jià)方法，通過(guò)限制子序列出現(xiàn)的次數(shù)降低了編碼之間的相似程度；2003年，Tulpant提出了隨機(jī)搜索編碼方法，采用隨機(jī)方式生成DNA編碼解空間，然后根據(jù)約束條件篩選出解空間中較好的DNA編碼序列。1DNA計(jì)算模型1.
6、1基于理論研究的DNA計(jì)算模型1996年，Roweis提出一種基于分子操作和隨機(jī)訪(fǎng)問(wèn)內(nèi)存的DNA計(jì)算粘貼模型，在運(yùn)算過(guò)程中不需要酶的作用和DNA鏈的延伸，主要有合并、分離、設(shè)置和清除四種基本操作。隨后，Kari等人在粘貼模型的基礎(chǔ)上提出了粘貼系統(tǒng)的概念，由Paun等人[3,7,11]將其推廣到更加普遍的形式上。2004年，許進(jìn)等人對(duì)粘貼模型給予了更為詳細(xì)的討論。1987年，Head在利用形式語(yǔ)言對(duì)DNA序列進(jìn)行分析的基礎(chǔ)上提出了剪接系統(tǒng)的概念[1,3,7],Paun等人對(duì)該系統(tǒng)的通用性、計(jì)算能力和剪接運(yùn)算等方面進(jìn)行了詳細(xì)的討論[3,7,12
7、]o2001年，Benenson等人利用剪接系統(tǒng)研制出一臺(tái)具有編程能力的有窮自動(dòng)機(jī)，并說(shuō)明了剪接系統(tǒng)是計(jì)算気備的。插入/刪除模型是建立在上下文插入和刪除基礎(chǔ)上的抽象模型[3,4,11],Paun等人于1998年利用上下文插入文法描述了遞歸可列語(yǔ)言，2002年，Takahara在第8屆國(guó)際DNA計(jì)算機(jī)會(huì)議上闡述了插入/刪除系統(tǒng)的計(jì)算能力。k-臂模型是1999年由Jonoska等人提出的一種DNA計(jì)算模型，Seeman等人的研究結(jié)果表明3-臂和4-臂DNA分子是相當(dāng)穩(wěn)定的，而且k-臂DNA分子的3'端一般為單鏈延伸。發(fā)夾模型是通過(guò)巧妙的DNA編
8、碼，使非可行解的DNA鏈在生化反應(yīng)中形成發(fā)夾結(jié)構(gòu)，通過(guò)DNA分子中BSTNI內(nèi)切酶的識(shí)別位來(lái)清除這些發(fā)夾結(jié)構(gòu)。2000年，Sakatomo等人利用該模型建立了一種求解可滿(mǎn)足性問(wèn)題
