孫 俠，殷志祥，趙前進，許 峰

（安徽理工大學 理學院，安徽 淮南 232001）

基于三鏈DNA結構的全錯位排列問題算法

孫 俠，殷志祥，趙前進，許 峰

（安徽理工大學 理學院，安徽 淮南 232001）

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

三鏈DNA結構；抗原中介；全錯位排列問題

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

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

1 三鏈DNA的結構與功能［11］

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

圖1 三螺旋DNA鏈的空間結構與分子結構

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

圖2 RecA蛋白介導下三鏈DNA形成模式圖

2 全錯位排列問題的三鏈DNA計算模型

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

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

2.1 編碼

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

圖3 編碼示意圖

2.2 生物操作

下面介紹相應的生物操作。

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

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

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

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

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

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

Step2為了得到滿足第二個子式（ˉy∨ˉz）的解，同 Step1類似，我們分三步進行：

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

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

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

Step3為了得到滿足第三個子式（x∨y）的解，同樣分三步進行：

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

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

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

Step4對tube3中的DNA進行PCR擴增和純化，即可讀出問題的解。

本問題的解是101，010，對應得到三元集合｛1，2，3｝的全錯位排列有231和312。

2.3 模型分析

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

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

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

［3］高 琳，許 進.圖的頂點著色問題的DNA算法［J］.電子學報，2003，4：494－497.

［4］殷志祥，張風月，許 進.0－1規(guī)劃問題的DNA計算［J］.電子與信息學報，2003，25（1）：62－66.

［5］殷志祥，張風月，許 進.基于分子信標的DNA計算［J］.生物數(shù)學學報，2003，18（4）：1－5.

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

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

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

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

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

［11］白寶璋，霍玉芹，劉福春，等.三鏈DNA的結構與功能［J］.農(nóng)業(yè)與技術，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－），女，安徽鳳臺人，講師，碩士，研究方向：圖論，給合優(yōu)化及DNA計算。

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

2012-01-15