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

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

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

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