基于改進的遺傳算法的DNA編碼序列設計

胡娟　李冬　張麗麗

【摘 要】在DNA計算中，DNA編碼序列的設計是DNA計算的重要手段。在不同的DNA序列設計中，需要選擇適當的約束條件，給出滿足該約束條件的評估公式。本文選擇海明距離和反海明距離約束條件，利用遺傳算法和改進的遺傳算法來設計滿足這兩個條件的DNA編碼序列，通過結果的比較，證明了改進的遺傳算法優于遺傳算法。

【關鍵詞】DNA計算；DNA編碼；組合優化；遺傳算法

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首次用于計算是1994年Adleman用此解決了有向Hamilton路問題，從此DNA計算模型以其高度并行性和海量存儲功能解決了大量NP完全問題，也使人們對DNA計算機產生了濃厚的興趣。DNA編碼序列設計問題也是該領域研究的核心問題之一，尋找到高質量DNA序列已成為DNA編碼序列優化設計一個熱點。

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

在本文中，我們主要選擇海明距離和反海明距離這兩個約束條件，首先用遺傳算法獲得大量的集合，滿足組合約束。然后，使用改進的遺傳算法來獲得大量的集合，以滿足組合約束。最后將這個結果與遺傳算法比較，結果證明改進的遺傳算法是優于基本遺傳算法的。

1 約束條件

Garzon首先提出了DNA計算的編碼問題的定義。即以DNA分子的四個堿基為字母表■={A，T，C，G}，設一長度為n的DNA分子的編碼集合為S，有|S|=4n，則對S的子集C？哿S有：

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

式中k∈Z■，τ為評價準則，顯然，編碼質量和編碼數量兩者是相互矛盾的。在滿足一定質量的條件下，約條件束越多，就會減少DNA序列的編碼數目來滿足約束。

在本文中，我們使用海明距離，海明反距離和海明反補距離。設DNA序列的長度為n，海明距離，海明反距離和海明反補距離為d。

1.1 海明距離約束

海明距離約束：兩個序列x■和x■之間的漢明距離大于或等于某參數d，即Hx■，x■≥d：

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

式中f′■（i）為第i個進化過程中對海明約束的評價。在這里，海明距離碼的最大值我們用A■■（n，d）來表示。

1.2 海明反距離約束

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

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

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

1.3 優化功能

我們使用平均權重處理功能來評價每個約束。

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

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

式中每個約束的權重為ω■，評價項的個數為m。

2 遺傳算法

2.1 基本遺傳算法

基本遺傳算法首先要隨機生成新的DNA序列，計算各個序列的適應度函數值來滿足海明距離和海明反距離組合約束；然后利用遺傳算子生成滿足海明距離和海明反距離組合約束條件下的新的DNA序列，從而獲得滿足條件的DNA序列的集合。

具體步驟如下：

1）設置參數，并隨機生成初始群體。

2）計算各個適應度函數值，從而滿足海明距離和海明反距離組合約束。

3）通過選擇、交叉和變異算子生成下一代個體。如果下一代小于3000，轉到2，如果不是進入4。

4）結束和輸出結果。

2.2 改進的遺傳算法

為了獲得更多的滿足約束條件的DNA序列的，通過控制個體的適應度函數值來進行改進。如下：

（1）在計算個體的適應度函數值上，使用動態的方式進化個體。

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

（3）在變異階段，調整變異與動態方法操作的可能性。

主要過程如下：用DNA序列生成動態遺傳算法，通過控制進化適應度函數值來選擇序列，以生成滿足海明距離和海明反補距離約束條件下的序列，然后通過選擇、交叉和變異算子生成新的DNA序列，獲得DNA序列集。

3 仿真實驗

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

從表1，表2中可以發現，當n在不斷增加時，A■（n，d）的值也在增加。可見計算的復雜性迅速增加。

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

表1 基于GA的A■■（n，d）結果

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

表2 基于改進的GA的A■■（n，d）的結果

Table2 results of A■■（n，d） by Dynamic GA

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

4 結論

在本文中，利用遺傳算法和改進的遺傳算法來設計滿足海明距離和反海明距離約束條件的DNA序列，通過兩種方法所得結果的比較，證明了改進的遺傳算法是優于遺傳算法的。當n增加，若個體的數量增加，下代的數量也可能增加。同時計算復雜度和時間也在增加。必須看到，雖然對DNA計算做了大量的研究，但其理論研究的深度和廣度都還有所欠缺，為此，還需要更深入研究DNA編碼，從而設計出滿足組合約束的好的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].計算機工程與應用，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.

[責任編輯：薛俊歌]

[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.

[責任編輯：薛俊歌]

[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.

[責任編輯：薛俊歌]