胡娟 李冬 張麗麗

摘要：針對DNA計算中的編碼序列設計問題，分析DNA編碼序列設計的目標和需要滿足的約束條件，從中選擇適當?shù)募s束條件，給出評估公式，提出人工魚群遺傳算法生成有效的DNA編碼序列。經(jīng)實驗結果表明，所述算法比遺傳算法及遺傳粒子群算法產(chǎn)生的DNA編碼序列質量更加穩(wěn)定可靠。

關鍵詞：DNA計算；DNA編碼；組合優(yōu)化；人工魚群遺傳算法

中圖分類號：TP3015 文獻標志碼：A

文章編號：1672-1098（2014）01-0056-05

1994年，當文獻[1]用DNA計算成功地解決了有向Hamilton路問題，人類已經(jīng)進入了借助DNA分子通過生化反應來進行計算的嶄新時代。從此越來越多的學者用DNA計算模型解決了許多NP完全問題，然而早期DNA計算中所用的序列都需要在設定編碼長度的基礎上隨機產(chǎn)生，這就會導致生物化學反應不可控制性。因此尋找高質量DNA序列及合適的DNA序列庫變得尤為重要。通常為了滿足DNA序列可靠性的要求，就會利用約束條件來篩選序列，決定序列編碼的約束條件主要有Gibb自由能增量約束、解鏈溫度約束Tm、H-measure約束、生物酶和DNA分子的生物特異性等，要想找到好的編碼就需要充分考慮這些約束條件。

遺傳算法（Genetic Algorithm，GA）是20世紀70年代初文獻[2]16首先提出來的。它常用來處理很復雜的非線性問題，具有非常好的魯棒性。但它最大的缺點就是進化過程盲目性，常會陷入局部極值。尤其在編碼問題中，當約束條件較多時，它有可能會搜索不到符合要求的編碼。而全局人工魚群算法是模仿魚群覓食的一種算法，算法簡單，又有避免陷入局部極值的良好能力。

本文在深入研究傳統(tǒng)遺傳算法的基礎上，為了克服其盲目搜索的缺點，提高進化效率，給出了一種基于遺傳算法和全局人工魚群算法的混合優(yōu)化算法（GAFSA/GA），用于DNA的編碼問題，經(jīng)實驗結果表明，所述算法比遺傳算法產(chǎn)生的DNA編碼序列質量更加穩(wěn)定可靠。

1DNA編碼序列設計及約束項分析

11DNA編碼問題

DNA計算中的編碼問題一般都描述為：設由四個字母組成的集合∑={A，T，C，G}，若DNA分子長度為n，其編碼集合為S，很明顯有|S|=4n，求CS使xi，xj∈C ，τ（xi，xj）≥k，其中τ為評價標準，k∈Z+。然而τ越嚴格，可供選擇的編碼數(shù)|C|就會越小。編碼問題，主要是編碼質量和數(shù)量問題。因為編碼質量越高，可靠性就會越好；而編碼數(shù)量越大，就會擴大應用范圍。然而，在現(xiàn)實中，他們是相互矛盾的。這就希望在保證質量的前提下能最大限度的得到編碼集合。

12約束項及評價函數(shù)

影響DNA計算的因素[3-7]有很多，結合眾多約束條件，給出本文的DNA編碼的約束條件。

1） H-measure約束。H-measure是一種通過移位比較兩個DNA序列漢明距離的最小值而獲得的有效約束，移位后的互補堿基對的數(shù)目可以有效防止雜交，定義公式如下：

2人工魚群遺傳算法

21基本遺傳算法

遺傳算法是模擬生物進化過程中適者生存規(guī)則，并將其與種群內(nèi)部染色體的隨機信息進行交換，是一種很好的局部優(yōu)化搜索方法[2]141。它的主要思想是：隨機生成DNA序列；計算DNA序列的適應度函數(shù)值，滿足約束條件；利用遺傳算子生成滿足約束條件的新的DNA序列，從而獲得 DNA序列的集合（見圖1）。

圖1算法流程圖

22人工魚群算法（GAFSA）

人工魚群算法就是模擬魚群的覓食，聚首及追尾行為而生成的全局優(yōu)化算法。通過觀察魚覓食會發(fā)現(xiàn)在一片水域中，魚最多的地方就是食物最多的地方，魚有自行或尾隨其他魚找到食物最多的地方特點。人工魚群算法就是根據(jù)魚群的這一特點，來構造人工魚群來模仿魚群行為，從而實現(xiàn)尋優(yōu)。

1） 確定魚群規(guī)模N，隨機產(chǎn)生N 個人工魚個體，組成初始群體，同時設置相關參數(shù)；

2） 計算初始魚群的個體適應函數(shù)值，并將最優(yōu)人工魚狀態(tài)記錄到公告板；

3） 個體通過覓食行為，聚首行為，追尾行為[8]生成新的魚群；

4） 選最優(yōu)個體與公告板進行比較，若比公告板優(yōu)，則以自身狀態(tài)更新公告板；

5） 根據(jù)文獻[8]對視野和步長進行調(diào)整；

6） 判斷是否滿足終止條件，若滿足，則輸出公告板記錄，算法終止；若不滿足，則執(zhí)行步驟3。

23人工魚群遺傳算法（GAFSA/GA）

該算法是以基本遺傳算法為基礎，將人工魚群算法作為遺傳算法的一個重要算子，具體步驟如下：

1） 設定相關參數(shù)，并產(chǎn)生初始種群；

2） 計算個體的適應度函數(shù)值，按照適應度函數(shù)值進行排序；

3） 判斷是否滿足目標，若滿足，輸出結果，結束進程； 否則進行下一步；

4） 更新個體種群，根據(jù)適應度函數(shù)值的確定一部分個體直接進入下一代種群，剩余個體通過GAFSA算法優(yōu)化過后進入下一代種群；

5） 對下代種群執(zhí)行遺傳算法的復制、交叉和變異等操作，轉步驟2。

流程圖如圖2所示。

圖2算法流程圖

3算法仿真結果及分析

31與遺傳算法的實驗比較

用全局人工魚群遺傳算法產(chǎn)生的DNA序列與文獻[9]的遺傳算法的編碼序列進行了比較，并給出了好的有向哈密爾頓路問題的DNA 序列。比較結果如表1和圖3所示。

從圖3可以看出，GAFSA/GA 算法生成的DNA編碼序列在Hairpin、GC含量方面比GA 算法生成的DNA編碼序列更優(yōu)，并且可以看出GAFSA/GA生成的序列解鏈溫度變化更小，這意味著GAFSA/GA算法具有較低的不完全匹配雙鏈產(chǎn)生的概率。同時GAFSA/GA算法大大降低了計算的難度，在解決DNA編碼問題方面效果很好，而且依靠群體人工魚并行計算，其收斂速度較快，如（見圖4）橫軸為進化代數(shù)；豎軸為每代群體經(jīng)排序后最差個體的適應度值。從圖4中可以看出，算法具有較好的收斂性。

進化代數(shù)

圖4GAFSA/GA算法的進化收斂圖

32與遺傳粒子群算法的實驗比較

雖然文獻[10]遺傳粒子群算法（GA/PSO）與GAFSA/GA選擇的約束條件不同，但鑒于實驗結果的比對應建立在相同約束條件的基礎上進行，采用GAFSA/GA的評價方法進行實驗比對。比較結果如表2和圖5所示。

從表2和圖5可以看出，GAFSA/GA算法生成的DNA編碼序列在解鏈溫度、發(fā)夾結構等約束方面優(yōu)于遺傳粒子群算法生成的DNA編碼序列。

4結論

從DNA 編碼的多個約束條件選取合適的約束，提出了GAFSA/GA 算法對DNA 計算中的編碼序列實現(xiàn)了優(yōu)化，產(chǎn)生了很好的DNA 序列，驗證了該算法的可行性和有效性。

參考文獻：

[1]ADLEMAN L M.Molecular computation of solution to combinatorial problems[J]. Science， 1994， 66（11）： 1 021-1 024.

[2]HOLLAND J H.Adaptation in natural and artificial systems [M].AnnArbor：University of Michigan Press，1975：1-153.

[3]DEATON R，GARZON M.The Rmodynamic Constraints on DNA-based Computing[C]// Computing with Bio Molecues：Theory and Expirements.ed.G.Paun，Springer-Verlag：Singapore，1998：138-152.

[4]DEATON R，F(xiàn)RANCESCHETI D R，GARZON M，et al. Information transfer through hybridyzation reaction in DNA based computing[C]//Proceedings of the Second Annual Conference，1997，July 13-16，Stanford University，.Morgan Kaufmann，San Francisco：463-471.

[5]DEATON R. A DNA Based Implementation of an Evolutionary Computation[C]// Proceedings IEEE Conference on Evolutionary Computation. Indianapolis，1997：267-271.

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

[7]ROSE J A. The Fidelity of DNA computation[D].Ph.D thesis，The University of Memphis，1999：11.

[8]付媛媛，張大方，向旭宇.基于人工魚群的DNA編碼序列組合優(yōu)化算法研究[J].湖南城市學院學報：自然科學版，2011，20（2）：55-56.

[9]ARITA M，NISHIKAWA A，HAGIVA M，et al. Improving sequencedesign for DNA computing[C]// In Proceedings of the Genetic andEvolutionary Computation Conference（GECCO-2000），2000：875-882.

[10]CUI G Z，NIU Y Y，WANG Y F，et al. A new approach based onPSO algorithm to findgood computational encoding sequences[J].Progress in Natural Science，2007，17（6）：712-716.

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

[12]張凱，肖建華.基于漢明距離的DNA編碼約束研究[J].計算機工程與應用，2008，44（14）：24-26.

[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）： 1 949-1 958.

[14]CUI GUANGZHAO，LI XIAO GUANG，ZHANG XUN CAI，et al. The Optimization of DNA Encodings Based on Modif ied PSO/GA Algorithm[J].CHINESE JOU RNAL OF OMPUT ERSVol， 2010，33（2）：312-313.

（責任編輯：何學華，吳曉紅）

進化代數(shù)

圖4GAFSA/GA算法的進化收斂圖

32與遺傳粒子群算法的實驗比較

雖然文獻[10]遺傳粒子群算法（GA/PSO）與GAFSA/GA選擇的約束條件不同，但鑒于實驗結果的比對應建立在相同約束條件的基礎上進行，采用GAFSA/GA的評價方法進行實驗比對。比較結果如表2和圖5所示。

從表2和圖5可以看出，GAFSA/GA算法生成的DNA編碼序列在解鏈溫度、發(fā)夾結構等約束方面優(yōu)于遺傳粒子群算法生成的DNA編碼序列。

4結論

從DNA 編碼的多個約束條件選取合適的約束，提出了GAFSA/GA 算法對DNA 計算中的編碼序列實現(xiàn)了優(yōu)化，產(chǎn)生了很好的DNA 序列，驗證了該算法的可行性和有效性。

參考文獻：

[1]ADLEMAN L M.Molecular computation of solution to combinatorial problems[J]. Science， 1994， 66（11）： 1 021-1 024.

[2]HOLLAND J H.Adaptation in natural and artificial systems [M].AnnArbor：University of Michigan Press，1975：1-153.

[3]DEATON R，GARZON M.The Rmodynamic Constraints on DNA-based Computing[C]// Computing with Bio Molecues：Theory and Expirements.ed.G.Paun，Springer-Verlag：Singapore，1998：138-152.

[4]DEATON R，F(xiàn)RANCESCHETI D R，GARZON M，et al. Information transfer through hybridyzation reaction in DNA based computing[C]//Proceedings of the Second Annual Conference，1997，July 13-16，Stanford University，.Morgan Kaufmann，San Francisco：463-471.

[5]DEATON R. A DNA Based Implementation of an Evolutionary Computation[C]// Proceedings IEEE Conference on Evolutionary Computation. Indianapolis，1997：267-271.

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

[7]ROSE J A. The Fidelity of DNA computation[D].Ph.D thesis，The University of Memphis，1999：11.

[8]付媛媛，張大方，向旭宇.基于人工魚群的DNA編碼序列組合優(yōu)化算法研究[J].湖南城市學院學報：自然科學版，2011，20（2）：55-56.

[9]ARITA M，NISHIKAWA A，HAGIVA M，et al. Improving sequencedesign for DNA computing[C]// In Proceedings of the Genetic andEvolutionary Computation Conference（GECCO-2000），2000：875-882.

[10]CUI G Z，NIU Y Y，WANG Y F，et al. A new approach based onPSO algorithm to findgood computational encoding sequences[J].Progress in Natural Science，2007，17（6）：712-716.

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

[12]張凱，肖建華.基于漢明距離的DNA編碼約束研究[J].計算機工程與應用，2008，44（14）：24-26.

[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）： 1 949-1 958.

[14]CUI GUANGZHAO，LI XIAO GUANG，ZHANG XUN CAI，et al. The Optimization of DNA Encodings Based on Modif ied PSO/GA Algorithm[J].CHINESE JOU RNAL OF OMPUT ERSVol， 2010，33（2）：312-313.

（責任編輯：何學華，吳曉紅）

進化代數(shù)

圖4GAFSA/GA算法的進化收斂圖

32與遺傳粒子群算法的實驗比較

雖然文獻[10]遺傳粒子群算法（GA/PSO）與GAFSA/GA選擇的約束條件不同，但鑒于實驗結果的比對應建立在相同約束條件的基礎上進行，采用GAFSA/GA的評價方法進行實驗比對。比較結果如表2和圖5所示。

從表2和圖5可以看出，GAFSA/GA算法生成的DNA編碼序列在解鏈溫度、發(fā)夾結構等約束方面優(yōu)于遺傳粒子群算法生成的DNA編碼序列。

4結論

從DNA 編碼的多個約束條件選取合適的約束，提出了GAFSA/GA 算法對DNA 計算中的編碼序列實現(xiàn)了優(yōu)化，產(chǎn)生了很好的DNA 序列，驗證了該算法的可行性和有效性。

參考文獻：

[1]ADLEMAN L M.Molecular computation of solution to combinatorial problems[J]. Science， 1994， 66（11）： 1 021-1 024.

[2]HOLLAND J H.Adaptation in natural and artificial systems [M].AnnArbor：University of Michigan Press，1975：1-153.

[3]DEATON R，GARZON M.The Rmodynamic Constraints on DNA-based Computing[C]// Computing with Bio Molecues：Theory and Expirements.ed.G.Paun，Springer-Verlag：Singapore，1998：138-152.

[4]DEATON R，F(xiàn)RANCESCHETI D R，GARZON M，et al. Information transfer through hybridyzation reaction in DNA based computing[C]//Proceedings of the Second Annual Conference，1997，July 13-16，Stanford University，.Morgan Kaufmann，San Francisco：463-471.

[5]DEATON R. A DNA Based Implementation of an Evolutionary Computation[C]// Proceedings IEEE Conference on Evolutionary Computation. Indianapolis，1997：267-271.

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

[7]ROSE J A. The Fidelity of DNA computation[D].Ph.D thesis，The University of Memphis，1999：11.

[8]付媛媛，張大方，向旭宇.基于人工魚群的DNA編碼序列組合優(yōu)化算法研究[J].湖南城市學院學報：自然科學版，2011，20（2）：55-56.

[9]ARITA M，NISHIKAWA A，HAGIVA M，et al. Improving sequencedesign for DNA computing[C]// In Proceedings of the Genetic andEvolutionary Computation Conference（GECCO-2000），2000：875-882.

[10]CUI G Z，NIU Y Y，WANG Y F，et al. A new approach based onPSO algorithm to findgood computational encoding sequences[J].Progress in Natural Science，2007，17（6）：712-716.

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

[12]張凱，肖建華.基于漢明距離的DNA編碼約束研究[J].計算機工程與應用，2008，44（14）：24-26.

[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）： 1 949-1 958.

[14]CUI GUANGZHAO，LI XIAO GUANG，ZHANG XUN CAI，et al. The Optimization of DNA Encodings Based on Modif ied PSO/GA Algorithm[J].CHINESE JOU RNAL OF OMPUT ERSVol， 2010，33（2）：312-313.

（責任編輯：何學華，吳曉紅）