唐新玉，殷志祥

(安徽理工大學理學院，安徽 淮南 232001)

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

DNA 自組裝是依賴分子間非共價鍵作用力自發(fā)的完成由小分子形成較大且復雜的結(jié)構(gòu)。文獻［2］、文獻［3］首次利用DNA 分子構(gòu)成了自組裝Tile 結(jié)構(gòu)，并利用其中一種瓦片結(jié)構(gòu)建立了多種復雜的算法模型。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ù)學中常見的一類問題，文獻［10－11］給出了基于表面、基于芯片以及基于三鏈的DNA 計算模型，與以往模型相比，本文給出的模型操作更為簡單，更易得出可行解。

1 全錯位排列問題

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

對于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對應的寡聚核苷酸取值為1，u'，v'，w'對應的寡聚核苷酸取值為0)，并把它們的補鏈記為和(其中第一段不參加反應，第二段為u，v，w和u'，v'，w'的前四個堿基的補，第三段為u，v，w和u'，v'，w'的后四個堿基的補)(見表1)。由此，和的完全補鏈和也可以確定。

表1 所有變量和其補鏈的編碼

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

步驟2

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

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

步驟3

步驟4

重復步驟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］.大學數(shù)學，2010，26(2):79－82.

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

［12］RAVINDERJIT S BRAICH，NICKOLAS CHELYAPOV，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］.生物信息學，2009，7(3):181－185.

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

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