孫 俠，殷志祥，趙前進(jìn)，許 峰

（安徽理工大學(xué) 理學(xué)院，安徽 淮南 232001）

基于三鏈DNA結(jié)構(gòu)的全錯(cuò)位排列問(wèn)題算法

孫 俠，殷志祥，趙前進(jìn)，許 峰

（安徽理工大學(xué) 理學(xué)院，安徽 淮南 232001）

目前，一種新型的DNA計(jì)算模型——三鏈DNA計(jì)算模式正越來(lái)越受到人們的關(guān)注。已經(jīng)證實(shí)，DNA單鏈能在RecA蛋白的介導(dǎo)下與同源的雙鏈DNA匹配成穩(wěn)定的三鏈DNA結(jié)構(gòu)，利用此三鏈核酸提取目的DNA序列是完全可行的。文章提出了全錯(cuò)位排列問(wèn)題的基于三鏈DNA的計(jì)算模型，由于表示可能解的鏈都是雙鏈，彼此不會(huì)錯(cuò)配，也不會(huì)形成發(fā)夾結(jié)構(gòu)，這樣就大大降低了編碼復(fù)雜度和計(jì)算錯(cuò)誤率。

三鏈DNA結(jié)構(gòu)；抗原中介；全錯(cuò)位排列問(wèn)題

DNA計(jì)算是一種以DNA和相關(guān)的某些生物酶作為最基本材料的，基于某種生化反應(yīng)原理的新型分子生物計(jì)算方法。自1994年，美國(guó)加利福尼亞大學(xué)的Adleman［1］博士提出DNA計(jì)算的思想以來(lái)，DNA計(jì)算領(lǐng)域的研究有了長(zhǎng)足的發(fā)展。許多NP—完全問(wèn)題和困難計(jì)算問(wèn)題都得到了解決，如中國(guó)郵遞員問(wèn)題，圖的著色問(wèn)題，匹配問(wèn)題，圖的最大團(tuán)問(wèn)題，最小覆蓋問(wèn)題，0－1規(guī)劃問(wèn)題等［2－6］。以前的DNA計(jì)算方法都是基于Watson－Crick原則，利用堿基間的互補(bǔ)配對(duì)來(lái)完成基本的運(yùn)算。隨著實(shí)驗(yàn)的技術(shù)的不斷提高，近年來(lái)許多研究者在實(shí)驗(yàn)中相繼證實(shí)分子可以以其它結(jié)構(gòu)存在，比如三鏈狀結(jié)構(gòu)。至今已發(fā)現(xiàn)的三鏈結(jié)構(gòu)有三股螺旋結(jié)構(gòu)和三股發(fā)辮結(jié)構(gòu)。對(duì)三鏈DNA的研究主要是醫(yī)學(xué)方面，也有人嘗試用三鏈DNA解決有關(guān)問(wèn)題，方剛等［7］用三鏈DNA計(jì)算模型解決了3－SAT問(wèn)題、三頂點(diǎn)著色問(wèn)題，楊靜等［8］利用三鏈DNA計(jì)算模型解決了0－1整數(shù)規(guī)劃問(wèn)題。

全錯(cuò)位排列問(wèn)題是組合數(shù)學(xué)中常見(jiàn)的一類(lèi)問(wèn)題，作者給出過(guò)它的基于芯片、基于表面的DNA計(jì)算模型［9，10］，這里將嘗試給出基于三鏈DNA的計(jì)算模型，與前面兩種模型相比，利用三鏈結(jié)構(gòu)，降低了編碼的復(fù)雜度，而且反應(yīng)后得到的解以雙鏈的形式出現(xiàn)，對(duì)于解的正確率有很好的效果。

1 三鏈DNA的結(jié)構(gòu)與功能［11］

1957年，F(xiàn)eisenfeld［12］等首次提出了三鏈核酸（triple－h(huán)elix DNA／triplex）的概念。三螺旋結(jié)構(gòu)是在雙螺旋結(jié)構(gòu)的基礎(chǔ)上形成的。三鏈DNA是由經(jīng)典的Watson－Crick雙螺旋中含有多聚嘌呤的那條鏈通過(guò)Hoogsteen和反式Hoogsteen型氫鍵與第三條鏈相作用形成的。第三條鏈位于Watson－Crick雙鏈的大溝中，靠Hoogsteen堿基對(duì)的氫鍵相聯(lián)系。見(jiàn)圖1所示。

圖1 三螺旋DNA鏈的空間結(jié)構(gòu)與分子結(jié)構(gòu)

2004年Shigemori等發(fā)現(xiàn)DNA在RecA蛋白及ATPr S的存在下，與線性雙螺旋DNA可形成穩(wěn)定的三鏈結(jié)構(gòu)（見(jiàn)圖2）。經(jīng)證實(shí)由RecA蛋白介導(dǎo)形成的三鏈DNA是相當(dāng)穩(wěn)定的［13］。2009年方剛［7］通過(guò)實(shí)驗(yàn)證實(shí)使用 RecA蛋白介導(dǎo)的三鏈核酸提取目的DNA序列的方法是完全可行的，它可以被設(shè)計(jì)用來(lái)進(jìn)行相應(yīng)的分子運(yùn)算。目前關(guān)于三鏈DNA的研究偏重于它的醫(yī)學(xué)應(yīng)用，如通過(guò)三螺旋結(jié)構(gòu)的形成，寡聚核苷酸可以充當(dāng)切割DNA的“分子剪刀”和提供抑制基因轉(zhuǎn)錄的新手段等等。下面給出全錯(cuò)位排列問(wèn)題的基于三鏈DNA結(jié)構(gòu)的計(jì)算模型。

圖2 RecA蛋白介導(dǎo)下三鏈DNA形成模式圖

2 全錯(cuò)位排列問(wèn)題的三鏈DNA計(jì)算模型

集合｛1，2，…，n｝的一個(gè)全錯(cuò)位排列是該集合的一個(gè)滿足條件ij≠j（1≤j≤n）的全排列i1i2…in，即集合｛1，2，…，n｝的一個(gè)沒(méi)有一個(gè)數(shù)字在它的自然順序位置上的全排列，集合｛1，2，…，n｝的全錯(cuò)位排列問(wèn)題即是要求出該集合的所有全錯(cuò)位排列。

下面以3元集合｛1，2，3｝的全錯(cuò)位排列問(wèn)題為例，要求出集合｛1，2，3｝的所有全錯(cuò)位排列就是要求出數(shù)字1，2，3都不在各自的自然位置上的全排列。經(jīng)過(guò)仔細(xì)分析，容易發(fā)現(xiàn)問(wèn)題存在3個(gè)原子命題：① 數(shù)字1排在第二個(gè)位置上，記為x；② 數(shù)字2排在第一個(gè)位置上，記為y；③ 數(shù)字3排在第一個(gè)位置上，記為z。它們的否命題分別為：ˉx，ˉy，ˉz。問(wèn)題要求滿足條件：（1）若數(shù)字1在第二個(gè)位置上，則數(shù)字3不在第二個(gè)位置；（2）若數(shù)字2在第一個(gè)位置上，則數(shù)字3不在第一個(gè)位置；（3）若數(shù)字1在第三個(gè)位置上，則數(shù)字2不在第三個(gè)位置。上述問(wèn)題可以轉(zhuǎn)化為下面的命題公式：F＝（ˉx∨z）∧（ˉy∨ˉz）∧（x∨y）的滿足性問(wèn)題。

2.1 編碼

公式F中含有3個(gè)變?cè)?個(gè)子式，首先我們構(gòu)造兩組寡聚核苷酸片段，分別表示x，y，z和ˉx，ˉy，ˉz，比如x對(duì)應(yīng)的DNA鏈表示x取值為1，ˉx對(duì)應(yīng)的DNA鏈表示x取值為0，其它變量同樣。由于使用較長(zhǎng)探針能更有效地提取目的序列，所以每個(gè)變量均用完全不同的30bp的DNA表示，見(jiàn)圖3所示。公式F總共有23＝8個(gè)可能解，那么每一個(gè)解就由一條90bp的雙鏈DNA表示，而這些雙鏈DNA的模版鏈序列由那些表示每個(gè)變量取值的DNA序列串聯(lián)而組成。在此這些表示每個(gè)變量取值的DNA均作為探針來(lái)提取解。

圖3 編碼示意圖

2.2 生物操作

下面介紹相應(yīng)的生物操作。

Step0將編碼后的DNA片段放入DNA自動(dòng)合成儀，合成F的全部解空間序列［14］，然后用PCR擴(kuò)增成雙鏈DNA，它們構(gòu)成初始數(shù)據(jù)池tube0；將表示每個(gè)變量取值的DNA單鏈 的5′端以SS－Biotin標(biāo)記，作為探針使用，這里用SS－Biotin標(biāo)記的作用是增大結(jié)合空間，便于磁珠吸附。

Step1為了得到滿足第一個(gè)子式（ˉx∨z）的解，我們分三步進(jìn)行：

（1）在表示x＝0，z＝1的DNA單鏈的5′端添加一個(gè)RecA蛋白，再標(biāo)記上生物素。使這些DNA單鏈和抗原蛋白質(zhì)在含有ATPγS溶液混合在適宜條件下生成RecA蛋白－DNA復(fù)合體，把這些核蛋白細(xì)狀體的DNA鏈作為模板構(gòu)造探針，探針見(jiàn)圖4。

（2）將上述探針混合到數(shù)據(jù)池tube0中，探針在RecA蛋白介導(dǎo)下，將與滿足第一子式的解形成穩(wěn)定的三鏈結(jié)構(gòu)。

（3）將上步得到的三鏈DNA與表面涂有鏈親和素的磁珠混合，由于鏈親和素的高度親和力，三鏈DNA與探針一起被吸附在磁珠上，不滿足該子式的雙鏈DNA被分離出去。對(duì)三鏈DNA經(jīng)過(guò)洗脫及脫蛋白處理，第三條鏈從三鏈中分離出來(lái)，得到滿足第一個(gè)子式的雙鏈DNA。將這些雙鏈DNA裝入試管tube1。

圖4 RecA包裹的探針ˉx和z

Step2為了得到滿足第二個(gè)子式（ˉy∨ˉz）的解，同 Step1類(lèi)似，我們分三步進(jìn)行：

（1）將表示y＝0，z＝0的DNA單鏈與RecA蛋白，ATPγS溶液混合，在適宜條件下生成核蛋白細(xì)狀體，把這些核蛋白細(xì)狀體的DNA鏈作為模板構(gòu)造探針。

（2）將上述探針混合到數(shù)據(jù)池tube1中，探針在RecA蛋白介導(dǎo)下，將與滿足第二子式的解形成穩(wěn)定的三鏈DNA。

（3）利用磁珠分離技術(shù)，剔除不滿足該子式的雙鏈DNA，保留滿足條件的三鏈DNA。再對(duì)三鏈DNA經(jīng)過(guò)洗脫及脫蛋白處理，第三條鏈從三鏈中分離出來(lái)，得到滿足該子式的雙鏈DNA。將這些雙鏈DNA裝入試管tube2。

Step3為了得到滿足第三個(gè)子式（x∨y）的解，同樣分三步進(jìn)行：

（1）將代表x＝1，y＝1的DNA單鏈與RecA蛋白，ATPγS溶液混合，在適宜條件下生成核蛋白細(xì)狀體，把這些核蛋白細(xì)狀體的DNA鏈作為模板構(gòu)造探針。

（2）將上述探針混合到數(shù)據(jù)池tube2中，探針在RecA蛋白介導(dǎo)下，將與滿足第三子式的解形成穩(wěn)定的三鏈結(jié)構(gòu)。

（3）利用磁珠分離技術(shù)，剔除不滿足該子式的雙鏈DNA，保留滿足條件的三鏈DNA。再對(duì)三鏈DNA經(jīng)過(guò)洗脫及脫蛋白處理，第三條鏈從三鏈中分離出來(lái)，得到滿足該子式的雙鏈DNA。將這些雙鏈DNA裝入試管tube3。

Step4對(duì)tube3中的DNA進(jìn)行PCR擴(kuò)增和純化，即可讀出問(wèn)題的解。

本問(wèn)題的解是101，010，對(duì)應(yīng)得到三元集合｛1，2，3｝的全錯(cuò)位排列有231和312。

2.3 模型分析

全錯(cuò)位排列問(wèn)題是組合數(shù)學(xué)中的一類(lèi)重要問(wèn)題，文章利用DNA單鏈能在RecA蛋白的介導(dǎo)下與同源的雙鏈DNA匹配成穩(wěn)定的三鏈DNA這一性質(zhì)，提出了基于三鏈DNA的計(jì)算模型，與以往的模型相比，由于表示可能解的鏈都是雙鏈，彼此不會(huì)錯(cuò)配，也不會(huì)形成發(fā)夾結(jié)構(gòu)，表示探針的單鏈由于和RecA蛋白結(jié)合，也不會(huì)出現(xiàn)上面的錯(cuò)誤，這樣就大大降低了編碼復(fù)雜度和計(jì)算錯(cuò)誤率，同時(shí)可以進(jìn)行大規(guī)模的分子計(jì)算。

［1］Adleman L.Molecular computation of solution to combinatorial problems［J］.Science，1994，66（11）：1021－1024.

［2］許 進(jìn)，張 雷.DNA計(jì)算原理、進(jìn)展及難點(diǎn)（1）：生物計(jì)算系統(tǒng)及其在圖論中的應(yīng)用［J］.計(jì)算機(jī)學(xué)報(bào)，2003，26（1）：1－11.

［3］高 琳，許 進(jìn).圖的頂點(diǎn)著色問(wèn)題的DNA算法［J］.電子學(xué)報(bào)，2003，4：494－497.

［4］殷志祥，張風(fēng)月，許 進(jìn).0－1規(guī)劃問(wèn)題的DNA計(jì)算［J］.電子與信息學(xué)報(bào)，2003，25（1）：62－66.

［5］殷志祥，張風(fēng)月，許 進(jìn).基于分子信標(biāo)的DNA計(jì)算［J］.生物數(shù)學(xué)學(xué)報(bào)，2003，18（4）：1－5.

［6］殷志祥.圖與組合優(yōu)化中的DNA計(jì)算［J］.科學(xué)出版社，2004.12：16－23.

［7］方 剛，張社民，朱 巖，等.基于三鏈核酸的DNA計(jì)算［J］.生物信息學(xué)，2009，7（3）：181－185.

［8］楊 靜，殷志祥.基于抗原中介三鏈DNA結(jié)構(gòu)的0－1整數(shù)線性規(guī)劃［J］.計(jì)算機(jī)工程與應(yīng)用，2008，44（2）：76－79.

［9］孫 俠，殷志祥，張家秀.全錯(cuò)位排列問(wèn)題的基于表面的DNA計(jì)算模型［J］.生物數(shù)學(xué)學(xué)報(bào)，2009，24（3）：513－517.

［10］孫 俠，殷志祥，李 勇，等.全錯(cuò)位排列問(wèn)題的基于芯片的DNA計(jì)算模型［J］.大學(xué)數(shù)學(xué)，2010，26（2）：79－82.

［11］白寶璋，霍玉芹，劉福春，等.三鏈DNA的結(jié)構(gòu)與功能［J］.農(nóng)業(yè)與技術(shù)，1996，92（3）：27－28.

［12］Huamin JI，Ioydm S，Richard A G.Rapid isolation of cosmid insert DNA by triple－h(huán)elix－mediated affinity capture［J］.Genetic Analy－sis Tech Application，1994，112（2）：43－47.

［13］Rao B J，Dutreix M，Radding C M.Stable three－stranded DNA made by RecA protein［J］.Pro Natl Acad Sci USA，1991，88（8）：2984－2988.

［14］Braich R S，Chelyapov N，Johnson C，et al.Solution of a 20－variable 3－SAT problem on a DNA computer［J］.Science，2002，296（4）：499－502.

DNA Computing Model on Triple－stranded of the Whole Error Permutation Problems

Sun Xia， Yin Zhixiang， Zhao Qianjin， Xu Feng

Now people closely pay attention to a new DNA computing mode based on triple－stranded DNA.It is proved that single－strand DNA can match with homologous double－stranded into a stable three－stranded structure mediated by RecA protein and the extraction of the target DNA is feasible by the three－stranded DNA.The paper gives the DNA computing model on triple－stranded.Because feasible values are coded by double－stranded DNA，wrong hybridization does not take place and hairpin structure does not form.Thus in this way，encoding complexity and the errors in computation will be decreased.

triple－stranded DNA；Antigen intermediary；the whole error permutation problem

Q812

A

1673-1794（2012）02-0018-03

孫 俠（1980－），女，安徽鳳臺(tái)人，講師，碩士，研究方向：圖論，給合優(yōu)化及DNA計(jì)算。

國(guó)家自然科學(xué)基金（60873144，61170172，61073102，60973050），安徽省優(yōu)秀青年基金（06042088），安徽省教育廳自然科學(xué)基金項(xiàng)目（KJ2009B071Z，KJ2009B174Z），安徽省高等學(xué)校省級(jí)優(yōu)秀青年人才基金（2009SQRZ059，2011SQRL035）

2012-01-15