[發(fā)明專利]基于3-臂DNA分子的DNA計(jì)算機(jī)廣義表數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 200810207759.1
• 申請(qǐng)日: 2008-12-25
• 公開(kāi)（公告）號(hào): CN101458740A
• 公開(kāi)（公告）日: 2009-06-17
• 發(fā)明（設(shè)計(jì)）人: 丁永生;李汪根;任立紅
• 申請(qǐng)（專利權(quán)）人: 東華大學(xué)
• 主分類號(hào): G06F19/00
• 分類號(hào): G06F19/00
• 代理公司: 上海泰能知識(shí)產(chǎn)權(quán)代理事務(wù)所
• 代理人: 黃志達(dá);謝文凱

技術(shù)領(lǐng)域

本發(fā)明屬生物技術(shù)及DNA計(jì)算領(lǐng)域，特別是涉及一種基于3-臂DNA分子的DNA計(jì)算機(jī)廣義表數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)方法。

背景技術(shù)

DNA計(jì)算中被處理的數(shù)據(jù)存儲(chǔ)在DNA分子中，數(shù)據(jù)的處理通過(guò)諸如合成、雜交、剪切等基因工程的方法來(lái)實(shí)現(xiàn)。DNA計(jì)算的最大優(yōu)點(diǎn)是極大的存儲(chǔ)密度和計(jì)算的高度并行性。科學(xué)家在DNA計(jì)算領(lǐng)域已經(jīng)取得了許多研究成果：1994年，Adleman首次成功地在實(shí)驗(yàn)室應(yīng)用DNA分子解決了7節(jié)點(diǎn)的Hamilton路徑問(wèn)題，證明了運(yùn)用DNA分子進(jìn)行計(jì)算的可行性；1995年，Lipton提出了運(yùn)用DNA實(shí)驗(yàn)解決可滿足性問(wèn)題的方法；1997年，Ouyang等人通過(guò)對(duì)全體可能的連通子圖構(gòu)建相應(yīng)的DNA分子計(jì)算池，從而解決了6節(jié)點(diǎn)的最大連通子圖問(wèn)題。1996年，Guarnieri等首次給出了DNA計(jì)算機(jī)運(yùn)算系統(tǒng)中正有理數(shù)的進(jìn)位加法運(yùn)算；1999年，Yurke等提出了一種對(duì)輸入串與運(yùn)算串的DNA分子編碼是分離的DNA計(jì)算機(jī)系統(tǒng)中的加法運(yùn)算模型。2001年，Shapiro等提出了一種以DNA分子為載體的有限狀態(tài)自動(dòng)機(jī)模型，該模型的硬件由生物操縱酶實(shí)現(xiàn)，軟件和輸入數(shù)據(jù)是預(yù)先編碼的DNA分子，通過(guò)在試管中自動(dòng)完成一系列剪切、連接循環(huán)最后可以得到編碼了最終狀態(tài)的輸出分子；2004年，Shapiro等又提出了一種用于控制基因表達(dá)的分子自動(dòng)計(jì)算機(jī)并應(yīng)用于疾病診斷治療。

DNA計(jì)算機(jī)要走向?qū)嶋H應(yīng)用，必須與電子計(jì)算機(jī)一樣，需要解決DNA計(jì)算機(jī)中信息的合理組織，這就需要合理的數(shù)據(jù)結(jié)構(gòu)來(lái)有效地組織DNA計(jì)算機(jī)需要處理的信息。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中占有重要地位，它有多種類型，如：隊(duì)列、堆棧、表、樹(shù)、圖等。廣義表是一種重要的數(shù)據(jù)結(jié)構(gòu)，被廣泛應(yīng)用在計(jì)算機(jī)各個(gè)領(lǐng)域。

使用k-臂DNA分子進(jìn)行計(jì)算于1999年由Jonoska等提出。他們所提出的算法模型用于解3-可滿足性問(wèn)題(3-SAT)及3-頂點(diǎn)著色問(wèn)題(3-VCP)，其算法所要求的步驟與公式中的變量數(shù)相等，并且解3-VCP的算法步驟不隨變量數(shù)的增加而增加。2002年，他們使用這種DNA分子構(gòu)造了相應(yīng)的三維圖結(jié)構(gòu)。用k-臂DNA分子來(lái)表示圖中度為k的頂點(diǎn)，直觀地反映了圖結(jié)構(gòu)，使算法很容易理解。類似于k臂DNA分子的結(jié)構(gòu)自然界已存在，如Holliday中間體。在分子生物學(xué)實(shí)驗(yàn)原理上，用這些分子作為頂點(diǎn)構(gòu)造三維圖結(jié)構(gòu)是可行的，如果某頂點(diǎn)的度為k，則用k臂分子作為其頂點(diǎn)構(gòu)造塊。

發(fā)明內(nèi)容

本發(fā)明所要解決的技術(shù)問(wèn)題是提供一種DNA計(jì)算機(jī)中廣義表數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)方法。特別給出基于3-臂DNA分子的DNA計(jì)算機(jī)中廣義表的表結(jié)點(diǎn)和原子結(jié)點(diǎn)的設(shè)計(jì)以及初始化、創(chuàng)建和遍歷廣義表的方法。

本發(fā)明解決其技術(shù)問(wèn)題所采用的技術(shù)方案是：提供一種基于3-臂DNA分子的DNA計(jì)算機(jī)廣義表數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)方法，包括表結(jié)點(diǎn)數(shù)據(jù)元素和原子結(jié)點(diǎn)數(shù)據(jù)元素，其特征在于，所述的方法包括下列步驟：參見(jiàn)圖1，

(1)設(shè)計(jì)限制性內(nèi)切酶的識(shí)別位點(diǎn)E(i)：在這種酶的活性條件下，在E(i)所在臂上被從廣義表上剪切下來(lái)，獲取結(jié)點(diǎn)；

(2)設(shè)計(jì)限制性內(nèi)切酶的識(shí)別位點(diǎn)Eh：在該酶的活性條件下，在Eh所在臂上被剪切形成粘性末端，以便新的鏈表結(jié)點(diǎn)鏈接到廣義表的表頭結(jié)點(diǎn)；

(3)設(shè)計(jì)限制性內(nèi)切酶的識(shí)別位點(diǎn)Et：在該酶的活性條件下，在Et所在臂上被剪切形成粘性末端，以便新的鏈表結(jié)點(diǎn)鏈接到廣義表的表尾結(jié)點(diǎn)；

(4)設(shè)計(jì)特定的DNA序列stick：預(yù)先設(shè)計(jì)好的結(jié)點(diǎn)通過(guò)在這個(gè)序列上發(fā)生連接反應(yīng)而被鏈接到廣義表上；

(5)設(shè)計(jì)特定的DNA序列element：這個(gè)序列用來(lái)表征廣義表的元素值；

(6)設(shè)計(jì)限制性內(nèi)切酶的識(shí)別位點(diǎn)Ec：在該酶的活性條件下，element元素值能被檢測(cè)分子識(shí)別；

(7)設(shè)計(jì)限制性內(nèi)切酶的識(shí)別位點(diǎn)E；粘性末端s與元素結(jié)點(diǎn)中酶Eh所剪切的粘性末端互補(bǔ)，以便將值element添加到元素結(jié)點(diǎn)中。

所述的Et和Eh所產(chǎn)生的粘性末端相同。

所述的各種限制性內(nèi)切酶不能為同一種酶。

所述的廣義表的操作包括初始化、創(chuàng)建廣義表和遍歷廣義表。

所述的初始化是指初始化一個(gè)不含任何元素的空的廣義表(如圖2所示)；sinn片段是E0的剪切位點(diǎn)上的特定堿基序列，用以標(biāo)示該結(jié)點(diǎn)是廣義表的首結(jié)點(diǎn)。

所述的創(chuàng)建廣義表，是指將廣義表的元素按照邏輯結(jié)構(gòu)逐次插入到廣義表上；除了已經(jīng)初始化的空的廣義表外，還需要以下幾種DNA片段：(如圖3所示)

(a)元素結(jié)點(diǎn)：所有最終插入到廣義表的結(jié)點(diǎn)都由元素結(jié)點(diǎn)經(jīng)過(guò)相應(yīng)的操作獲取；