王艷釵，張　會，董亞非,

(1.陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，陜西西安 710119； 2.陜西師范大學(xué)生命科學(xué)學(xué)院，陜西西安 710119)

DNA納米顆粒共聚體在圖的連通度問題中的應(yīng)用

王艷釵1，張會2，董亞非1,2

(1.陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，陜西西安 710119； 2.陜西師范大學(xué)生命科學(xué)學(xué)院，陜西西安 710119)

本文提出了一種利用DNA納米金顆粒共聚體的自組裝過程解決圖論中一個NP完全問題—連通度問題的DNA計(jì)算方法，構(gòu)建了解決圖的連通度問題的三維DNA自組裝計(jì)算模型.根據(jù)設(shè)計(jì)的算法，首先需要根據(jù)具體的圖的連通度問題設(shè)計(jì)用于自組裝的DNA納米金顆粒共聚體，然后根據(jù)算法經(jīng)過一系列實(shí)驗(yàn)設(shè)計(jì)來求解連通度問題.本文利用Visual DSD仿真該實(shí)驗(yàn)的可行性，為下一步DNA自組裝計(jì)算模型的應(yīng)用提供了可行的方案.

DNA計(jì)算；DNA納米金顆粒；圖的連通度；三維模型

1　引言

1994年，Adleman[1]首次利用線性DNA 分子解決了一個7個頂點(diǎn)的Hamilton路問題.隨后，許多科學(xué)家的目光被吸引到分子計(jì)算領(lǐng)域.1995年，Lipton[2]建立了解決可滿足問題的DNA計(jì)算機(jī).兩年后，Ouyang等[3]提出了解決最大團(tuán)問題的DNA計(jì)算模型.最近，張成[4,5]利用環(huán)形DNA分子求解了最大團(tuán)問題同時利用自組裝DNA鏈置換設(shè)計(jì)分子邏輯計(jì)算模型.以上方法都是利用DNA分子計(jì)算NP完全問題.近年來，很多研究學(xué)者提出了利用如RNA[6]、質(zhì)粒[7]和瓦片[8,9]等多種不同的分子作為工具進(jìn)行計(jì)算.2007年，Brun[10]利用瓦片進(jìn)行了加法和乘法運(yùn)算.目前利用DNA自組裝引導(dǎo)納米粒子形成三維納米結(jié)構(gòu)的技術(shù)極大地推進(jìn)了許多基礎(chǔ)科學(xué)問題的研究.Yan[11]設(shè)計(jì)出了用DNA納米金顆粒共聚體的自組裝過程構(gòu)建納米金顆粒三維管狀結(jié)構(gòu)的方法，通過控制納米金顆粒的大小，可以分別形成疊環(huán)、單螺旋、雙螺旋和嵌套螺旋等不同的結(jié)構(gòu).Alivisatos[12]報道了構(gòu)建納米金顆粒三維結(jié)構(gòu)的方法，他們利用DNA鏈修飾的納米金顆粒自組裝形成金字塔結(jié)構(gòu)，通過調(diào)節(jié)金字塔四個頂點(diǎn)的納米金顆粒的大小，構(gòu)建了納米金顆粒的三維手性結(jié)構(gòu).2012年，楊玉星等[13]提出一種解決Ménage問題的粘貼DNA算法并簡要分析了該算法的復(fù)雜度.2013年，李肯立[14]DNA自組裝模型來求解N皇后問題的DNA計(jì)算方法.算法通過減少實(shí)驗(yàn)操作步驟數(shù)，降低了生化解的錯誤率.

最近，DNA自組裝和DNA/AuNP被廣泛應(yīng)用在邏輯門和數(shù)字環(huán)路的設(shè)計(jì)，2010年，張成等[15]建立了一個基于環(huán)狀DNA的邏輯門系統(tǒng).證明了邏輯結(jié)果容易通過熒光信號和納米金組裝進(jìn)行檢測.2011年，張成等[16]構(gòu)建了一個邏輯模型，該模型能夠用于H1N1病毒基因的檢測.2011年，Qian和 Winfree等[17]實(shí)驗(yàn)性的論證了數(shù)個數(shù)字邏輯環(huán)路.解決了一個由130條DNA鏈組成的在4-位(bit)平方根環(huán)路的問題.2013年，楊靜等[18]利用納米金顆粒構(gòu)建了一個“YES”和“AND”的邏輯門.2014年，張成等[19]建立了一個基于環(huán)狀DNA用納米金顆粒來控制鏈置換過程.

本文提出了一種利用DNA納米金顆粒共聚體的自組裝過程解決圖論中一個NP完全問題—連通度問題的DNA計(jì)算方法，構(gòu)建了解決圖的連通度問題的三維DNA自組裝計(jì)算模型.根據(jù)設(shè)計(jì)的算法，首先需要根據(jù)具體的圖的連通度問題設(shè)計(jì)用于自組裝的DNA納米金顆粒共聚體，然后根據(jù)算法經(jīng)過一系列實(shí)驗(yàn)過程來求解連通度問題.另外還通過了Visual DSD和NUPACK對該生物實(shí)驗(yàn)進(jìn)行了仿真，來說明該實(shí)驗(yàn)的可行性.與傳統(tǒng)的電子計(jì)算機(jī)相比，降低了計(jì)算的復(fù)雜度，所使用的生物化學(xué)實(shí)驗(yàn)技術(shù)也很成熟且便于操作，為下一步DNA自組裝計(jì)算模型的應(yīng)用提供了可行的方案.

2　基于DNA納米顆粒共聚體分子算法

2.1連通度問題

連通度問題是圖論中的一個NP完全問題,它對于構(gòu)造可靠通訊網(wǎng)絡(luò)有很重要的意義，由于它與網(wǎng)絡(luò)模型和組合優(yōu)化有密切關(guān)系,因此具有很重要的理論和應(yīng)用價值.

定義1若G≠Kp是一個連通圖，φ≠V1?V(G)，若G-V1非連通，則稱V1是圖G的頂點(diǎn)割.若頂點(diǎn)割V1含k個頂點(diǎn)，也稱V1是k頂點(diǎn)割.

設(shè)G是p階連通圖，令

(1)

稱κ(G)為G的連通度.

定義2若G≠Kp是一個連通圖，φ≠E1?E(G)，若G-E1非連通，則稱E1是圖G的邊割.若邊割E1含k條邊，也稱E1是k邊割.

設(shè)G是p階連通圖，令

(2)

稱λ(G)為G的邊連通度.從而一個非平凡連通圖的邊連通度就是使這個圖成為非連通圖所需要去掉的最小邊數(shù).

定理1G是p階簡單圖，則以下幾條結(jié)論成立：

(1)κ(G)≤δ(G)，λ(G)≤δ(G)；

(2)κ(G)≤p-1，等號成立當(dāng)且僅當(dāng)G?Kp；

(3)λ(G)≤p-1，等號成立當(dāng)且僅當(dāng)G?Kp;

(4)對G的任意一個頂點(diǎn)u，κ(G)-1≤κ(G-u)；

(5)對G的任意一條邊e，λ(G)-1≤λ(G-e)≤λ(G).

引證1若G是p階簡單圖，由定理1知λ(G)≤δ(G)；

假設(shè)G是連通的非完全圖.設(shè)λ(G)是一個最小邊割，則恰好有兩個連通分支，記為G1和G2，并且G1與G2分別存在一個頂點(diǎn)u∈V(G1)和v∈V(G2)，使uv?E(G)，否則，p(G1)=p1，p(G2)=p2=p-p1，有

λ(G)=|E1|≥p1(p-p1)≥p-1

由定理1，知G?Kp，與假設(shè)矛盾.

現(xiàn)取G的一個點(diǎn)子集：V1={ui/ui是不同與u和v且與ei關(guān)聯(lián)的一個頂點(diǎn)，i=1,2,…,λ(G)}則|V1|≤|E1|=λ(G)，并且在G-V1中不存在(u-v)路，所以V1是G的一個頂點(diǎn).故κ(G)≤|V1|≤λ(G)

∴

κ(G)≤λ(G)≤δ(G)

(3)

嚴(yán)格成立.其中δ(G)是G的頂點(diǎn)的最小度.求解圖的連通度目前沒有有效的算法,主要采用最大流算法求解圖的邊連通度,而對于點(diǎn)連通度目前沒有很好的算法[20].但是，2004年，馬潤年等[21]基于質(zhì)粒技術(shù)的無向圖的最大權(quán)團(tuán)問題的DNA算法,依據(jù)Head T等的實(shí)驗(yàn)手段，解決了最大團(tuán)問題，方剛[22]用三維DNA圖結(jié)構(gòu)設(shè)計(jì)了一種生物算法求解圖的連通度，張社民[23,24]用類似的結(jié)構(gòu)設(shè)計(jì)了一種生物進(jìn)化算法.這給我們求解連通度提供了一個種新的思路.本文利用DNA納米金顆粒共聚體的自組裝過程解決連通度問題，構(gòu)建了解決圖的連通度問題的三維DNA自組裝計(jì)算模型.

2.2DNA納米顆粒共聚體算法

用DNA納米顆粒共聚體自組裝計(jì)算模型解決圖的連通度問題，根據(jù)具體的圖的頂點(diǎn)和邊設(shè)計(jì)所需的DNA納米金顆粒共聚體上DNA鏈的具體數(shù)目和堿基序列，以完成自組裝形成所需要的結(jié)構(gòu).

以一個具體的圖為例，如圖1所示，設(shè)G=(V，E)是無向圖，V為頂點(diǎn)集，E為邊集.其中第j條邊用ej=(ej1,ej2)表示.

第一步，構(gòu)造DNA納米金顆粒共聚體.首先設(shè)計(jì)連接不同數(shù)目的寡核苷酸鏈的納米晶體.DNA的末端通過巰基化的修飾可以連接到納米金顆粒上，然后通過置換反應(yīng)使金顆粒攜帶不同的DNA鏈.

經(jīng)過退火反應(yīng)，預(yù)先設(shè)計(jì)好的DNA納米金顆粒的晶體可以生成代表圖1的DNA納米金顆粒共聚體，如圖3所示.

第二步，刪去頂點(diǎn).刪除頂點(diǎn)用DNA鏈置換反應(yīng)技術(shù)來實(shí)現(xiàn).例如以頂點(diǎn)V3為例，我們要刪除已經(jīng)形成的代表圖G的三維納米結(jié)構(gòu)中的頂點(diǎn)V3，只要設(shè)計(jì)出能鏈置換與V3關(guān)聯(lián)的2條邊的DNA單鏈，這樣在實(shí)驗(yàn)室條件下，在含有圖G的三維納米結(jié)構(gòu)的溶液中加入取代鏈，經(jīng)過DNA鏈置換反應(yīng)，原來代表V3的DNA納米金顆粒共聚體就被置換了，V3頂點(diǎn)就被成功地刪除了.以此類推，圖G的8個頂點(diǎn)都需要設(shè)計(jì)與其關(guān)聯(lián)的邊的取代鏈，根據(jù)鏈置換反應(yīng)的條件，取代鏈與被取代鏈相比，應(yīng)當(dāng)含有相對較長的堿基互補(bǔ)序列，這是在設(shè)計(jì)和合成取代鏈時需考慮的問題.

在圖1所示的圖中要得到其連通度，刪除頂點(diǎn)組合的數(shù)目將是28-2=254.解空間是比較大的，為縮小解空間可以參見不等式(3)，據(jù)此不等式刪除的頂點(diǎn)將是不超過該圖最小度δ(G)的任意幾個頂點(diǎn)的組合而δ(G)=2,因此需刪除頂點(diǎn)組合的數(shù)目，即可行解的數(shù)目將會縮小至

(4)

這樣解空間可通過這一定理大大的縮小.刪除頂點(diǎn)后形成的2種納米結(jié)構(gòu)組合中含有正確解.

第三步，檢測正確的解.這一步通過瓊脂糖凝膠電泳技術(shù)進(jìn)行.不同的DNA納米金顆粒共聚體結(jié)構(gòu)在瓊脂糖凝膠電泳中呈現(xiàn)不同的形態(tài)，但仍然遵循電泳的一般規(guī)律，即顆粒的遷移率與其所帶電荷和顆粒大小有關(guān)[25,26]，代表頂點(diǎn)的DNA納米金顆粒共聚體根據(jù)其所連接的DNA單鏈的數(shù)目在電泳中可以區(qū)別，數(shù)目越多遷移率越?。淮韴DG的自組裝結(jié)構(gòu)由于含有最多的納米金顆粒遷移率最小.如圖4所示.利用DNA分子的特殊性質(zhì)，我們可以控制連接的納米顆粒的數(shù)目、大小、間距、空間維度和結(jié)構(gòu)的柔性.金納米顆粒具有大小和形狀的均一性，并且在溶液中也便于操控，因此較為普遍地被用于各種研究.

3　算法及仿真結(jié)果分析

當(dāng)刪除頂點(diǎn)后，Gi代表刪除i個頂點(diǎn)后的圖形，detect(Gi)，如果恰好能使圖Gi不連通，那么不連通的圖結(jié)構(gòu)在電泳中的分布可以通過對照區(qū)分出.如果連通，則令t=1；否則t=0.以本文圖G為例，刪除V5后得到兩種不再連通的圖結(jié)構(gòu)，含有1個納米金顆粒的自組裝結(jié)構(gòu)，在瓊脂糖中很容易辨認(rèn)出.

對于其它的圖的連通度問題，本文提出的生物化學(xué)算法也是可行的.本算法的通用計(jì)算如下所示：

1for i1 to δ(G)

2delete(G，i)

3t=detect(Gi)

4if(t)

5returnκ(G)=i

6else goto1

7end

本文以頂點(diǎn)V3為例，通過Visual DSD仿真來驗(yàn)證該實(shí)驗(yàn)的可行性.表1是該仿真過程用到的序列，其中3和5段的基因序列長度是6bp和4bp，其他基因段均為20bp.為了方便以圖5中所示的3種產(chǎn)物a，b，c表示.本文用NUPACK和Visual DSD對該實(shí)驗(yàn)仿真，該仿真實(shí)驗(yàn)?zāi)苷f明該實(shí)驗(yàn)的可行性.

在圖6是頂點(diǎn)V3被鏈a，c置換反應(yīng)過程.可以看出b鏈被a置換生成d和e，被c鏈置換生成f和g，同時e又可以被c置換，f可以被a置換,反應(yīng)過程如圖5所示，最后所有產(chǎn)物可能是d，e，f，h，g.

表1　實(shí)驗(yàn)仿真過程需要的DNA序列

名稱序列(5’-3’)名稱序列(5’-3’)1CCCAAAACAAAACAAAACAA5GCTA2CCCTTATCATATCAATACAAxCCCTATACTATACAATACTA3TATTCC7CCCTAATCTAATCATAACTA6CCCAAAACAAAACAAAACAAtCCCTAAACTTATCTAAACATyCCCTTAACTTAACAAATCTAaCCCTATTCAATTCAAATCAA

最后的反應(yīng)產(chǎn)物與a和c濃度有關(guān)，濃度不同，產(chǎn)物也會不同.本文通過調(diào)整a，c的濃度進(jìn)行對比分析.

本文通過對置換鏈a，c的濃度進(jìn)行調(diào)整利用Visual DSD仿真，做出了在高濃度圖7(a)，適中濃度圖7(b)，低濃度圖7(c)的3種情況的反應(yīng)過程實(shí)驗(yàn)圖，其中圖7(a)是置換鏈a,c的濃度在6500nM，被置換鏈?zhǔn)?000nM.圖7(b)是都在5000nM的情況，圖7(c)是置換鏈a,c的濃度在4500nM，被置換鏈?zhǔn)?000nM.通過對比圖7(a)，圖7 (b)我們可以看出圖7(a)參加反應(yīng)的收斂速度明顯要高于圖7(b) 圖6(c)，圖7(a)在500s的時候基本開始收斂，在1400s的時候已經(jīng)穩(wěn)定并且收斂后反應(yīng)也比較充分，雜質(zhì)比較少；而圖7(b)和圖7(c)都是在700s的時候才開始收斂，在2100s時才趨于穩(wěn)定并且收斂后反應(yīng)產(chǎn)物比較復(fù)雜，對于頂點(diǎn)V1來說相當(dāng)于刪掉的情況濃度比較小.在7(a)高濃度圖，圖7(b)適中濃度，圖7(c)低濃度這3種情況下最后的反應(yīng)產(chǎn)物如表2.

表2在高濃度(a)，適中濃度(b)，低濃度(c)3種情況下的濃度分析

類型abcdEfgh高濃度/nM15001500050000050005000中濃度/nM1581183155115484244824727低濃度/nM26556470449447444954025

本文最后利用退火反應(yīng)、鏈置換反應(yīng)、瓊脂糖凝膠電泳技術(shù)，通過這些生物化學(xué)技術(shù)對最后反應(yīng)產(chǎn)物進(jìn)行操作，然后再通過測序就可以驗(yàn)證圖1的連通度,具體操作過程:構(gòu)建DNA邏輯計(jì)算模型時，按照仿真的中圖7(a)的比例進(jìn)行實(shí)際實(shí)驗(yàn)操作.將混合液體置于常溫下進(jìn)行退火.此步驟后，可進(jìn)行瓊脂糖凝膠電泳進(jìn)行檢測.實(shí)驗(yàn)中，DNA鏈置換在緩沖液中實(shí)現(xiàn).加入的DNA鏈和運(yùn)算邏輯模塊混合后，在室溫下反應(yīng)6h以上，即可進(jìn)行PAGE電泳結(jié)果檢測.

4　討論

假設(shè)圖的頂點(diǎn)個數(shù)為n，邊的條數(shù)為m，那么本文提出了一種利用DNA納米金顆粒共聚體的自組裝過程解決連通度問題的DNA計(jì)算方法，構(gòu)建了解決圖的連通度問題的三維DNA自組裝計(jì)算模型的時間復(fù)雜度O(n+m).而1991年，kanevsky & Ramachandram提到當(dāng)頂點(diǎn)個數(shù)k=4的時間復(fù)雜度為O(n2)；1996年Henzinger & Rao提到當(dāng)頂點(diǎn)個數(shù)k=k時間復(fù)雜度為O(kmnlogn).本文的算法設(shè)計(jì)大大的縮小了時間復(fù)雜度.另外本文提出的生物化學(xué)算法分別使用了退火反應(yīng)、鏈置換反應(yīng)、瓊脂糖凝膠電泳技術(shù)，這些生物化學(xué)技術(shù)都便于操作；設(shè)計(jì)和合成DNA納米金顆粒共聚體的化學(xué)方法也是簡便易行的.該計(jì)算模型的優(yōu)勢還在于利用了DNA分子堿基序列的可編程性，以及納米顆粒的特殊化學(xué)結(jié)構(gòu)和性質(zhì)，與傳統(tǒng)DNA計(jì)算方法相比，不僅降低了實(shí)驗(yàn)的繁瑣程度，而且也克服了隨著問題規(guī)模的增加帶來的“指數(shù)爆炸問題”，降低了計(jì)算復(fù)雜度.基于DNA納米顆粒共聚體的特殊性質(zhì)，其它的檢測技術(shù)如透射電鏡技術(shù)，熒光技術(shù)也能很好地用于檢驗(yàn)本文提出的計(jì)算模型，這為下一步DNA自組裝計(jì)算模型的應(yīng)用提供了可行的方案.

本文提出的解決圖的連通度問題的三維DNA自組裝計(jì)算模型雖然是理論模型，但是通過Visual DSD的仿真驗(yàn)證了該實(shí)驗(yàn)的可行性并且通過調(diào)整置換鏈的濃度的對比分析，說明在實(shí)際實(shí)驗(yàn)中要將置換鏈過量這樣更能增加實(shí)驗(yàn)成功概率.盡管如此，在實(shí)際的操作和實(shí)驗(yàn)中，仍然無法避免非解的產(chǎn)生，許多無法預(yù)料的問題仍然是實(shí)驗(yàn)過程中無法控制的因素.在實(shí)驗(yàn)中不斷完善和檢驗(yàn)理論模型，在新的技術(shù)和方法中改進(jìn)理論模型和實(shí)驗(yàn)方法，這是建立通用的DNA計(jì)算模型的有效途徑.

[1]Adleman L.Molecular computation of solution to combinatorial problems[J].Science,1994,66:1021-1024.

[2]Lipton R J.Using DNA to solve NP-complete problems[J].Science,1995,268:542-545.

[3]Ouyang Q,Kaplan P D,Liu S,et al.DNA solution of the maximal clique problem[J].Science,1997,278:446-449.

[4]楊靜,張成,許進(jìn),等.基于環(huán)形DNA分子的一種求解最大集團(tuán)的計(jì)算模型[J].中國科學(xué),2010,40(8):1078-1085.

Yang Jing,Zhang Cheng,Xu Jin,et al.A novel computing model of the maximum clique problem based on circular DNA[J].SCIENCE CHINA Information Sciences,2010,40(8):1078-1085.(in Chinese)

[5]張成，馬麗娜，董亞非等.自組裝DNA鏈置換分子邏輯計(jì)算模型[J].科學(xué)通報，2012，31(57)：2909-2915.

Zhang Cheng,Ma Lina,Dong Yafei,et al.A computing model of self-assembly based on DNA strand displacement[J].Chinese Science Bulletin,2012,31(57):2909-2915.(in Chinese)

[6]Faulhammer D,Cukras A,Lipton R J,et al.Molecular computation:RNA solutions to chess problems[J].P Natl AcadSci,2000,97:1385-1389.

[7]Head T,Rozenberg G,Bladergroen R S,et al.Computing with DNA by operating on plasmids[J].BioSystems,2000,57:87-93.

[8]Mao CD,LaBean T H,Reif J H,et al.Logical computation using algorithmic self-assembly of DNA triple-crossover molecules[J].Nature,2000,407:493-496.

[9]Carbone A,Seeman N C.Circuits and programmable self-assembling DNA structures[J].P Natl Acad Sci,2002,99:12577-12582.

[10]Brun Y.Arithmetic computation in the tile assembly model:addition and multiplication[J].Theor Comput Sci,2007,378:17-31.

[11]Sharma J,Chhabra R,Cheng A,Brownell J,Liu Y,Yan H.Control of self-assembly of DNA tubules through integration of gold nanoparticles[J].Science,2009,313:112-116.

[12]Mastroianni AJ,Claridge SA,Alivisatos AP.Pyramidal and chiral groupings of gold nanocrystals assembled using DNA scaffolds[J].JAm Chem Soc 2009,131:8455-8459.

[13]楊玉星，王世英.Ménage問題的一種粘貼DNA算法[J].電子學(xué)報，2012，40(4):751-755.

Yang Yuxing,Wang Shiying.A DNA sticker algorithm for the ménage problem[J].Acta Electronica Sinica,2012,40(4):751-755.(in Chinese)

[14]吳帆,李肯立.基于自組裝的N皇后問題DNA計(jì)算算法[J].電子學(xué)報，2013，41(11)：2174-2180.

Wu Fan,Li Kenli.An algorithmin tile assembly model for N queen problem[J].Acta Electronica Sinica,2013,41(11):2174-2180.(in Chinese)

[15]Zhang C,Yang J,Xu J.Circular DNA logic gates with strand displacement[J].Langmuir,2010,26,1416-1419.

[16]Qian L L,Winfree E.Scaling up digital circuit computation with DNA strand displacement cascades[J].Science,2011,332(3):1196-1201.

[17]Cheng Z,Jing Y,Jin X.Molecular logic computing model based on self-assembly of DNA nanoparticles[J].Chinese Science Bulletin,2011,56(33):3566-3571.

[18]Jing Yang,Lingjing Shen,et al.Fluorescent nanoparticle beacon for logic gate operation regulated by strand displacement[J].ACS Appl Mater Interfaces,2013,5:5392-5396.

[19]Zhang C,Ma J J,Yang J,Dong Y F,Xu J.Control of gold nanoparticles based on circular DNA strand displacement[J].Journal of Colloid and Interface Science,2014,418:31-36.

[20]Bondy J A,Murty U S R.Graph Theory with Applications[M].London,The Macmillan Press L T D,1976,108-117.

[21]王樹禾.圖論[ M ].北京:科學(xué)出版社,2004:141-144.

Wang Shuhe.Graph Theory[M].Beijing:Sciences Press,2004:141-144.(in Chinese)

[22]馬潤年,張強(qiáng)，高琳,等.圖的最大權(quán)團(tuán)的DNA計(jì)算[J].電子學(xué)報，2004，32(1):13-16.

Ma Runnian,Zhangqiang,Gao Lin.et al.Using DNA to solve the maximum weight clique of graphs[J].Acta Electronica Sinica,2004,32(1):13-16.(in Chinese)

[23]方剛,張社民,許進(jìn).邊連通度問題的三維DNA圖結(jié)構(gòu)解法[J].系統(tǒng)工程與電子技術(shù)，2006，28(1):119-121.

Fang Gang,Zhang Shemin,Xu Jin.Three dimensional DNA graph structure solution to edge-connectivity[J].Systems Engineering and Electronics,2006,28(1):119-121.(in Chinese)

[24]張社民,方剛.連通度問題的三維DNA結(jié)構(gòu)進(jìn)化算法[J].計(jì)算機(jī)工程與應(yīng)用，2007，43(7):41-44.

Zhang Shemin,Fang Gang.Three dimensional DNA structure solution to connectivity based on evolutionary algorithm[J].Computer Engineering and Applications,2007,43(7):41-44.(in Chinese)

[25]Daniela Zanchet,Christine M Micheel,Wolfgang J Parak,Daniele Gerion,A Paul Alivisatos.Electrophoretic isolation of discrete Au nanocrystal/DNA conjugates[J].Nanoletters,2001,1(1):32-35.

[26]Daniela Z,Christine M,Wolfgang P,A Paul Alivisatos.Electrophoretic and structural studies of DNA-directed Au nanoparticle groupings[J].J Phys Chem B,2002,106:11758-11763.

王艷釵女,1989年10月出生，河南清豐人,2012年畢業(yè)于河南師范大學(xué)計(jì)算機(jī)與信息學(xué)院.2012年進(jìn)入陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院.從事DNA計(jì)算和基因網(wǎng)絡(luò)方面的有關(guān)研究.

E-mail:wangyanchai1025@163.com

董亞非男,1963年12月出生，陜西西安人,副教授、碩士生導(dǎo)師、中國系統(tǒng)工程學(xué)會會員、IEEE會員.華中科技大學(xué)工學(xué)博士，生物醫(yī)學(xué)博士后.現(xiàn)為陜西師范大學(xué)副教授，主要從事DNA計(jì)算、基因網(wǎng)絡(luò)及生物信息學(xué)等方面的研究工作.

E-mail:dongyf@snnu.edu.cn

The Application of DNA/ Nanoparticle Conjugate on the Graph’s Connectivity Problem

WANG Yan-chai1,ZHANG Hui2,DONG Ya-fei1,2

(1.College of Computer Sciences,Shaanxi Normal University,Xi′an,Shaanxi 710119,China; 2.College of Life Sciences,Shaanxi Normal University,Xi′an,Shaanxi 710119,China)

A DNA computing algorithm is proposed in this paper which uses the assembly process of DNA/Au nanoparticle conjugate to solve an NP-complete problem in the Graph theory,the connectivity problem,and a 3D DNA self-assembly algorithm model is also established.According to the algorithm,we need to design the special DNA/Au nanoparticle conjugate which will be based on a specific graph.Then,a series of experiments are performed to get the final answer and Visual DSD is used as the simulation in the paper,which will provide a practical way to the best use of DNA self-assembly algorithm model.

DNA computing;DNA/Au nanoparticle;graph’s connectivity;3D model

2013-12-26;

2014-10-24；責(zé)任編輯：郭游

國家自然科學(xué)基金(No.61272246);陜西師范大學(xué)2013年勤助科研創(chuàng)新基金(No.QZZD13005);陜西師范大學(xué)重點(diǎn)項(xiàng)目和陜西師范大學(xué)研究生培養(yǎng)創(chuàng)新基金

TN911

A

0372-2112 (2016)07-1561-06

??學(xué)報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.07.006