基于改進(jìn)的遺傳算法的DNA編碼序列設(shè)計(jì)

胡 娟 李 冬 張麗麗

（1.淮南職業(yè)技術(shù)學(xué)院 基礎(chǔ)部，安徽 淮南232001；2.淮南工業(yè)學(xué)校 電子組，安徽 淮南232001；3.安徽理工大學(xué) 理學(xué)院，安徽 淮南232001）

0 引言

DNA 首次用于計(jì)算是1994 年Adleman 用此解決了有向Hamilton 路問(wèn)題,從此DNA 計(jì)算模型以其高度并行性和海量存儲(chǔ)功能解決了大量NP 完全問(wèn)題， 也使人們對(duì)DNA 計(jì)算機(jī)產(chǎn)生了濃厚的興趣。 DNA 編碼序列設(shè)計(jì)問(wèn)題也是該領(lǐng)域研究的核心問(wèn)題之一，尋找到高質(zhì)量DNA 序列已成為DNA 編碼序列優(yōu)化設(shè)計(jì)一個(gè)熱點(diǎn)。

雖然DNA 計(jì)算在許多領(lǐng)域都取得了巨大進(jìn)展，但編碼，生物技術(shù)等問(wèn)題還需進(jìn)一步解決。 而且，目前還沒(méi)有一種通用的好方法來(lái)解決編碼問(wèn)題。目前制約DNA 編碼的約束條件有兩種：距離約束和熱力學(xué)約束。 距離約束有海明距離（HD），海明反距離（RH），海明反補(bǔ)距離（RC）等；熱力學(xué)約束有GC 含量，自由能ΔG，解鏈溫度Tm等。

在本文中， 我們主要選擇海明距離和反海明距離這兩個(gè)約束條件，首先用遺傳算法獲得大量的集合，滿(mǎn)足組合約束。 然后，使用改進(jìn)的遺傳算法來(lái)獲得大量的集合，以滿(mǎn)足組合約束。 最后將這個(gè)結(jié)果與遺傳算法比較，結(jié)果證明改進(jìn)的遺傳算法是優(yōu)于基本遺傳算法的。

1 約束條件

Garzon 首先提出了DNA 計(jì)算的編碼問(wèn)題的定義。即以DNA 分子的四個(gè)堿基為字母表∑={A，T，C，G},設(shè)一長(zhǎng)度為n 的DNA 分子的編碼集合為S，有|S|=4n，則對(duì)S 的子集C?S 有：

式中k∈Z+，τ 為評(píng)價(jià)準(zhǔn)則，顯然，編碼質(zhì)量和編碼數(shù)量?jī)烧呤窍嗷ッ艿摹?在滿(mǎn)足一定質(zhì)量的條件下，約條件束越多，就會(huì)減少DNA序列的編碼數(shù)目來(lái)滿(mǎn)足約束。

在本文中，我們使用海明距離，海明反距離和海明反補(bǔ)距離。 設(shè)DNA 序列的長(zhǎng)度為n，海明距離，海明反距離和海明反補(bǔ)距離為d。

1.1 海明距離約束

海明距離約束：兩個(gè)序列xi和xj之間的漢明距離大于或等于某參數(shù)d，即

式中f′Hamming（i）為第i 個(gè)進(jìn)化過(guò)程中對(duì)海明約束的評(píng)價(jià)。在這里，海明距離碼的最大值我們用AHD4 （n，d）來(lái)表示。

1.2 海明反距離約束

海明反距離約束： 兩個(gè)序列xi和之間的漢明距離大于或等于某參數(shù)d，即其中是xi的反序列。

1.3 優(yōu)化功能

我們使用平均權(quán)重處理功能來(lái)評(píng)價(jià)每個(gè)約束。

式中每個(gè)約束的權(quán)重為ωj，評(píng)價(jià)項(xiàng)的個(gè)數(shù)為m。

2 遺傳算法

2.1 基本遺傳算法

基本遺傳算法首先要隨機(jī)生成新的DNA 序列， 計(jì)算各個(gè)序列的適應(yīng)度函數(shù)值來(lái)滿(mǎn)足海明距離和海明反距離組合約束;然后利用遺傳算子生成滿(mǎn)足海明距離和海明反距離組合約束條件下的新的DNA 序列，從而獲得滿(mǎn)足條件的DNA 序列的集合。

具體步驟如下：

1）設(shè)置參數(shù)，并隨機(jī)生成初始群體。

2）計(jì)算各個(gè)適應(yīng)度函數(shù)值，從而滿(mǎn)足海明距離和海明反距離組合約束。

3）通過(guò)選擇、交叉和變異算子生成下一代個(gè)體。 如果下一代小于3000，轉(zhuǎn)到2，如果不是進(jìn)入4。

4）結(jié)束和輸出結(jié)果。

2.2 改進(jìn)的遺傳算法

為了獲得更多的滿(mǎn)足約束條件的DNA 序列的， 通過(guò)控制個(gè)體的適應(yīng)度函數(shù)值來(lái)進(jìn)行改進(jìn)。 如下：

（1）在計(jì)算個(gè)體的適應(yīng)度函數(shù)值上，使用動(dòng)態(tài)的方式進(jìn)化個(gè)體。

（2）在選擇階段，使用最省策略。

（3）在變異階段，調(diào)整變異與動(dòng)態(tài)方法操作的可能性。

主要過(guò)程如下：用DNA 序列生成動(dòng)態(tài)遺傳算法，通過(guò)控制進(jìn)化適應(yīng)度函數(shù)值來(lái)選擇序列，以生成滿(mǎn)足海明距離和海明反補(bǔ)距離約束條件下的序列，然后通過(guò)選擇、交叉和變異算子生成新的DNA 序列，獲得DNA 序列集。

3 仿真實(shí)驗(yàn)

改進(jìn)的遺傳算法使用的參數(shù)： 初始群體規(guī)模為40， 交叉概率為0.7，變異概率被為0.03，下一代是500。列表1 是在滿(mǎn)足海明距離和海明反距離約束條件下由遺傳算法獲得的DNA 的界限序集。 表2 是在滿(mǎn)足海明距離和海明反距離條件下由改進(jìn)的遺傳算法獲得的DNA 的界限序集。 對(duì)每個(gè)值我們都做了做5 次的試驗(yàn)。

從表1，表2 中可以發(fā)現(xiàn)，當(dāng)n 在不斷增加時(shí)，AR（n，d）的值也在增加。 可見(jiàn)計(jì)算的復(fù)雜性迅速增加。

表1 中，粗體的部分都大于或等于以前下界值，‘-’表示不存在的值。其它則是小于以前的下界值。表2 中，粗體的部分大于以前的下界值，‘！ ’表示大于或等于表1 中的值。

表1 基于GA 的（n，d）結(jié)果Table1 results of （n，d） by GA

表1 基于GA 的（n，d）結(jié)果Table1 results of （n，d） by GA

?

表2 基于改進(jìn)的GA 的（n，d）的結(jié)果Table2 results of （n，d） by Dynamic GA

表2 基于改進(jìn)的GA 的（n，d）的結(jié)果Table2 results of （n，d） by Dynamic GA

?

根據(jù)表1，與表2 比較，我們可以看到，改進(jìn)的遺傳算法比遺傳算法更好地地滿(mǎn)足了組合約束。

4 結(jié)論

在本文中，利用遺傳算法和改進(jìn)的遺傳算法來(lái)設(shè)計(jì)滿(mǎn)足海明距離和反海明距離約束條件的DNA 序列，通過(guò)兩種方法所得結(jié)果的比較，證明了改進(jìn)的遺傳算法是優(yōu)于遺傳算法的。 當(dāng)n 增加，若個(gè)體的數(shù)量增加，下代的數(shù)量也可能增加。同時(shí)計(jì)算復(fù)雜度和時(shí)間也在增加。必須看到，雖然對(duì)DNA 計(jì)算做了大量的研究，但其理論研究的深度和廣度都還有所欠缺，為此，還需要更深入研究DNA 編碼，從而設(shè)計(jì)出滿(mǎn)足組合約束的好的DNA 編碼序列。

［1］Holland J H.Adaptation in natural and artificial systems [M].AnnArbor：University of Michigan Press，1975.

［2］Deaton R，Murphy R C，Rose J A，et al.A DNA based implementationof an evolutionary search for good encodings for DNAcomputation [C]//Proceedings of IEEE Conference on EvolutionaryComputation，Indianapolis，IL.Los Alamitos，CA：IEEE Computer SocietyPress，1997：267-271.

［3］Wood DH，Chen J.Physical separation of DNA according to royalroad fitness[C]//Proceedings of IEEE Conference on EvolutionaryComputation.Washington，CA：IEEE Computer Society Press，1999：1016-1025.

［4］Feldkamp U，Raube H，Banzhaf W.Software tools for DNA sequence design[J].Genetic Programming and Evolvable Machines，2003，4（2）：153-171.

［5］Marathe A.On combinatorial DNA word design [J].DIMACS Series in Discrete Mathematics and Theoretical Computer Science，1999，44：75-88.

［6］張凱，肖建華.基于漢明距離的DNA 編碼約束研究[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（14）：24-26.

［7］Shin S Y,Lee I H，Kim Detal.Multiobjective evolut ionary optimization of DNA sequences for reliable DNA computing[J].IEEE Transactions on Evolutionary Comput ation，2005,9(2):143-158.

［8］Deaton R.and Garzon M.Thermodynamic Constraints on DNA -based Computing，in Computing with Bio-Molecues:Theory and Expirements.ed.G.Paun[M].Springer-Verlag:Singapore,1998：138-152.

［9］Deaton R.,Francescheti D.R.,GarzonM.,RoseJ.A.,MurphyR.C.,and Stevens S.E Information transfer through hybridyzation reaction in DNA based computing[J].Proceedings of the Second Annual Conference,1997,July 13 -16，Stanford University,.Morgan Kaufmann,San F rancisco：463-471.

［10］Deaton R.et al.A DNA Based Implementation of an Evolutionary Computation Proceedings IE EEC onference on Evolutionary Computation[J].In diana,1997：267-271.

［11］Marathe, A.; Condon, A. E.; Corn, R. M. On Combinatorial DNA word Design[J].DI MACS Ser ies in Discrete M athematics and Theoretical Computer Science,1999;Vol.44 ：75-87.

［12］RoseJ.A.,The Fidelity of DNA computation[D].The University of Memphis,1999,11.

［13］Xiao J H,Jin X,Chen Z H,et al.A hybrid quantum chaotic swarm evolutionary algorithm or DNA encoding[J].Computers& Mathematics with Applications,2009, 57(11/12):1949-1958.

［14］Marathe A,Condon A,Corn R.On combinatorial DNA word design[J].Journal of Computational Biology，2001，8(3)：201-220.