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

岑巍

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

?

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

岑巍

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

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

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

引言

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

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

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

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

1.1 約束限制

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

(1) 相似性

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

H(Dj,σl(Dk))=

(1)

(2)

由此可知：

(3)

依據(jù)DNA編碼序列的無(wú)限制運(yùn)動(dòng)與全面擴(kuò)展[9]，利用以下最小相似性作為目標(biāo)方法：

(4)

(2) 移動(dòng)測(cè)度

移動(dòng)測(cè)度主要是使用于標(biāo)記DNA編碼序列中各個(gè)移位運(yùn)動(dòng)概率值，設(shè)定：

(5)

(6)

(3)h-距離

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

(7)

(4)GC含量

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

(8)

(5)Tm溫度

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

(9)

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

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

(10)

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

fHP(Dj)≤kHP

(11)

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

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

(12)

fCon(Dj,N)≤kCon

(13)

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

依據(jù)上述提供的多種目標(biāo)方法與約束條件的局限限制，DNA編碼序列設(shè)計(jì)思路能夠構(gòu)成一種標(biāo)準(zhǔn)的優(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è)計(jì)過(guò)程中的約束限制與優(yōu)化結(jié)構(gòu)，設(shè)計(jì)出一種結(jié)合多目標(biāo)優(yōu)化機(jī)制的小種蟻群算法，將其應(yīng)用與DNA編碼序列中，從而產(chǎn)生出MO_DE算法。

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

(15)

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

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

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

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

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

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

(7) 終止操作。持續(xù)進(jìn)化時(shí)間長(zhǎng)度超過(guò)幾百年且達(dá)到歷史最優(yōu)化解時(shí)終止，不刷新操作。

通過(guò)上述算子元素，其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算法流程中會(huì)出現(xiàn)對(duì)應(yīng)的種群分散與擴(kuò)展現(xiàn)象，其大小分散與擴(kuò)展的上限大致是初始化狀態(tài)的5倍至7倍左右。

3 模擬實(shí)驗(yàn)與結(jié)果分析

針對(duì)相關(guān)約束限制與優(yōu)化模型，在Matlab 7.0的平臺(tái)環(huán)境下，對(duì)設(shè)計(jì)的MO_DE算法進(jìn)行模擬實(shí)驗(yàn)，操作環(huán)境為：Pentium Dual E2104，2.5 GHz，512 MB，Windows2008。設(shè)置參數(shù)因子：(1)DNA編碼序列發(fā)卡數(shù)值是0；(2)GC含量是50%；(3)對(duì)應(yīng)于MO_DE算法的各個(gè)參數(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)，以七個(gè)DNA編碼序列為示例，實(shí)驗(yàn)結(jié)果見(jiàn)表1。

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

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

表2 DNA編碼序列結(jié)果評(píng)估項(xiàng)對(duì)比表

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

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

圖2 MO_DE算法的進(jìn)化收斂圖

4 結(jié)束語(yǔ)

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

[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] 張強(qiáng),王賓,張銳,等.基于動(dòng)態(tài)遺傳算法的DNA序列集合設(shè)計(jì)[J].計(jì)算機(jī)學(xué)報(bào),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] 殷脂,葉春明,馬慧民,等.基于文化進(jìn)化粒子群算法的DNA序列設(shè)計(jì)[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(1):40-42.

[8] 張凱,耿修堂,肖建華,等.DNA編碼問(wèn)題及其復(fù)雜性研究[J].計(jì)算機(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] 段海濱,王道波,朱家強(qiáng),等.蟻群算法理論及應(yīng)用研究的進(jìn)展[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ù)庫(kù)優(yōu)化、云計(jì)算等方面的研究,(E-mail)2656543164@qq.com

1673-1549(2015)03-0046-05

10.11863/j.suse.2015.03.10

TP301

A