基于改進(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è)約束條件，首先用遺傳算法獲得大量的集合，滿足組合約束。 然后，使用改進(jìn)的遺傳算法來(lái)獲得大量的集合，以滿足組合約束。 最后將這個(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ī)烧呤窍嗷ッ艿摹?在滿足一定質(zhì)量的條件下，約條件束越多，就會(huì)減少DNA序列的編碼數(shù)目來(lái)滿足約束。

在本文中，我們使用海明距離，海明反距離和海明反補(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)滿足海明距離和海明反距離組合約束;然后利用遺傳算子生成滿足海明距離和海明反距離組合約束條件下的新的DNA 序列，從而獲得滿足條件的DNA 序列的集合。

具體步驟如下：

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

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

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

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

2.2 改進(jì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)選擇序列，以生成滿足海明距離和海明反補(bǔ)距離約束條件下的序列，然后通過(guò)選擇、交叉和變異算子生成新的DNA 序列，獲得DNA 序列集。

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

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

從表1，表2 中可以發(fā)現(xiàn)，當(dāng)n 在不斷增加時(shí)，AR（n，d）的值也在增加。 可見計(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)的遺傳算法比遺傳算法更好地地滿足了組合約束。

4 結(jié)論

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