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

胡娟　李冬　張麗麗

【摘 要】在DNA計(jì)算中，DNA編碼序列的設(shè)計(jì)是DNA計(jì)算的重要手段。在不同的DNA序列設(shè)計(jì)中，需要選擇適當(dāng)?shù)募s束條件，給出滿足該約束條件的評(píng)估公式。本文選擇海明距離和反海明距離約束條件，利用遺傳算法和改進(jìn)的遺傳算法來(lái)設(shè)計(jì)滿足這兩個(gè)條件的DNA編碼序列，通過(guò)結(jié)果的比較，證明了改進(jìn)的遺傳算法優(yōu)于遺傳算法。

【關(guān)鍵詞】DNA計(jì)算；DNA編碼；組合優(yōu)化；遺傳算法

The Design of DNA Code Sequence Based on Improved Genetic Algorithm

HU Juan1 LI Dong2 ZHANG Li -li3

（1.The Foundation department of Huainan Vocational Technical College，Huainan Anhui 232001，China；

2.The Electronics Set of Huainan Industrial School，Huainan Anhui 232001，China；

3.Dept. of Mathematics and Physics， Anhui Univ. of Science and Technology， Huainan Anhui 232001，China）

【Abstract】In the calculation of DNA， DNA sequence design is an important means for DNA computing. In the design of DNA sequences in different， need to choose the proper constraint conditions are satisfied， the evaluation formula of the constraint conditions. This paper chooses Hamming distance and Hamming distance constraint conditions， using genetic algorithm and improved genetic algorithm to design the DNA coding sequence satisfy these two conditions， by comparison the results， proved that genetic algorithm is better than the improved genetic algorithm

【Key words】DNA computing；DNA encoding；Combinational optimization；Genetic algorithm

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)一步解決。而且，目前還沒有一種通用的好方法來(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有：

？坌x■，x■∈C τ（x■，j■）≥k（1）

式中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è)序列x■和x■之間的漢明距離大于或等于某參數(shù)d，即Hx■，x■≥d：

f′■（i）=■{Hx■，j■}（2）

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

1.2 海明反距離約束

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

f′■（i）=■{Hx■，x■■}（3）

在這里海明反距離碼的最大值我們用A■■（n，d）來(lái)表示。

1.3 優(yōu)化功能

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

f■∈f■[i]，f■[i]

f（i）=■ω■f■[i]（4）

式中每個(gè)約束的權(quán)重為ω■，評(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í)，A■（n，d）的值也在增加?？梢娪?jì)算的復(fù)雜性迅速增加。

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

表1 基于GA的A■■（n，d）結(jié)果

Table1 results of A■■（n，d） by GA

表2 基于改進(jìn)的GA的A■■（n，d）的結(jié)果

Table2 results of A■■（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編碼序列。

【參考文獻(xiàn)】

[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.，F(xiàn)rancescheti 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.

[責(zé)任編輯：薛俊歌]

[9]Deaton R.，F(xiàn)rancescheti 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.

[責(zé)任編輯：薛俊歌]

[9]Deaton R.，F(xiàn)rancescheti 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.

[責(zé)任編輯：薛俊歌]