ＤＮＡ編碼問題及其復雜性研究
2008-12-31 00:00:00張凱耿修堂肖建華張勛才
計算機應用研究 2008年11期
(華中科技大學 控制科學與工程系， 武漢 430074)
摘要：高質量的DNA編碼可以避免DNA分子間的非特異性雜交，提高DNA計算的有效性和可靠性。首先對DNA編碼的約束條件進行歸類，分析了各編碼約束對編碼質量的影響；然后研究了編碼質量、編碼數量、序列長度與DNA計算可靠性、有效性、可擴充性之間的關系；最后通過類比DNA編碼問題和圖的獨立集問題，說明了求解最大DNA序列集合問題是NP完全的。
關鍵詞：DNA計算; DNA編碼設計; 組合優化
中圖分類號：TP301.5文獻標志碼：A
文章編號：1001-3695(2008)11-3264-04
DNA sequence design problem and complexity analysis
ZHANG Kai， GENG Xiu-tang， XIAO Jian-hua， ZHANG Xun-cai
(Dept. of Control Science Engineering， Huazhong University of Science Technology， Wuhan 430074， China)
Abstract:High quality DNA sequences can prevent the interference between different DNA molecules， and improve the reliability and effectiveness of DNA computation. At first， classified DNA constraints， and analyzed the influence of constraints on the quality of DNA sequences. Then the paper studied the relationship between DNA sequence and the efficiency of DNA computing. Finally， the paper carried on the analogy to DNA sequence design problem and graph independent set problem， and proved the maximum DNA sequences set problem was a NP complete problem.
Key words：DNA computing; DNA sequences design; combinatorial optimization
0引言
20世紀70年代初期，科學工作者發現大量源于實際的組合優化問題非常難解，并定義和證明這些問題為NP完全問題。隨后出現了一系列優化計算方法，如人工神經網絡、遺傳、模擬退火、蟻群優化和粒子群算法，也不能徹底解決復雜的組合優化問題。1994年，美國南加州大學的Adleman[1]使用DNA分子成功求解出七個城市的有向Hamilton路問題。隨后，許多學者提出了求解其他NP完全問題的DNA計算模型[2~5]。這種基于生物分子的計算模式在求解NP完全問題時顯示出了極大潛力。1997年，Garzon等人[6]指出生物分子計算的核心是對DNA序列進行編碼，從而將現實問題映射到DNA分子上，再通過生物實驗獲得代表問題解的DNA分子。因此，DNA編碼質量的優劣直接決定了DNA計算的效率。
近年來，許多學者對DNA編碼問題進行了深入的研究，并提出了各種DNA編碼約束和各種算法來編碼DNA序列。Frutos等人[7]提出的基于模板的DNA編碼方法，利用漢明距離和反補漢明距離減少編碼間的相似程度。Tanaka等人[8]提出了評價DNA序列的適應度函數，用模擬退火算法設計DNA序列，并給出自補漢明距離等約束來評價DNA編碼質量。Feldkamp等人[9]利用有向樹編碼DNA，通過限制子序列僅允許出現一次，降低編碼間的相似程度。Deaton等人[10]提出了基于自由能的動態規劃DNA編碼算法。這些算法使用不同編碼約束評價DNA序列的質量。
1DNA編碼問題及編碼約束
DNA編碼問題可以表示為，設X=5′-x1x2…xn-3′為一個長度為n的單鏈DNA序列。其中：xi代表堿基，xi∈{A，C，G，T}。設S為長度為n的DNA序列集合，顯然集合S的大小為｜S｜=4n。求S的一個子集CS，使得C中任意DNA序列滿足給定的DNA編碼約束，如漢明距離、相似度、H-measure、解鏈溫度、最小自由能等。這些編碼準則可以分成四類：a)基于漢明距離的編碼約束；b)化學熱力學約束；c)DNA二級結構約束；d)DNA堿基組成約束。
11基于漢明距離的編碼約束
DNA分子之間的非特異性雜交是指不完全互補的兩單鏈DNA分子間產生的錯配雜交，會導致DNA計算過程中出現錯誤，極大地降低了DNA計算的效率。基于漢明距離的編碼約束可以有效地限制DNA序列間的非特異性雜交，從而使每條DNA序列X僅與其補鏈XC生成雙螺旋結構。基于漢明距離的編碼約束共有七個，分別為：
a)漢明距離約束。兩個DNA序列的漢明距離是所有對應位置堿基不同的總數。設DNA序列X和Y分別為X=5′-x1x2…xn-3′和Y=5′-y1y2…yn-3′，其漢明距離H(X，Y)的計算為
H(X，Y)=∑ni=1h(xi，yi)，h(xi，yi)=0，若xi=yi1，若xi≠yi(1)
DNA編碼設計中，漢明距離被用來描述兩個DNA序列的不相似程度。DNA序列X和Y的漢明距離越大，則兩序列相同的堿基個數就越少，因此X與YC(Y的補序列)之間互補的堿基個數就越少，X和YC之間發生雜交的可能性就越小；反之，漢明距離越小，X與YC發生非特異性雜交的可能性就越大。
b)相似度約束。它被用來描述兩個DNA序列X和Y堿基組成的相似程度。滿足相似度約束的兩條DNA鏈的同向序列盡可能惟一，且序列滑動后也盡量不會重復。相似度可以通過計算序列X和Y之間移動后取最小漢明距離得到，其計算如下：
similarity(X，Y)=min-n＜k＜nH(X，σk，(Y))
(2)
其中：H(*，*)表示漢明距離。當k>0時，σk表示右移；當k＜0時，σk表示左移，k表示移動的位數。如果X和Y經過距離為k的移動后漢明距離減小，那么similarity的值也隨之減小。Similarity值較小時序列X和Y就非常相似，序列X和YC之間互補的堿基就多，容易出現非特異性雜交；反之，當similarity值較大時，X和YC不會發生雜交。
c)H-measure約束。Garzon等人[11]提出H-measure約束，將核酸堿基互補的信息擴充到漢明距離中，計算如下所示：
H-measure(X，Y)=min-n＜k＜nH(X，σK(Y))(3)
H(X，Y)=∑ni=1bp(xi，yi)，bp(xi，yi)=1，若xi≠yi0，若xi=yi
其中：xi，yi∈{A，C，G，T}。當k>0時，σk表示右移；當k<0時，σk表示左移，k表示移動的位數。Y表示DNA序列Y的補鏈。如果一條DNA序列移動后和另一條DNA序列的片段發生Watson-Crick互補，H-measure的值就減少為這兩條DNA序列移動后的漢明距離。也就是說，如果H-measure值較小，則兩條DNA序列非常可能相互粘貼；如果H-measure值很大時，則Y與X幾乎不存在互補的DNA子片段，因而不會發生雜交。
d)反補漢明距離約束。DNA計算實驗中，單鏈DNA分子在溶液中任意擴散，因此X可能與Y的反向序列YR發生雜交。反補漢明距離H(X， YRC)被用來描述X與YRC之間的相似程度。H(X， YRC)越大，說明X和YRC不同的堿基個數越多，那么它們互補的堿基對就越少，因此不容易出現非特異性雜交；反之，H(X，YRC)越小，X和YR越容易出現非特異性雜交。
e)自補漢明距離約束。DNA分子以一定濃度存在于溶液中，由于空間距離較近，容易發生自身的雜交。Tanaka等人[8]提出了自補漢明距離約束，以避免DNA分子和其自身的反序列雜交。由于考慮DNA序列和其自身的反序列互補，該約束用H-measure計算公式來表示：
H_measure(X，Y)=min-n＜k＜nH(X，σk(XR))
(4)
該約束與H-measure類似，當k>0時，σk表示右移；當k<0時，σk表示左移，k表示移動的位數。XR表示DNA序列X的反鏈。當H-measure值較小時X容易與XR相互雜交；當H-measure值很大時說明X和XR幾乎不存在互補的DNA子片段，因而不會自身雜交。
f)序列3′端H-measure約束。如果一個DNA序列的3′端與另一個序列的一部分互補，則在PCR過程中會發生錯誤的擴增。為了避免該情況的發生，Tanaka等人[8]提出評價函數：
H-measure_3end(X，Y)=CN(X，Y(k))(5)
這里：CN(X，Y(k))表示序列X與序列Y的3′端的k位堿基構成的子序列之間互補的位數；k為常數。
g)重疊子序列約束(最小子串約束)。其要求長度為m的子序列在DNA中最多出現一次，即任取兩段長度為m的子序列都不會重復。Feldkamp等人[9]在算法中提出該約束條件，它可以保證任意兩個DNA序列不會出現過長的連續相同子序列，從而降低了DNA序列間的相似程度。
12化學熱力學約束
DNA計算要求參加反應的DNA序列具有相似的化學熱力學特性。例如DNA分子具有一致的解鏈溫度才能保證特異性雜交的有效性。DNA化學特性約束通常包含：
a)GC含量約束。GC含量即為DNA序列中堿基G和堿基C的個數或者百分比。由于DNA分子中堿基G和C之間的氫鍵作用力比堿基A與T之間的作用力大，DNA序列的GC含量影響該序列的化學性質。例如解鏈溫度可以由GC含量計算得到。DNA計算要求DNA分子具有一致的GC含量。
b)解鏈溫度約束。解鏈溫度(Tm)是雙鏈DNA分子在加溫變性過程中，有50%的DNA分子打開雙鏈變成單鏈時的溫度。解鏈溫度是評價DNA分子化學熱力學穩定性的一個重要參數。DNA計算要求DNA分子具有一致的解鏈溫度。
影響解鏈溫度Tm的因素為DNA分子組成、DNA分子濃度、溶液pH值等。可選擇三個公式計算Tm。
(a)根據Wallace法則[12]，計算：
Tm=(A+T)×2℃+(C+G)×4℃ (＜20bp)(6)
(b)根據GC百分含量， 計算：
Tm=81.5+16.6×log10([salt]/(1.0+0.7×[salt]))+
41×GC(x)-500/｜x｜(7)
(c)根據Nearest-Neighbors熱力學模型[13]， 計算:
Tm=(1 000×ΔH)/[ΔS+R×ln(C/4)]-273.15(8)
ΔH°是相鄰堿基的總焓；ΔS°是相鄰堿基的總熵；R為氣體常數(1.987cal/Kmol)；C為DNA分子濃度。
c)化學自由能約束。自由能(ΔG)是兩單鏈DNA分子雜交形成雙鏈DNA的能量變化。由于DNA雜交通常放出熱量，自由能的變化通常為負值，即ΔG＜0。ΔG是DNA雙鏈穩定性的度量，其絕對值越高，DNA雙鏈越穩定。兩單鏈DNA分子發生非特異性雜交，是由于它們形成雙鏈時ΔG較大，形成的雙鏈較穩定。為防止DNA序列間的非特異性雜交，則要求DNA解集C中的序列都滿足最小自由能約束。給定最小自由能變化閾值ΔGmin，使DNA解集C中任意兩個DNA分子發生非特異性雜交的ΔG都大于該閾值ΔGmin，從而不能形成穩定的雙鏈結構，阻止非特異性雜交的發生。
自由能采用Nearest-Neighbor熱力學模型[13]，計算如下：
ΔG=∑iniΔG(i)+ΔG(ini GC)+ΔG(ini AT)+ΔG(sym)(9)
其中：ΔG(i)表示近鄰堿基對的自由能，如ΔG(1)= ΔG(AA/TT)，ΔG(2)=ΔG(TA/AT)等，共包含10種Watson-Crick近鄰堿基對組合；ni表示ΔG(i)的個數；ΔG(ini GC)表示起始位置GC配對的修正值；ΔG(ini AT)表示起始位置AT配對的修正值；ΔG(sym)表示自補DNA序列的修正值。
13DNA二級結構約束
如果單鏈DNA 分子形成了二級結構，它就不能有效地與補鏈發生特異性雜交。因此DNA計算要求設計的單鏈DNA分子不含有二級結構。
1)發卡結構約束單鏈DNA分子產生二級結構通常由自身反向折疊而形成，發卡結構為典型的自身折疊結構，如圖1所示。通過限制DNA反向互補堿基的個數，可以限制發卡結構的形成。
2)連續性約束如果一個DNA序列中，相同的堿基連續出現，如“AAA”“CCC”“TTT”“GGG”，則在堿基分子氫鍵力作用下出現不穩定的二級結構。DNA計算要避免使用具有連續堿基的DNA序列。
14DNA堿基組成約束
這組編碼準則約束DNA序列的堿基組成，包括：
a)限定子序列約束。生物分子實驗常用到各種生物酶，這些酶是具有特殊功能的DNA分子，如連接酶可以連接DNA分子，限制性內切酶可以斷開DNA分子。這些生物酶具有固定的堿基組成，需要在DNA序列設計時避免使用有特殊功能的DNA子序列，否則在生物實驗中會出現錯誤。
有些生物分子實驗需要對DNA序列的堿基{A，C，G，T}進行限制，需要保留一個或多個堿基。由于堿基對G-T幾乎與堿基對A-T一樣的穩定，即堿基G可以與堿基A一樣同堿基T相互綁定，導致發生非特異性雜交。如果DNA序列設計要求GC百分比含量滿足一定的要求，假如既可以用堿基G也可以用堿基C，通常選擇C而不選擇G。此外PCR擴增為了讓其3′端不產生互補序列，盡量只用兩個堿基進行編碼即{C，T}。對單個堿基可以看做長度為1的子序列。
b)DNA模板序列約束。DNA計算模型要求DNA序列某些位置具有固定的堿基組成，如Whiplash PCR[14]模型為了有效擴增，DNA分子末端要求以堿基T作為末端，其模板為5′--nnnnnnT-3′。以該模板產生的DNA序列，鏈長為7，且序列末端的堿基均為T。
15DNA編碼約束分析
這些編碼約束條件中，基于漢明距離的編碼約束和化學自由能需要序列之間的比對。序列間的比對是為了有效避免(減少)DNA分子間的非特異性雜交，如圖2所示。
隨著DNA解集中序列數量的增加，其序列間比對的計算量階乘級上升。而其他的編碼約束都是對單條DNA序列的約束，其計算量相對較小。可見DNA編碼問題的復雜性在于序列間的相互約束，排除非特異性雜交DNA序列是DNA編碼問題的重點。
2DNA編碼問題復雜性研究
DNA計算的基本問題是提高DNA計算的可靠性、有效性和可擴充性。可靠性和有效性與DNA編碼的質量息息相關，它要求任意兩個DNA序列不發生非特異性雜交。可擴充性是指在保證可靠性的前提下，提高解決問題的規模。這就是說，編碼質量越高，DNA計算的可靠性越高；編碼數量越多，解決問題的應用規模也就越大。但事實上，編碼質量和數量之間存在相互制約的關系：編碼質量越高則滿足條件的編碼數量就越少。因此DNA編碼問題是典型多目標組合優化問題[15]，具有以下特點：
a)多目標。隨著DNA計算求解問題規模的不斷增大，需要使用的DNA序列數量急劇增多。為了保證DNA計算的有效性和可靠性，需要嚴格的編碼約束以提高編碼質量。DNA序列越長，其合成的成本就越高，且在實驗中控制DNA長鏈的難度會越大。這樣，DNA編碼問題的目標為：(a)DNA序列長度盡可能短；(b)編碼約束盡可能強；(c)編碼數量盡可能多。然而，這些目標相互存在著沖突。對于給定長度的DNA編碼，編碼約束越強則編碼數量就越少；DNA鏈長越短，滿足條件的DNA數量也越少。這種多目標性DNA編碼問題的復雜性和計算量急劇增加。
b)復雜性。DNA編碼受到堿基距離約束、化學熱力學約束、DNA二級結構約束、DNA分子組成約束等多種編碼規則的組合約束，在計算量上是NP完全問題，即隨著問題規模的增大，對于求解最優DNA序列集合的計算量呈指數增長。如果設計鏈長為n的一組DNA序列，由于每位的堿基有｛A，T，G，C｝四種可能，其解空間為4n。如果要求DNA序列集合最大，僅考慮DNA序列之間非特異性雜交的限制，對于長度為n的DNA序列，就等價于求解4n個頂點的圖的最大獨立集問題。如果還考慮DNA二級結構等其他約束，問題就變得更加復雜。筆者將DNA序列的雜交關系網絡和圖的獨立集問題作類比，說明DNA編碼問題的復雜性。
1）DNA序列雜交關系網絡給定一個單鏈DNA雜交網絡N(S，H)，S為長度n的DNA序列集合，H為S中任兩條DNA雜交關系的集合，如圖3所示。si代表單鏈DNA序列，h(si，sj)∈H表示DNA序列si和sj可以非特異性雜交。設S′是S的子集S′S，如果對任意兩個DNA序列si，sj∈S′，h(si，sj)H，則S′中任意兩個序列都不能非特異性雜交，則S′為DNA計算可用編碼集合，即為DNA編碼問題的解。黑色的點代表相互不能非特異性雜交的DNA分子。
2）圖的獨立集問題給定一個圖G=(V，E)，V是頂點vi的集合，E是邊e(vi，vj)的集合，如圖4所示。V′是V的子集VV，如果對任意兩個頂點vi，vj∈V′，e(vi，vj)E，則稱V′為G的一個獨立集。黑色的點表示圖的一個獨立集。
兩個問題的對應關系如下：
GN， VS， EH， V′S′，visi， e(vi，vj)h(xi，xj)
可見，DNA序列設計問題等價于圖的獨立集問題。為了提高DNA計算模型的可擴充性，以解決更大規模的計算問題，DNA編碼問題需找到盡可能多的滿足約束的DNA序列，即求解滿足約束的最大DNA集合。而求解圖的最大獨立集為NP完全問題。因此，DNA編碼問題的計算量也是NP完全的。
3結束語
DNA編碼質量的優劣直接決定DNA計算效率的高低。為了提高DNA計算的可靠性、有效性，必須設計高質量的DNA編碼。本文對各類DNA編碼算法的編碼約束進行歸類，研究了各編碼約束對DNA編碼質量的影響；分析了DNA編碼問題具有多目標、多約束的復雜組合優化問題的特點；通過類比DNA編碼問題和圖的獨立集問題，說明了求解最大DNA序列集合問題是NP完全的。
參考文獻：
［1］ADELMAN L M. Molecular computation of solutions to combinatorial problems[J].Science，1994，266（5187）:1021-1024.
［2］LIPTON R J. DNA solution ofthe hard computation problems[J].Science，1995，268(4):542-545.
［3］OUYANG Qi. DNA solution of the maximal clique problem[J].Science，1997，278(17):446-449.
［4］BRAICH R S，CHELYAPOV N，JOHNSON C.Solution of a 20-variable 3-SAT problem on a DNA computer[J].Science，2002，296(5567):499-502.
［5］FAULHAMMER D，CUKRAS A，LIPTON R J. Molecular computation: RNA solutions to chess problems[C]//Proc of National Academy of Sciences.2000: 1385-1389.
［6］GARZON M， DEATON R， NEATHERY P. On the encoding problem for DNA computing[C]//Proc ofthe 3rd DIMACS Workshop on DNA-based Computers. 1997:230-237.
［7］FRUTOS A G， LIU Qing-hua， THIEL A J，et al. Demonstration of a word design strategy for DNA computing on surface[J].Nucleic Acids Research，1997，25(23):4748-4757.
［8］TANAKA F， NAKATSUGAWA M，YAMAMOTO M.Towards a general purpose sequence design system in DNA computing[C]//Proc of the 2002 Congress on Evolutionary Computing， CEC’02. 2002:73-78.
［9］FELDKAMP U， RAUHE H， BANZHAF W. Software tools for DNA sequence design[J].Genetic Programming and Evolvable Machines，2003，4(2):153-171.
［10］DEATON R， CHEN J， BI H， et al. A software tool for generating non cross hybridization libraries of DNA oligonucleotides[C]//Proc of the 8th Int Workshop on DNA-based Computing. 2002:252-261.
［11］GARZON M， DEATON R， NINO L F. Genome encoding for DNA computing[C]//Proc of the 3rd DIMACS Workshop on DNA-based Computing. 1999:230-237.
［12］WALLACE R B， SHAFFER F， MURRHY R F，et al.Hybridzation of synthetic oligodeoxyribonucleotides to phichi 173 DNA:the effect of single base pair mismatch[J].Nucleic Acids Research，1979，6(11)：3543-3557.
［13］LUCIA S. A unified view of polymer， dumbbell， and oligonucleotide DNA nearest neighbor thermodymamics[C]//Proc ofNational Academy of Sciences. 1998:1460-1465.
［14］ARITA M， NISHIKAWA A， HAGIYA M. Improving sequence design for DNA computing[C]//Proc of the Genetic and Evolutionary Computation Conference (GECCO-2000). 2000:875-882.
［15］SHIN S Y， LEE I H， DONGMIN K. Multi objective evolutionary optimization of DNA sequences for reliable DNA computing[J].IEEE Trans on Evolutionary Computation，2005，9(2):143-158.
