姚慶安, 鄭 虹, 王 濤(長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 長(zhǎng)春 130012)

?

利用發(fā)夾結(jié)構(gòu)分子實(shí)現(xiàn)棧式結(jié)構(gòu)的DNA計(jì)算模型

姚慶安, 鄭 虹, 王 濤
(長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 長(zhǎng)春 130012)

為使DNA計(jì)算機(jī)能像電子計(jì)算機(jī)一樣解決數(shù)據(jù)的組織與存儲(chǔ)問(wèn)題, 提出了一種利用發(fā)夾結(jié)構(gòu)分子實(shí)現(xiàn)棧式數(shù)據(jù)結(jié)構(gòu)的DNA計(jì)算模型, 描述了數(shù)據(jù)的存儲(chǔ)和組織方式以及元素入棧、 出棧等操作的生物操作過(guò)程。經(jīng)驗(yàn)證, DNA計(jì)算模型求解數(shù)據(jù)的組織問(wèn)題是可行的, 有助于DNA計(jì)算機(jī)走向?qū)嶋H應(yīng)用。

DNA計(jì)算; 數(shù)據(jù)結(jié)構(gòu); 棧; 發(fā)夾結(jié)構(gòu)

0 引 言

DNA計(jì)算自從產(chǎn)生以來(lái)得到了迅速發(fā)展, 理論已經(jīng)證明, DNA計(jì)算機(jī)能像電子計(jì)算機(jī)一樣解決各種計(jì)算問(wèn)題[1]。 而數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)中的一個(gè)重要問(wèn)題, 它是算法設(shè)計(jì)和信息處理的基礎(chǔ), DNA計(jì)算機(jī)也必須能有效地解決數(shù)據(jù)處理和信息組織問(wèn)題才能具有真正的應(yīng)用價(jià)值。目前關(guān)于DNA計(jì)算在數(shù)據(jù)結(jié)構(gòu)方面的研究不多。

棧和隊(duì)列是兩種重要的線性數(shù)據(jù)結(jié)構(gòu), 實(shí)際應(yīng)用非常廣泛。李汪根等[2]研究了一種DNA計(jì)算模型進(jìn)行隊(duì)列的組織, 采用DNA雙鏈存儲(chǔ)數(shù)據(jù), 在DNA雙鏈的兩端分別設(shè)置入隊(duì)和出隊(duì)操作的標(biāo)記序列, 采用特定的生物酶在標(biāo)記部分進(jìn)行鏈的切割和連接, 實(shí)現(xiàn)數(shù)據(jù)的入隊(duì)和出隊(duì)操作。

筆者提出了一種基于發(fā)夾結(jié)構(gòu)分子實(shí)現(xiàn)棧式數(shù)據(jù)結(jié)構(gòu)的DNA計(jì)算模型, 描述了編碼的方法和元素入棧、 出棧等操作的實(shí)現(xiàn)方法。

1 實(shí)現(xiàn)棧式結(jié)構(gòu)的生物基礎(chǔ)

基于棧只在棧頂進(jìn)行操作的特性[3], 采用發(fā)夾結(jié)構(gòu)的DNA分子進(jìn)行編碼。

1.1 發(fā)夾結(jié)構(gòu)

DNA計(jì)算是利用DNA序列的各種生化反應(yīng)解決計(jì)算問(wèn)題的一種計(jì)算模式[4]。發(fā)夾結(jié)構(gòu)的形成是在較長(zhǎng)的單鏈DNA序列中, 某兩部分片段按相反方向恰好滿足Watson-Crick互補(bǔ)原則[5], 如圖1中的片段A和片段B, 在一定條件下, A與B將會(huì)產(chǎn)生雜交反應(yīng), 結(jié)合成為雙鏈, 形成一端為雙鏈, 另一端為環(huán)狀的發(fā)夾結(jié)構(gòu)(見(jiàn)圖2)。

圖1 部分滿足Watson-Crick原則的單鏈DNA分子Fig.1 DNA molecule partially according toWatson-Crick complementary principle

圖2 發(fā)夾結(jié)構(gòu)Fig.2 Hairpin structure

1.2 生物酶

棧中儲(chǔ)存的數(shù)據(jù)編碼與發(fā)夾結(jié)構(gòu)分子的雙鏈部分進(jìn)行入棧和出棧操作時(shí), 需要在棧頂元素的前端或后端對(duì)DNA鏈進(jìn)行切割, 在斷開(kāi)的部分插入或刪除表示數(shù)據(jù)元素的編碼序列, 再將各個(gè)部分連接成完整序列。在這個(gè)過(guò)程中需要使用某些生物酶。生物酶一般都具有特異性, 只催化某種特定的生化反應(yīng)。限制性內(nèi)切酶用來(lái)實(shí)現(xiàn)雙鏈DNA序列的切割, 連接酶用來(lái)實(shí)現(xiàn)DNA片段的連接。

1) 限制性內(nèi)切酶。限制性內(nèi)切酶在某個(gè)特定的識(shí)別位點(diǎn)切割雙鏈DNA分子。不同種類的限制性內(nèi)切酶的識(shí)別位點(diǎn)也各不相同。

圖3描述了限制性內(nèi)切酶的切割效果, 在距離識(shí)別位點(diǎn)5′-GACGC-3′ 5個(gè)堿基的位置進(jìn)行切割, 并留下一個(gè)具有5個(gè)堿基的單鏈部分。將這段單鏈部分稱為切割后的粘性末端, 記為(10,15), 10表示酶進(jìn)行切割的起始位置, 距離識(shí)別位點(diǎn)的起始距離10個(gè)堿基, 15表示雙鏈DNA分子下鏈切割結(jié)束的位置, 距離識(shí)別位點(diǎn)的起始15個(gè)堿基[6]。

圖3 限制性內(nèi)切酶的切割效果Fig.3 Action of restriction endonucleases

2) 連接酶。連接酶將兩個(gè)具有互補(bǔ)的粘性末端的雙鏈DNA分子連接成為完整的雙鏈序列, 圖4為連接酶的作用。這種反應(yīng)常稱為粘貼操作。

圖4 連接酶的作用Fig.4 Action of ligase

2 棧的編碼設(shè)計(jì)

將棧表示為一個(gè)發(fā)夾結(jié)構(gòu)分子。環(huán)狀部分是不可操作的棧底部分, 雙鏈部分用來(lái)存儲(chǔ)數(shù)據(jù)。在棧頂元素編碼部分的最前端和最后端分別設(shè)置兩種不同的限制性內(nèi)切酶的識(shí)別位點(diǎn), 用于入棧和出棧操作。元素的入棧和出棧操作需要留下一個(gè)特定的粘性末端, 將操作后被切割的雙鏈部分再連接完整。這就需要在棧和數(shù)據(jù)元素的編碼中包括一段相同的標(biāo)志片段。

2.1 標(biāo)志片段的編碼

標(biāo)志片段用一段帶有粘性末端的雙鏈DNA序列編碼, 用來(lái)實(shí)現(xiàn)入棧和出棧操作的兩種不同限制性內(nèi)切酶的識(shí)別位點(diǎn)。筆者使用酶BsmFI在棧頂元素之前切割,BsmFI的識(shí)別位點(diǎn)為5′-GGGAC-3′, 其切割位置為(10,14), 切割后留下具有4個(gè)堿基的粘性末端。使用BseXI在棧頂元素的下一個(gè)位置進(jìn)行切割,BseXI的識(shí)別位點(diǎn)是5′-GCAGC-3′, 其切割位置為(8,12), 切割后同樣留下一段具有4個(gè)堿基的粘性末端。

這兩種酶識(shí)別位點(diǎn)的長(zhǎng)度均為5個(gè)堿基, 識(shí)別棧頂?shù)拿窧smFI進(jìn)行切割的起始位置距離識(shí)別位點(diǎn)起始處的長(zhǎng)度為10個(gè)堿基, 因此, 在這兩段識(shí)別位點(diǎn)之間需要另外的5個(gè)堿基長(zhǎng)度的序列。這段序列任意編碼, 只要保證與兩種酶識(shí)別位點(diǎn)區(qū)別明顯。將這段編碼記為PF。

圖5 標(biāo)志片段的編碼結(jié)構(gòu)Fig.5 Code of flag section

兩種酶切割后都會(huì)留下長(zhǎng)度為4個(gè)堿基的粘性末端, 需要采用一段具有4個(gè)堿基的3′-5′方向的單鏈DNA分子與粘性末端進(jìn)行連接反應(yīng), 這段單鏈分子作為標(biāo)志片段的后綴, 記為SF。圖5描述了標(biāo)志片段的編碼。最前端的20個(gè)堿基對(duì)是引物部分, 用于串的擴(kuò)增。

2.2 數(shù)據(jù)元素的編碼

為實(shí)現(xiàn)元素入棧和出棧操作, 數(shù)據(jù)元素的編碼中需包含與標(biāo)志片段相同的前綴和后綴, 這樣數(shù)據(jù)元素的編碼由3部分組成： 前綴PF+數(shù)據(jù)區(qū)Data+后綴SF。數(shù)據(jù)區(qū)Data編碼為雙鏈DNA序列。

圖6 數(shù)據(jù)元素的編碼結(jié)構(gòu)Fig.6 Code of data

圖7 棧底的編碼結(jié)構(gòu)Fig.7 Code of the bottom

在入棧和出棧進(jìn)行切割以及連接操作時(shí), Data區(qū)需要設(shè)置一段與后綴部分SF相同的3′-5′方向的單鏈DNA分子, 所以, Data部分也需要一段標(biāo)志片段, 記為FD, 是一段雙鏈分子, 長(zhǎng)度為4個(gè)堿基對(duì), 下鏈與SF相同, 為3′-TCGA-5′。由于棧頂元素下一個(gè)位置切割標(biāo)記的酶BseXI的識(shí)別位點(diǎn)距離切割的結(jié)束位置R2有8個(gè)堿基的距離, 需要在FD的4個(gè)堿基后面編碼長(zhǎng)度4個(gè)堿基的序列, 用來(lái)表示不同的數(shù)據(jù)元素, 即編碼長(zhǎng)度為4的雙鏈DNA序列。圖6描述了數(shù)據(jù)元素的編碼結(jié)構(gòu)。

2.3 棧底的編碼

棧底不可操作, 可用發(fā)夾結(jié)構(gòu)分子的環(huán)形部分編碼。棧為空時(shí), 棧底部分與標(biāo)志片段進(jìn)行連接； 棧非空時(shí), 棧底部分與數(shù)據(jù)元素進(jìn)行連接, 因此, 棧底部分的編碼中有個(gè)上鏈部分的粘性末端, 與標(biāo)志片段及數(shù)據(jù)元素的后綴SF互補(bǔ)。圖7顯示了棧底的編碼。

3 數(shù)據(jù)的操作

3.1 棧的初始化

1) 生成標(biāo)志片段和棧底的編碼分子；

2) 在連接酶的作用下, 對(duì)這兩個(gè)具有互補(bǔ)的粘性末端的分子進(jìn)行連接, 形成如圖8所示的結(jié)構(gòu)。

圖8 棧的初始化Fig.8 Initial operation

3.2 元素入棧操作

1) 生成待入棧元素的DNA分子序列；

2) 使用酶BsmFI在棧頂位置進(jìn)行切割, 被切割的左部包含標(biāo)志片段, 具有粘性末端SF, 右部是以原棧頂元素為開(kāi)始的數(shù)據(jù)區(qū)域, 其起始端是與SF互補(bǔ)的3′-5′方向的粘性末端(見(jiàn)圖9);

3) 刪除切割的左部, 即標(biāo)志片段；

4) 將待入棧元素通過(guò)連接酶與切割的右部數(shù)據(jù)區(qū)進(jìn)行連接(見(jiàn)圖10)。

圖9 棧頂元素前切割Fig.9 Cut before the top element

圖10 新元素與剩余數(shù)據(jù)區(qū)連接, 元素入棧Fig.10 Splice the new element and push into stack

3.3 元素出棧操作

1) 生成標(biāo)志片段分子；

2) 使用酶BseXI在棧頂元素的下一位置切割, 被切割的左部包含棧頂元素, 具有粘性末端SF, 右部為以原棧頂元素的下一數(shù)據(jù)為開(kāi)始的數(shù)據(jù)區(qū)域, 數(shù)據(jù)區(qū)的起始端是與SF互補(bǔ)的3′-5′方向的粘性末端(見(jiàn)圖11)；

3) 刪除切割后的左部, 即棧頂元素；

4) 將標(biāo)志片段分子通過(guò)連接酶與切割后的剩余的右部進(jìn)行連接(見(jiàn)圖12)。

圖11 棧頂元素后切割Fig.11 Cut after the top element

圖12 標(biāo)致片段與剩余數(shù)據(jù)區(qū)連接, 原棧頂元素出棧Fig.12 Throw the top element and splice the flag section

4 結(jié) 語(yǔ)

筆者提出了一種基于發(fā)夾結(jié)構(gòu)分子的DNA計(jì)算模型, 實(shí)現(xiàn)棧中數(shù)據(jù)的組織以及元素的入棧、 出棧等基本操作。發(fā)夾結(jié)構(gòu)分子的環(huán)狀部分表示棧底, 柄狀的雙鏈部分用于數(shù)據(jù)元素的存儲(chǔ)。在棧頂部分分別設(shè)置兩種不同的限制性內(nèi)切酶BsmFI和BseXI的識(shí)別位點(diǎn), 用來(lái)定位入棧和出棧時(shí)的切割位置。筆者詳細(xì)描述了編碼方案, 給出了棧的初始化、 元素入棧及出棧操作的生物實(shí)現(xiàn)方法。該模型對(duì)如何利用DNA計(jì)算模型進(jìn)行數(shù)據(jù)組織和信息處理、 推進(jìn)DNA計(jì)算的實(shí)際應(yīng)用提供了一種可行的方法。

[1]SALOMAA A TURING, WATSON-CRICK, LINDENMAYER. Aspects of DNA Complementarity [J]. Springer: Unconventional Models of Computation, 1998, 76(4): 94-107.

[2]李汪根,丁永生. DNA計(jì)算機(jī)中隊(duì)列數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)及實(shí)現(xiàn) [J]. 計(jì)算機(jī)學(xué)報(bào), 2007, 30(6): 993-998. LI Wanggen, DING Yongsheng. Design and Implementation of Queue Data Structure in DNA Computer [J]. Chinese Journal of Computer, 2007, 30(6): 993-998.

[3]嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu) [M]. 北京: 清華大學(xué)出版社, 2011. YAN Weimin, WU Weimin. Data Structure [M]. Beijing: Tsinghua University Press, 2011.

[4]ADLEMAN L. Molecular Computation of Solution to Combinatorial Problems [J]. Science Magazine, 1994(11): 1021-1024.

[5]許進(jìn), 譚鋼軍, 范月科, 等. DNA計(jì)算機(jī): 原理、 進(jìn)展及難點(diǎn)(Ⅲ) ----分子生物計(jì)算中的數(shù)據(jù)結(jié)構(gòu)與特性 [J]. 計(jì)算機(jī)學(xué)報(bào), 2007, 29(6): 869-880. XU Jin, TAN Gangjun, FAN Yueke, et al. DNA Computing Principle, Advances and Difficulties(Ⅲ): The Structure and Character of “Data” in DNA Computing [J]. Chinese Journal of Computer, 2007, 29(6): 869-880.

[6]PAUN G, ROZENBERG G, SALOMAA A. DNA計(jì)算: 一種新的計(jì)算模式 [M]. 許進(jìn), 王淑棟, 潘林強(qiáng)譯. 北京: 清華大學(xué)出版社, 2004. PAUN G, ROZENBERG G, SALOMAA A. DNA Computing: A New Computing Paradigms [M]. Beijing: Tsinghua University Press, 2004.

(責(zé)任編輯： 劉東亮)

DNA Computing Model for Stack Based on Hairpin Structure

YAO Qingan, ZHENG Hong, WANG Tao
(School of Computer Science and Engineering,Changchun University of Technology, Changchun 130012, China)

In order to solve the problem of data organization and storage as electronic computer, a DNA computing model of stack based on hairpin structure is proposed. The method for data storage is described. And data operation method is demonstrated. The idea of this paper is feasible to solve data organization problem for DNA computer so that it can help DNA computer development for practical application.

DNA computing; data structure; stack; hairpin structure

1671-5896(2014)05-0545-05

2014-06-04

吉林省科技廳自然科學(xué)基金資助項(xiàng)目(20130101060JC)； 吉林省教育廳“十二五”科學(xué)技術(shù)研究基金資助項(xiàng)目(2014132; 2014125)

姚慶安(1975— ), 男, 吉林磐石人, 長(zhǎng)春工業(yè)大學(xué)講師, 碩士, 主要從事數(shù)字圖像處理、 智能計(jì)算及生物信息研究, (Tel)86-18686699551(E-mail)yao@mail.ccut.edu.cn;

： 鄭虹(1974— ), 女, 長(zhǎng)春人, 長(zhǎng)春工業(yè)大學(xué)副教授, 碩士生導(dǎo)師, 主要從事人工智能、 軟件工程研究, (Tel)86-13039301323(E-mail)hollytz@163.com。

TP301

： A