DNA計(jì)算中B-樹(shù)和B+-樹(shù)數(shù)據(jù)結(jié)構(gòu)的研究與設(shè)計(jì).pdf

1、隨著分子生物學(xué)、計(jì)算機(jī)科學(xué)、生物技術(shù)及信息技術(shù)的發(fā)展，提出了DNA計(jì)算。DNA計(jì)算以其高度并行性、運(yùn)算速度快、信息貯存容量大的優(yōu)勢(shì)，已經(jīng)成為一種新的計(jì)算模式，被用來(lái)解決各種NP完全問(wèn)題。DNA計(jì)算模型也得到了迅速發(fā)展，從粘貼模型到有窮自動(dòng)機(jī)，到插入-剪接系統(tǒng)，到自組裝系統(tǒng)。
　　在傳統(tǒng)的電子計(jì)算機(jī)中，數(shù)據(jù)是以二進(jìn)制形式存儲(chǔ)在半導(dǎo)體器件和磁性材料中的。而在DNA計(jì)算機(jī)中，數(shù)據(jù)均通過(guò)堿基序列的編碼存儲(chǔ)在DNA分子中。數(shù)據(jù)從邏輯上可以劃

2、分為棧、隊(duì)列、廣義表、二叉樹(shù)和圖等基本數(shù)據(jù)結(jié)構(gòu)類(lèi)型。在數(shù)據(jù)庫(kù)系統(tǒng)中建立文件索引，多叉樹(shù)具有獨(dú)特的優(yōu)勢(shì)，因此被用來(lái)表示和描述文件索引的數(shù)據(jù)結(jié)構(gòu)。
　　本文首先分析了DNA計(jì)算的原理及計(jì)算模型，探討了并行計(jì)算及其結(jié)構(gòu)模型和計(jì)算模型，并比較了高性能電子計(jì)算機(jī)和DNA分子計(jì)算并行思想的異同。
　　然后總結(jié)了現(xiàn)有DNA計(jì)算機(jī)的基本數(shù)據(jù)結(jié)構(gòu)的DNA分子編碼，對(duì)某些數(shù)據(jù)結(jié)構(gòu)提出修改和優(yōu)化，如用環(huán)形DNA分子表示基于順序存儲(chǔ)的循環(huán)隊(duì)列，用熒

3、光標(biāo)記的DNA雙鏈片段表示廣義表的表頭。設(shè)計(jì)了3D DNA分子結(jié)構(gòu)表示鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的二叉樹(shù)。
　　最后，重點(diǎn)設(shè)計(jì)及實(shí)現(xiàn)了B-樹(shù)和B+-樹(shù)的k-arms3D DNA編碼，通過(guò)實(shí)例分析給出了k-arms3D DNA分子編碼的B-樹(shù)和B+-樹(shù)的初始化、查找、插入和刪除等基本操作的生物技術(shù)實(shí)現(xiàn)過(guò)程，并提出一種基于自治的DNA并行計(jì)算的新模型--EPCL，模型及其改進(jìn)模型，該模型不僅在輸入輸出的技術(shù)上增加了并行機(jī)制，還在計(jì)算過(guò)程中加入了并行