MO_DE：一種結(jié)合多目標優(yōu)化機制的DNA編碼序列算法

岑巍

(上海浦東發(fā)展銀行, 上海200042)

?

MO_DE：一種結(jié)合多目標優(yōu)化機制的DNA編碼序列算法

岑巍

(上海浦東發(fā)展銀行, 上海200042)

針對現(xiàn)有DNA計算中存在的編碼序列設(shè)計穩(wěn)定性不足、可靠性不完善等問題，充分考慮基本編碼問題，設(shè)計出一種基于多目標優(yōu)化機制的DNA編碼序列設(shè)計算法(MO_DE：multiobjective design algorithm)。在一定的約束條件下，該算法利用了多目標優(yōu)化機制以及采取小種蟻群算法，將h-distance因子添加到單鏈DNA架構(gòu)中，建立一種DNA序列公用方法。通過模擬實驗表明，該算法與同類型算法相比，在計算效率、優(yōu)化性方面具有一定優(yōu)勢。

DNA計算;多目標優(yōu)化;小種蟻群;編碼序列;MO_DE

引言

近年來，智能化生物計算機作為一個新型的熱點研究領(lǐng)域，得到了長足發(fā)展與廣泛關(guān)注。DNA計算則是其中重要一環(huán)。DNA計算是以DNA鏈條作為操作處理手段，使用DNA鏈中多行反應(yīng)計算能力的一種智能化生物計算方式，現(xiàn)已成功解決了眾多世界性難題，如Hamilton路徑、NP完全難題等[1]。

在DNA計算中，DNA編碼序列算法是影響DNA計算的核心與關(guān)鍵問題。Cui G Z等[2]提出，如何加強DNA編碼序列的特異性設(shè)計與計算區(qū)別功能是DNA編碼序列問題的關(guān)鍵研究方向。在進行DNA編碼序列設(shè)計之前，首先需要關(guān)聯(lián)DNA組合限制約束條件、熱力學問題(如：漢明距離限制、二級結(jié)構(gòu)限制、連續(xù)性限制、解鏈溫度限制、GC含量限制等)，所以，張強等[3]基于上述相關(guān)約束條件，提出了一種DNA模板編碼方法。Zhang X等[4]在文獻[3]的基礎(chǔ)之上，提出了一種基于DNA編碼序列的編譯算法。Shin S Y等[5]基于遺傳算法設(shè)計了一種新型的DNA序列類型；Wang W等[6]將DNA編碼序列問題成功轉(zhuǎn)化成一個附有約束限制的多目標優(yōu)化問題。殷脂等[7]分析了DNA編碼序列對DNA計算的穩(wěn)定性和可靠性的影響，文中指出，DNA編碼的多約束條件是影響DNA計算穩(wěn)定性和可靠性的主要因素。目前，DNA編碼序列設(shè)計問題解決手段一般包括隨機查詢、種族進化、模板編碼以及多目標優(yōu)化等。因此，如何找到一種標準條件下的DNA編碼序列問題求解方法，成為首要解決的目標。

針對上述描述，本文充分考慮到DNA基本編碼問題[8]，結(jié)合多目標優(yōu)化機制，設(shè)計出一種新型的DNA編碼序列設(shè)計算法，即MO_DE算法(MO_DE：multiobjective design algorithm)。在一定的約束條件下，并采取小種蟻群算法，將h-distance因子添加到單鏈DNA架構(gòu)中，構(gòu)造一種DNA序列公用方法。通過與相關(guān)文獻作比較分析，說明了該算法在計算效率、優(yōu)化性等方面具有一定優(yōu)勢。

1 約束限制與優(yōu)化結(jié)構(gòu)

1.1 約束限制

具體包括以下幾種約束條件與限制因素，即：

(1) 相似性

相似性主要應(yīng)用于調(diào)整DNA編碼序列設(shè)計中的移位相似度，對于DNA單序列鏈條Dj與Dk，由于存在相關(guān)關(guān)聯(lián)公式：

H(Dj,σl(Dk))=

(1)

(2)

由此可知：

(3)

依據(jù)DNA編碼序列的無限制運動與全面擴展[9]，利用以下最小相似性作為目標方法：

(4)

(2) 移動測度

移動測度主要是使用于標記DNA編碼序列中各個移位運動概率值，設(shè)定：

(5)

(6)

(3)h-距離

h-距離(漢明)說明了DNA編碼序列在相似性以及移動測度相關(guān)特征，表達了DNA編碼序列中公用分享度。

(7)

(4)GC含量

GC含量是堿基G和C量之間在DNA編碼序列中的存在占有比重。設(shè)定GC(Dj)是DNA編碼序列Dj的GC含量，GCgoal表示目標參數(shù)，kGC表示GC含量能夠接受上下限區(qū)域，可知GC含量的約束限制：

(8)

(5)Tm溫度

在DNA編碼設(shè)計過程中，一半左右的DNA鏈條所需的溫度參數(shù)值。設(shè)定Tm(Dj)是DNA編碼序列Dj的Tm溫度參數(shù)值，Tm goal表示目標參數(shù)，kTm表示Tm溫度能夠接受上下限區(qū)域，可知Tm溫度約束限制：

(9)

(6)HP環(huán)形模型

HP環(huán)形模型是DNA編碼序列中雜交而成，設(shè)定：

(10)

其中，Haripin(p,r,s,Dj)說明DNA編碼序列Dj中起始于點p、DNA環(huán)形周長是r、DNA環(huán)形桿長是s的發(fā)卡參數(shù)。設(shè)定kHP表示HP能夠接受上下限區(qū)域，可知HP約束限制：

fHP(Dj)≤kHP

(11)

(7)Con函數(shù)因子

基于DNA編碼序列中Con函數(shù)知識，設(shè)定：

(12)

fCon(Dj,N)≤kCon

(13)

1.2 優(yōu)化結(jié)構(gòu)

依據(jù)上述提供的多種目標方法與約束條件的局限限制，DNA編碼序列設(shè)計思路能夠構(gòu)成一種標準的優(yōu)化結(jié)構(gòu)，即：

maxF(Dj)=[fH(Dj),fHR(Dj)]

s.t.fGC(Dj)≤kGCfTm(Dj)≤kTmfHP(Dj)≤kHPfCon(Dj,N)≤kCon

(14)

2 MO_DE算法

按照上面DNA編碼序列設(shè)計過程中的約束限制與優(yōu)化結(jié)構(gòu)，設(shè)計出一種結(jié)合多目標優(yōu)化機制的小種蟻群算法，將其應(yīng)用與DNA編碼序列中，從而產(chǎn)生出MO_DE算法。

針對DNA編碼序列Dj以及Dk，可知共同分享方法設(shè)置：

(15)

基于DNA編碼序列種群四進制整數(shù)矩陣Pm×n，添加一些算子元素：

(2)RX，即隨機交叉處理。通過概率參數(shù)PRXO，對四進制整數(shù)矩陣Pm×n的行參數(shù)進行隨機選擇并配對，其次隨機進行交叉位置選取，進行隨機交叉操作。

(3)RM，即逆向密碼因子變異操作。設(shè)定r表示密碼因子長度參數(shù)，通過概率參數(shù)PRMO，對四進制整數(shù)矩陣Pm×n的r層子表達式進行隨機選取，然后按行向量獲取逆向序列。

(4)RCM(RM的補集操作)，即逆向補密碼因子變異操作。設(shè)定r表示密碼因子長度參數(shù)，通過概率參數(shù)PRCMO，對四進制整數(shù)矩陣Pm×n的r層子表達式進行隨機選取，然后按行向量獲取逆向補集序列。

(5)M，即變異操作。通過概率參數(shù)PMO，對四進制整數(shù)矩陣Pm×n的L層子表達式進行隨機選取，將其堿基因子對應(yīng)的整數(shù)參數(shù)隨機代替上限整數(shù)參數(shù)。

(6)S，即選擇操作。采取競賽選取機制，大小為2。

(7) 終止操作。持續(xù)進化時間長度超過幾百年且達到歷史最優(yōu)化解時終止，不刷新操作。

通過上述算子元素，其MO_DE算法的具體流程如圖1所示。

圖1 MO_DE算法流程圖

具體算法如下：

P0，i=0；//第一步；

C<= BestSave(P0，m’)；//第二步

while 不符合終止操作 do//第三步

Pi<=S(Pi)，

Pi0<=SX(Pi),

Pi1<=RX(Pi0),

Pi2<=RM(Pi0),

Pi3<=RCM(Pi0),

Pi4<=M(Pi0);

Pi’<=Union(Pi1,Pi2,Pi3,Pi4,C);

C’ <= BestSave(Pi’，m’);

If MeanFitness(C’) > MeanFitness(C)

C<=C’;//第四步

Pi+1 <= BestSave(Pi’，m);//第五步

end while//第六步

在MO_DE算法流程中會出現(xiàn)對應(yīng)的種群分散與擴展現(xiàn)象，其大小分散與擴展的上限大致是初始化狀態(tài)的5倍至7倍左右。

3 模擬實驗與結(jié)果分析

針對相關(guān)約束限制與優(yōu)化模型，在Matlab 7.0的平臺環(huán)境下，對設(shè)計的MO_DE算法進行模擬實驗，操作環(huán)境為：Pentium Dual E2104，2.5 GHz，512 MB，Windows2008。設(shè)置參數(shù)因子：(1)DNA編碼序列發(fā)卡數(shù)值是0；(2)GC含量是50%；(3)對應(yīng)于MO_DE算法的各個參數(shù)(n，m’，m，i，r，GCgoal，Tmgoal，ɑ1,ɑ2,ɑ3,ɑ4,ɑ5,ɑ6,σ,ɑ,PSXO,PRXO,PRMO,PRCMO,PMO)分別是：(40，6，20，400，3，40，47，1，1，1，1，1，1，8，1，0.8，0.2，0.2，0.2，0.4)，以七個DNA編碼序列為示例，實驗結(jié)果見表1。

依據(jù)DNA編碼序列的無限制運動與全面擴展，對模擬實驗的數(shù)據(jù)信息進行評估處理，特定在DNA編碼序列中選取兩個目標方法參數(shù)的最小數(shù)(min(MS),min(MH))；選取GC含量與Tm溫度的相對標準差參數(shù)，即(σGC,σTm)，從而使得DNA編碼序列的理化性質(zhì)保持相對統(tǒng)一；選取SCon保證DNA編碼序列的一定連續(xù)性。以七個DNA編碼序列為示例，評估結(jié)果見表2。

表1 MO_DE與同類型算法之間的DNA編碼序列結(jié)果對比表

表2 DNA編碼序列結(jié)果評估項對比表

從表1與表2中可知，在各個評估項中，MO_DE算法具有最優(yōu)化結(jié)果，特別是在DNA編碼序列的連續(xù)性上具有很大改進，同時Tm溫度以及GC含量都足夠統(tǒng)一集中，表示DNA編碼序列的理化性質(zhì)保持了相對統(tǒng)一，比同類型的兩種算法都有明顯的優(yōu)勢。除此之外，在種群分散膨脹方面，MO_DE算法均比同類型兩種算法更加完善，其迭代次數(shù)最少，計算操作量也最優(yōu)。

在適應(yīng)度函數(shù)方面，MO_DE算法同樣進行了改進設(shè)計，MO_DE算法的進化收斂過程如圖2所示。表明MO_DE算法在適應(yīng)度函數(shù)方面具有很好的收斂性。

圖2 MO_DE算法的進化收斂圖

4 結(jié)束語

針對現(xiàn)有DNA計算中存在的編碼序列設(shè)計穩(wěn)定性、可靠性不完善等問題，從多層面分析，DNA編碼序列設(shè)計問題是一種多目標函數(shù)的優(yōu)化問題。因此，本文充分考慮基本編碼問題，結(jié)合多目標優(yōu)化機制，設(shè)計出一種新型的、改進的DNA編碼序列設(shè)計算法(MO_DE)。實驗與分析表明，MO_DE算法與同類型算法相比，在計算效率、優(yōu)化性方面均具有一定優(yōu)勢。在將來，自適應(yīng)算法[12]的應(yīng)用分析，能夠使其DNA編碼序列設(shè)計問題得到更好的提高與解決，這將是下一步的研究方向。

[1] Chang Wenglong, Vasilakos A V.DNA algorithms of implementing biomolecular databases on a biological computer[J].IEEE Transactions on NanoBioscience,2015,14(2):104-111.

[2] Cui G Z,Qin L M.Modified PSO algorithm for solving planar graph coloring problem[J].Progress in Natural Science,2008,18(3):353-357.

[3] 張強,王賓,張銳,等.基于動態(tài)遺傳算法的DNA序列集合設(shè)計[J].計算機學報,2008,31(12):2193-2199.

[4] Zhang X,Wang Y,Cui G,et al.Application of a novel IWO to the design of encoding sequences for DNA computing[J].Computers and Mathematics with Applications,2009,57(11/12):2001-2008.

[5] Shin S Y,Lee I H,Kim D,et al.Multiobjective evolutionary optimization of DNA sequences for reliable DNA computing[J].IEEE Transactions on Evolutionary Computation,2005,9(2):143-158.

[6] Wang W,Zheng X,Zhang Q,et al.The optimization of DNA encodings based on GA/SA algorithm[J].Progress in Natural Science,2007,17(6):739-744.

[7] 殷脂,葉春明,馬慧民,等.基于文化進化粒子群算法的DNA序列設(shè)計[J].計算機工程與應(yīng)用,2011,47(1):40-42.

[8] 張凱,耿修堂,肖建華,等.DNA編碼問題及其復雜性研究[J].計算機應(yīng)用研究,2008,25(11):3264-3267.

[9] Cervantes-Salido V M,Jaime O,Brizuela C A,et al. Improving the design of sequences for DNA computing: a multiobjecticve evolutionary approach[J].Applied Soft Computing,2013,13(12):4594-4607.

[10] 段海濱,王道波,朱家強,等.蟻群算法理論及應(yīng)用研究的進展[J].控制與決策,2004,19(12):1321-1326.

[11] Chaves-Gonzaiez J M,Vega-Rodriguez M A,Granado-riado J M.A multiobjective swarm intelligence approach based on artificial bee colony for reliable DNA sequence design[J].Engineering Applications of Artificial Intelligence,2013,26(9):2045-2057.

[12] Sharma S,Saxen R,Sharma S.Identification of mircrosatellites in DNA using adaptive S-transform[J].IEEE Journal of Biomedical and Health Informatics,2014,19(3):1097-1105.

MO_DE: A DNA Coding Sequence Algorithm Based on Multi-objective Optimization Mechanisms

CENWei

(Shanghai Pudong Development Bank, Shanghai 200042, China)

Aiming at the poor stability and reliability problems of sequence design existed in DNA computing, a DNA coding sequence design algorithm based on multi-objective optimization mechanism (MO_DE: multi-objective design algorithm) was designed with a full consideration of basic coding issues. Under certain constraints, MO_DE algorithm established a DNA sequence shared function by using multi-objective optimization mechanism and small populations ant colony algorithm, and adding the h-distance factor to the single stranded DNA architecture. The simulation experiments show that the MO_DE algorithm has certain advantages in computing efficiency and optimization compared with same type algorithms.

DNA computing; multi-objective optimization; small populations ant colony; coding sequence; MO_DE

2015-04-23

岑 巍(1974-),男,浙江余姚人,工程師,碩士,主要從事商業(yè)銀行中間業(yè)務(wù)產(chǎn)品研發(fā)和數(shù)據(jù)庫優(yōu)化、云計算等方面的研究,(E-mail)2656543164@qq.com

1673-1549(2015)03-0046-05

10.11863/j.suse.2015.03.10

TP301

A