唐新玉　殷志祥

摘要：針對全錯位排列這類NP 完全問題，提出了一種基于DNA 自組裝的全錯位排列問題計算模型。該模型利用了DNA 分子間的自組裝能力，在具體操作時只用到凝膠電泳技術(shù)，在一定程度上減少了實驗誤差。

關(guān)鍵詞：全錯位排列問題；可滿足問題；DNA 自組裝

中圖分類號：O29 文獻標志碼：A

文章編號：1672-1098（2014）01-0080-03

自文獻[1]利用 DNA 計算方法解決了哈密爾頓路徑問題以后，越來越多的學(xué)者開始關(guān)注 DNA 計算并提出解決圖論問題的方法，如 0-1 規(guī)劃問題，圖著色問題，最小生成樹問題等。

DNA 自組裝是依賴分子間非共價鍵作用力自發(fā)的完成由小分子形成較大且復(fù)雜的結(jié)構(gòu)。文獻[2]、文獻[3]首次利用 DNA 分子構(gòu)成了自組裝 Tile 結(jié)構(gòu)，并利用其中一種瓦片結(jié)構(gòu)建立了多種復(fù)雜的算法模型。2000年，文獻[4]通過實驗給出了自組裝 DNA 計算模型求解累積異或運算的實現(xiàn)過程和方法。2002 年，文獻[5]將自組裝 DNA 計算的基本思想用于求解布爾邏輯表達式并將其實現(xiàn)邏輯電路。2004年，文獻[6]利用 DX Tile 結(jié)構(gòu)實現(xiàn)了一維元胞自動機，在此基礎(chǔ)上分析證明了用 DNA Tile 自組裝結(jié)構(gòu)實現(xiàn)任何元胞自動機的可行性。Tile 自組裝還被用來解決組合優(yōu)化問題[7-8]，2008年，文獻[9]在前任的基礎(chǔ)上提出了求解可滿足性問題的非確定性自組裝模型。

全錯位排列是組合數(shù)學(xué)中常見的一類問題，文獻[10-11]給出了基于表面、基于芯片以及基于三鏈的 DNA 計算模型，與以往模型相比，本文給出的模型操作更為簡單，更易得出可行解。

1全錯位排列問題

全錯位排列問題即“裝錯信封問題”，可用數(shù)學(xué)語言描述如下：

對于n元集合{1，2，…，n}，當滿足條件 ij≠ j （1≤j≤n）時，得到的全排列 i1，i2，…，in 稱為全錯位排列。

本文以3元集合{1，2，3}為例具體說明。即求數(shù)字1，2，3都不在各自的自然位置上的全排列。經(jīng)分析知，存在3個原子命題：①數(shù)字1排在第二位，記為u ；②數(shù)字2排在第一位，記為v；③數(shù)字3排在第一位，記為w。它們的否命題分別為：u′表示數(shù)字1在第三位；v′表示數(shù)字2在第三位； w′表示數(shù)字3在第二位。問題需滿足條件：①若數(shù)字1在第二位，則數(shù)字3不在第二位；②若數(shù)字2不在第一位，則數(shù)字3不在第一位；③若數(shù)字1在第三位，則數(shù)字2不在第三位。上述問題可以轉(zhuǎn)化為

2操作過程

步驟 1

1） 給出6 種短的寡聚核苷酸來代表u， v，w和u′ ，v′ ，w′（其中u， v，w對應(yīng)的寡聚核苷酸取值為1，u′ ，v′ ，w′對應(yīng)的寡聚核苷酸取值為0），并把它們的補鏈記為u，v，w和u′ ，v′ ，w′ （其中第一段不參加反應(yīng)，第二段為u， v，w和u′，v′，w′的前四個堿基的補，第三段為u， v，w和u′，v′，w′的后四個堿基的補）（見表1）。由此，u，v，w和u′，v′，w′的完全補鏈u，v，w和u′，v′，w′也可以確定。

2） 合成所需的8 種DNA 鏈放入數(shù)據(jù)池中，然后進行純化和PCR 擴增（見圖1a）

步驟2

首先判斷子句（u′∨w），往數(shù)據(jù)池中加入足量的u′ ，w的補鏈u′，w，數(shù)據(jù)池中含有u′，w的DNA序列將與補鏈u′ ，w發(fā)生雜交反應(yīng)形成發(fā)夾結(jié)構(gòu)（見圖1b），與此同時，使式（1）中子句（u′∨w）為假的組合不形成發(fā)夾結(jié)構(gòu)，通過凝膠電泳，將不符合條件的DNA鏈分離出去，剩余的DNA鏈即為使（u′∨ w）為真的鏈。

（a） 初始數(shù)據(jù)池中的所有DNA 組合（b）加入補鏈DNA 后形成發(fā)夾結(jié)構(gòu)

圖1初始DNA 鏈與補鏈雜交圖

步驟3

在步驟2 得到的產(chǎn)物中，加入u′，w的完全補鏈u′，w，把溫度調(diào)整到適當范圍內(nèi)，u′和u′，w和

w雜交，即發(fā)夾打開（見圖2）。在此利用凝膠電泳得到DNA 單鏈。

步驟4

重復(fù)步驟2、步驟3，檢查式（1）中的剩余子句，提出F中所有不滿足條件的DNA 鏈后，最后剩余的DNA 鏈滿足F式的所有子句，也就得出了全錯位排列的排列順序。通過測序知為101 和010，所以231 和312 即為所求的全錯位排列。

圖2發(fā)夾結(jié)構(gòu)打開過程

3結(jié)論

通過把全錯位排列問題轉(zhuǎn)化為可滿足問題，利用自組裝的方法最終得到三元全錯位問題的具體排列順序。這種方法在實現(xiàn)過程中只用到凝膠電泳操作，在一定的程度上減少了因生物操作過多而

引起的各種實驗誤差，便于計算三元以上的全錯位排列問題。

參考文獻：

[1]LEONARD ADLEMAN. Molecular computation of solution to combinatorial problems[J]. Science， 1994，Z66（11）：1 021-1 024.

[2]SEEMAN N C.DNA nanotechnology： novel DNA constructions[J].Annual Review of Biophysics and Biomolecular Struture，1998，27：225-248.

[3]MAO C， SUN W， SEEMAN N C. Designed two dimensional DNA Holliday junction arrays visualized by atomic force microscopy[J].Journal of the American Chemical Society，1999，121（23）：5 437-5 443.

[4]MAO C，LABEAN T H，RIEF J H， et al. Logical computation using algorithmic self-assembly of DNA tri-crosser molecules [J].Nature，2000，407（6803）：493-496.

[5]CARBONE A， SEEMAN N C. Circuits and programmable self-assembling DNA [J].Academy of Sciences of the United States of America，2002，99（20）：12 577-12 582.

[6]ROTHEMUND P W K， PAPADAKIS N， WINFREE E. Algorithmic self-assembly of DNA Sierpinski triangles[J].PloS Biology，2004，2（12）：2 041-2 053.

[7]MICHAIL G L， LABEAN T H.2D DNA self-assembly for satisfiability[J].DIMACS Series in Discrete Mathematics and Theoretical Computer Science，1999，44：139-152.

[8]BRUN Y. Solving NP-complete problems in the tile assembly model [J].Theoretical Computer Science，2008，395（1）：31-36.

[9]BRUN Y. Solving satisfiability in the tile assembly model with a constant-size tile set[J].Journal of Algorithms，2008，63（4）：155-156.

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

[11]孫俠，殷志祥，趙前進， 等. 基于三鏈DNA結(jié)構(gòu)的全錯位排列問題算法[J].滁州學(xué)院學(xué)報，2012，2（14）：18-20.

[12]RAVINDERJIT S BRAICH，NICKOLAS CHELYAP-OV，CLIFF JOHNSON，et a1.Solution of a 20-variable 3-SAT problem On a DNA computer[J].Science，2002，296（5567）：499-502.

[13]XU JIN，QIANG XIAO-LI，F(xiàn)ANG GANG，ct a1.A DNA computer model for solving vertex coloring problem[J].Chinese Science Bulletin，2006，51（20）：2 541-2 549.

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

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

[16]宋勃生，殷志祥， 甄誠， 等.DNA自組裝的可滿足性問題模型[J]. 小型微型計算機系統(tǒng)，2011，9（32）：1 872-1 875.

（責(zé)任編輯：何學(xué)華）