ＤＮＡ計算機中二叉樹的鏈式存儲結構
2008-12-31 00:00:00朱雅莉李肯立李琳
計算機應用研究 2008年9期
摘 要：利用DNA分子和連接酶的生物特性，提出DNA計算機中二叉樹的鏈式存儲結構的設計方法，并給出二叉樹鏈式存儲結構的形式描述。在連接酶的作用下，各節點之間產生雜交和連接反應形成DNA雙鏈，其中用到的生物技術在實驗室中都能實現。為了驗證方法的可行性，給出一棵二叉樹的鏈式存儲結構實例，實例表明該設計方法構造的DNA雙鏈對應于二叉樹的中序遍歷序列。
關鍵詞：DNA計算機；二叉樹；數據結構；鏈式存儲結構
中圖分類號：TP384 文獻標志碼：A
文章編號：1001-3695(2008)09-2631-03
Linked storage structure of binary tree in DNA computer
ZHU Yali1，2， LI Kenli2， LI Lin1，2
(1.Dept. of Computer Science， Hengyang Normal University， Hengyang Hunan 421008， China; 2.School of Computer Communications， Hunan University， Hunan 410082， China)
Abstract:This paper proposed the method of designing linked storage structure of the binary tree in DNA computer， which utilized the biological characteristics of DNA molecules and ligases. The linked storage structure of the binary tree was formally described. Being affected by ligase， among the various nodes generated hybridizations and linking reaction to form doublestranded DNA. All the biological technology mentioned could be practically implemented in the laboratory. To prove the feasibility of this method，gave out an instance of a binary tree’s linked storage structure.The example indicates the doublestranded DNA correspond with the binary tree’s inorder traversing.
Key words:DNA computer; binary tree; data structure; linked storage structure
DNA計算機是模擬生物分子DNA的結構并借助生物分子技術進行DNA計算的一種新型計算機。DNA計算機要走向實際應用，必須像電子計算機一樣，需要解決DNA計算機中信息的組織問題，這就需要合理的數據結構來有效地組織DNA計算機需要處理的信息[1，2]。因此，研究DNA計算機中數據結構的設計對DNA計算機的具體實現具有重要的研究意義。本文繼DNA計算機中背包問題算法[3]、堆棧、基于順序存儲方式的二叉樹數據結構的設計之后，展開對DNA計算機中二叉樹的鏈式存儲結構設計問題的研究。文中用到的生物技術在實驗室中已經有很成熟的應用[4]。為便于理解，本文首先介紹有關的DNA生物操作與知識；然后重點闡述在DNA計算機中實現二叉樹鏈式存儲結構的主要思想和規則；最后通過一個實例說明其可行性。
1 理論基礎
DNA 計算是以DNA 分子作為數據，以生物酶和生化操作作為信息處理工具的一種新的計算模式。這種計算方式的變革具有劃時代的意義。
1.1 DNA分子的組成
DNA分子由不同的核苷酸排列而成。每一個構成DNA的脫氧核苷酸是由一分子磷酸、一分子脫氧核酸和一分子含氮堿基組成。組成核苷酸的含氮堿基有腺嘌呤(A)、鳥嘌呤(G)、胞嘧啶(C)和胸腺嘧啶(T)四種。兩條鏈上的堿基通過氫鍵連接起來。堿基對的連接嚴格依據堿基互補配對原則，即腺嘌呤(A)通過兩個氫鍵與胸腺嘧啶(T)配對，鳥嘌呤(G)通過三個氫鍵與胞嘧啶(C)配對；反過來也必定是T與A配對，C與G配對。DNA 本身有兩個不同的末端，即5′和3′末端，因此整個分子是有方向性的。
1.2 生物酶和基本生化操作
1.2.1 酶
酶是由蛋白質組成的一種有機物，對生化反應起催化作用。不同類型的酶可完成不同的操作任務。酶有很多，如限制性核酸內切酶、連接酶、聚合酶、外切酶、末端轉移酶、反轉錄酶等。其中，限制性核酸內切酶(restriction endonuclease)簡稱限制酶，具有高度的專一性，表現在它能識別雙鏈DNA 中某段堿基的排列順序，并且只能在某個特定位點上將DNA分子切開。1968年由Meselson和Yuan在大腸桿菌細胞中首次發現，現已成為基因工程中必不可缺的常用工具酶，在DNA計算領域也有廣泛應用。連接酶(ligase)是一種催化雙鏈DNA上具有相鄰的3′羥基和5′磷酸末端單鏈缺口的修復，以及具有粘性末端或平整末端DNA片段的端端連接的酶。聚合酶(polymerase)是一種能夠在DNA模板上催化寡核苷酸聚合的酶。
1.2.2 基本生化操作
1)DNA分子的合成
由文獻[5]可知，在DNA計算中，作為“數據”的DNA 分子不能隨機地產生，原因是由于DNA分子在雜交過程中可能產生不希望出現的假陽性和假陰性DNA分子。為了避免不必要的分子雜交現象，需要進行優化編碼。在確定了問題的編碼而需進行生化操作時，首要的問題是對這些編碼的DNA鏈進行合成。DNA分子合成主要有五種方法，即磷酸二酯鍵、磷酸三酯鍵、亞磷酸三酯鍵方法以及在后兩者基礎上發展起來的固相合成法和自動化合成法等。目前主要是在某些生物制品公司用合成儀進行合成；有些學者則是利用一些新的研究成果進行合成，如Ouyang等人在建立求解圖的最大團問題的DNA計算模型時采用了由Stemmer等人建立的平行重疊組裝POA技術進行。
2)DNA分子的切割
切割是利用限制酶在特定位置上切割DNA雙鏈分子。限制酶首先在DNA分子鏈上找到切割位置，然后再進行切割。不同的限制酶的切割位點及切口是不同的。有的限制酶的切割結果是具有粘性末端的DNA分子；有的限制酶的切割結果是具有平端的DNA分子。
3)DNA分子的連接
如果兩個具有粘性末端的DNA分子，它們的末端符合堿基互補配對原則，則通過退火反應，這兩個分子可以連接在一起。連接酶可以將DNA鏈的5′端與3′端連接到一起，也可以將DNA鏈的3′端與5′端連接到一起，防止重組分子變松動。在連接酶的作用下，還可將單鏈DNA分子連接到平端分子中的一條鏈上，形成具有粘性末端的DNA分子[6]。
為了更形象地說明DNA分子的連接，下面列舉了在T4DNA連接酶的作用下進行催化連接反應的例子：
實例1 連接含有粘性末端DNA
4)DNA分子的雜交
DNA 分子的雜交是將來源不同的DNA 片段，按堿基互補關系形成雜交雙鏈分子或者部分雙鏈的過程。雜交的類型主要有完全性雜交、假陽性雜交、假陰性雜交、發夾構形雜交四種。完全性雜交是指按照堿基互補配對原則，完全互補的兩條DNA序列之間在一定的條件下相互匹配的堿基之間均形成氫鍵的現象；假陽性雜交是指不完全互補的DNA分子在適當的條件下也能夠雜交形成雙鏈分子的現象；假陰性雜交是指完全互補的DNA分子在反應過程中由于種種原因而沒有完全雜交的現象；發夾構形雜交是指一個單鏈的DNA序列自身的堿基序列之間在一定條件下通過氫鍵引力形成氫鍵的現象。
5)DNA分子的變性與復性
DNA分子的變性是指雙鏈DNA分子結構的氫鍵能夠在加熱、酸、堿、甲醇、乙醇、尿素、甲酰胺等理化因素的作用下發生斷裂，當所有的氫鍵都被破壞時，雙鏈DNA分子多核苷酸鏈就完全分開變成兩條完全互補的單鏈DNA分子。DNA分子的復性是變性過程的逆過程，即對于變性后的兩條完全互補的單鏈DNA分子，在適當的條件下恢復到雙鏈，甚至天然雙螺旋結構的過程。復性時的降溫速度必須緩慢，否則復性過程不可能完成。
2 鏈式存儲結構
二叉樹是一種特殊的樹型結構，其特點是每個節點至多只有兩棵子樹，即二叉樹中不存在度大于2的節點，并且二叉樹的子樹有左右之分，其次序不能任意顛倒。二叉樹有五種基本形態：空二叉樹、僅有根節點的二叉樹、右子樹為空的二叉樹、左子樹為空的二叉樹、左右子樹均非空的二叉樹。
從數據結構角度看，二叉樹的存儲結構有順序存儲結構和鏈式存儲結構。下面將對DNA計算機中二叉樹的鏈式存儲結構設計問題進行討論。
2.1 主要思想
為了實現所謂的鏈式存儲結構，本文提出一種方法，其主要思想如下：
a)把二叉樹中的所有節點分為根節點、最左葉子節點、最右葉子節點、普通左葉子、普通右葉子、只有左孩子的節點、只有右孩子的節點、既有左孩子又有右孩子的節點八種類型。最左葉子節點是指位于根節點的左子樹中最左邊的葉子節點；最右葉子節點是指位于根節點的右子樹中最右邊的葉子節點；普通左葉子節點是指二叉樹中除了最左葉子節點之外的左葉子；普通右葉子節點是指二叉樹中除了最右葉子節點之外的右葉子。
b)按不同的節點類型所對應的規則對每個節點進行DNA編碼與合成。對這些節點采用單、雙鏈混合型DNA 分子進行編碼，主要由地址、數據兩部分組成。通常，數據部分采用雙鏈，地址部分采用單鏈，有的節點的地址部分分為左側、右側兩個小部分。每個節點地址部分的DNA編碼都是惟一的。當要中序遍歷該二叉樹時，就加入連接酶，在連接酶的作用下進行雜交和連接反應可形成DNA雙鏈。該雙鏈對應的是該二叉樹的中序遍歷序列。
當然，為增加操作的可靠性，還可在DNA雙鏈的左右兩側加入“引物”部分的設計。通過加入分離元素SEP（限制性內切酶）有望解決編碼空間小的問題[7]。
2.2 具體規則
下面給出二叉樹各節點元素的鏈式存儲結構的形式描述規則。用數據表示該節點DNA編碼中的數據部分，這部分包括節點類型標記和值的編碼；用本地址表示該節點地址對應的DNA編碼；母地址表示該節點的母親節點地址對應的DNA編碼；左地址表示該節點的左孩子節點地址對應的DNA編碼；右地址表示該節點的右孩子節點地址對應的DNA編碼；上面的橫線表示補序列，如本地址表示該節點地址DNA編碼的補序列。
具體規則如下：
a）對于根節點，如果只有左孩子，則由左地址+數據+空地址和空地址構成的雙鏈組成；如果只有右孩子，則由空地址和空地址構成的雙鏈+數據+右地址組成；如果既有左孩子又有右孩子，則由左地址+數據+右地址組成；如果沒有左、右孩子，則由空地址和空地址構成的雙鏈+數據+空地址和空地址構成的雙鏈組成。對于空二叉樹，則由空地址和空地址構成的雙鏈組成。
b）對于最左葉子節點，其DNA序列主要由數據+本地址組成。
c）對于最右葉子節點，其DNA序列主要由本地址+數據組成。
d）對于普通左葉子節點，其DNA序列主要由母地址+數據+本地址組成。
e）對于普通右葉子節點，其DNA序列主要由本地址+數據+母地址組成。
f）對于只有左孩子的節點，其DNA序列主要由左地址+數據+本地址組成。
g）對于只有右孩子的節點，其DNA序列主要由本地址+數據+右地址組成。
h）對于既有左孩子又有右孩子的節點，其DNA序列主要由左地址+數據+右地址組成。 2.3 實例分析
為了驗證上述方法的可行性，下面通過一個實例給出每個節點DNA結構的形式描述，以及在連接酶作用下發生雜交和連接反應后生成的二叉樹DNA雙鏈的結構示意圖。通過示意圖可以看出，得到了DNA雙鏈的數據部分恰好就是二叉樹的中序遍歷序列。
實例3 給出DNA計算機中如圖1所示二叉樹的鏈式存儲結構的形式描述。
a）節點1是既有左孩子又有右孩子的根節點，由左地址+數據+右地址組成。其中：左地址就是左孩子節點2的地址，是5′→3′方向的單鏈；右地址是右孩子節點3的地址的補，是3′→5′方向的單鏈；數據是節點1的數據部分，是雙鏈。
節點2、3都是既有左孩子又有右孩子的節點，由左地址+數據+右地址組成。
c）節點4是只有左孩子的節點，由左地址+數據+本地址組成。其中：左地址就是左孩子節點8的地址，是5′→3′方向的單鏈；本地址是節點4的地址的補，是3′→5′方向的單鏈；數據是節點4的數據部分，是雙鏈。
d）節點5是普通右葉子節點，由本地址+數據+母地址組成。其中:本地址就是該節點5的地址，是5′→3′方向的單鏈；母地址是節點5的母親節點2地址的補，是3′→5′方向的單鏈；數據是節點5的數據部分，是雙鏈。
e）節點6是普通左葉子節點，由母地址+數據+本地址組成。其中:母地址就是節點6的母親節點3的地址，是5′→3′方向的單鏈；本地址是該節點6地址的補，是3′→5′方向的單鏈；數據是節點6的數據部分，是雙鏈。
f）節點7是只有右孩子的節點，由本地址+數據+右地址組成。其中:本地址就是該節點7的地址，是5′→3′方向的單鏈；右地址是節點7的右孩子節點9地址的補，是3′→5′方向的單鏈；數據是節點7的數據部分，是雙鏈。
g）節點8是最左葉子節點，由數據+本地址組成。其中:本地址是節點8地址的補，是3′→5′方向的單鏈；數據是節點8的數據部分，是雙鏈。
h）節點9是最右葉子節點，由本地址+數據組成。其中:本地址就是節點9的地址，是5′→3′方向的單鏈；數據是節點9的數據部分，是雙鏈。
圖2給出圖1中二叉樹各節點的DNA結構示意圖。
二叉樹各節點元素的地址編碼都是不同的，并存在互補的粘性末端，在連接酶的作用下就會進行雜交和連接反應，形成DNA雙鏈。該DNA雙鏈就是二叉樹鏈式存儲結構的DNA鏈，從數據部分看，恰好是該二叉樹的中序遍歷序列，如圖3所示。圖上標志的數字是對應節點的編號，其序列為842516379；由數據結構知識可知，圖1的二叉樹中序遍歷序列為842516379，兩者完全相符。因此，二叉樹DNA雙鏈的數據部分恰好就是二叉樹的中序遍歷序列。
由于數據部分主要包括節點類型標記和值兩個小部分，且各節點的地址部分編碼不同，只要DNA序列檢測技術進一步精確與成熟，就能較輕松地找到該二叉樹的根節點、某一節點的母親節點、左孩子節點和右孩子節點。也就是說，基于鏈式存儲結構思想的二叉樹數據結構的基本操作在DNA計算機上可以實現。
該方法充分運用了堿基互補配對原則。從理論上講，按如上規則進行DNA編碼的二叉樹節點元素，在連接酶的作用下能夠形成DNA雙鏈，而且該DNA雙鏈與二叉樹的中序遍歷序列一致。因此，這種方法適用于任意形狀的二叉樹。但該方法對DNA編碼的要求很高，DNA編碼的好壞直接影響到操作的正確性，尤其是當二叉樹規模較大時，在具體實現上會碰到更多的難題需要攻克。這里，僅給出了二叉樹鏈式存儲結構的DNA形式描述，有關DNA編碼等問題未作深入研究。
3 結束語
本文主要給出DNA計算機中二叉樹的鏈式存儲結構的形式描述，該方法適用于各種形狀的二叉樹。下一步將對DNA計算機中基于鏈式存儲方式的二叉樹的基本操作以及DNA編碼展開研究，實現其數據結構的設計。
參考文獻：
［1］LI Wanggen，DING Yongsheng.Design of queue for DNAbased computer[J].Journal of Donghua University:Eng Ed，2006，23(2):47-50.
［2］LI Wanggen，DING Yongsheng.Design and implementation of queue data structure in DNA computer[J].Chinese Journal of Computers，2007，30(6):993-998
［3］LI Kenli，YAO Fengjuan，LI Renfa，et al.Improved molecular solutions for the knapsack problem on DNAbased supercomputing[J].Journal of Computer Research and Development，2007，44(6):10631070.
［4］DING Yongsheng，SHAO Shihuang，REN Lihong.DNA computing and soft computing[M].Beijing:Science Press，2002.
［5］XU Jin，HUANG Buyi.DNA computer principle，advances and difficulties(Ⅱ):setting up the database of DNA computer by the synthesis of DNA molecules［J］.Chinese Journal of Computers，2005，28(10):15831590.
［6］LI Yan.A new field of compute science:DNA computing(I)［J］.Computer Science，2002，33(1):202-222.
［7］TSAFTAFIS S A，KATSAGGELOS A K.On designing DNA databases for the storage and retrieval of digital signals[C]//Proc ofICNC.Berlin:SpringerVerlag，2005:11921201
