基于聚類小生境遺傳算法的DNA編碼優(yōu)化

鄭學(xué)東

(大連大學(xué)先進(jìn)設(shè)計(jì)與智能計(jì)算省部共建教育部重點(diǎn)實(shí)驗(yàn)室,遼寧大連116622)

基于聚類小生境遺傳算法的DNA編碼優(yōu)化

鄭學(xué)東

(大連大學(xué)先進(jìn)設(shè)計(jì)與智能計(jì)算省部共建教育部重點(diǎn)實(shí)驗(yàn)室,遼寧大連116622)

DNA編碼優(yōu)化問(wèn)題是DNA計(jì)算中的核心問(wèn)題。分析DNA編碼優(yōu)化的約束條件,在單鏈DNA序列集合上引入h距離,將聚類小生境技術(shù)應(yīng)用于小種群遺傳算法的構(gòu)造,對(duì)DNA編碼優(yōu)化問(wèn)題進(jìn)行求解。基于h距離定義DNA序列間的相似函數(shù),將堿基字母編碼為4進(jìn)制整數(shù)、DNA編碼序列作為個(gè)體編碼為4進(jìn)制整數(shù)向量、種群編碼為4進(jìn)制整數(shù)矩陣,基于模4算術(shù)運(yùn)算,構(gòu)造相應(yīng)的遺傳算子,并給出DNA編碼序列的具體計(jì)算結(jié)果。實(shí)驗(yàn)結(jié)果表明,與現(xiàn)有DNA編碼序列優(yōu)化結(jié)果相比,該算法可得到更好的DNA編碼序列且計(jì)算效率較高。

DNA計(jì)算;DNA編碼;遺傳算法;聚類分析;小生境;模運(yùn)算

1 概述

DNA編碼問(wèn)題是DNA計(jì)算[1-2]研究中的首要與核心問(wèn)題[3]。在DNA編碼問(wèn)題中,首要目標(biāo)是提高DNA編碼序列的特異性識(shí)別能力,即降低DNA序列間的相似性。文獻(xiàn)[4]提出用最小相同子序列來(lái)定義不同DNA編碼序列之間的相似程度。由于DNA分子在溶液中可以自由擴(kuò)散與相對(duì)移動(dòng),文獻(xiàn)[5]提出用移位測(cè)度(h-measure)來(lái)刻畫(huà)DNA編碼序列之間的相似性。盡管移位測(cè)度不滿足距離公理,但由于考慮了在DNA序列間可能發(fā)生的移位雜交,因此其仍是一個(gè)度量DNA序列間相似程度的較好方法。Phan等人于2009年基于移位測(cè)度進(jìn)一步定義了h距離(h-distance)[6],并對(duì)相應(yīng)距離空間的幾何性質(zhì)進(jìn)行了討論,給出了DNA序列集合設(shè)計(jì)的相應(yīng)結(jié)果。由于DNA分子具有特殊的理化性質(zhì),為了保證參與生化反應(yīng)的DNA分子具有一致的理化性質(zhì),在DNA編碼過(guò)程中還需考慮其他諸如自由能、解鏈溫度、連續(xù)性、GC含量等DNA分子的熱力學(xué)約束以及發(fā)卡等二級(jí)結(jié)構(gòu)約束[7]。

上述相關(guān)約束大致可以分為2類:一類是漢明距離類約束(或稱為組合類約束,約束條件主要基于漢明距離定義,如相似性與移位測(cè)度),這類約束的主要目標(biāo)是增加DNA分子的特異性識(shí)別能力,避免出現(xiàn)假陽(yáng)性或假陰性的錯(cuò)誤配對(duì);另一類是熱力學(xué)約束及二級(jí)結(jié)構(gòu)類約束,這類約束的主要目標(biāo)是保證DNA分子理化性質(zhì)的穩(wěn)定性與一致性,以保證生化反應(yīng)的順利進(jìn)行。

對(duì)于DNA編碼問(wèn)題,求解方法主要有隨機(jī)搜索[8]、進(jìn)化算法[9-10]、模板映射方法[11]、多目標(biāo)優(yōu)化[12-13]等。DNA編碼問(wèn)題是一個(gè)難于求解的問(wèn)題[14],目前還沒(méi)有統(tǒng)一的規(guī)范方法來(lái)求解。

聚類分析方法作為一種數(shù)據(jù)分析手段,已在模式識(shí)別、數(shù)據(jù)挖掘等方面得到了廣泛應(yīng)用[15]。本文利用聚類小生境技術(shù),在單鏈DNA序列集合上引入h距離,定義單鏈DNA序列間的相似性度量函數(shù),采用小種群遺傳算法,基于模4算術(shù)運(yùn)算,設(shè)計(jì)3個(gè)遺傳算子,對(duì)DNA編碼問(wèn)題進(jìn)行求解,并給出具體的DNA編碼序列。

2 DNA編碼的相關(guān)約束與優(yōu)化模型

2.1 約束條件

本文采用的相關(guān)約束具體如下:

(1)相似性(Sm):對(duì)長(zhǎng)度為n的2個(gè)DNA序列Dj與Dk,其相似性度量的數(shù)學(xué)定義為:

(2)移位測(cè)度(HM):在考慮相對(duì)移動(dòng)的情況下,為避免2個(gè)DNA編碼序列之間的雜交,引入hmeasure,其數(shù)學(xué)定義為:

(3)GC含量(GC):即堿基G與C在DNA序列中的百分比,GC含量約束可表示為:

其中,GC(Dj)表示序列Dj的GC含量;GCgoal表示GC含量的目標(biāo)值;kGC表示可接受范圍。

(4)連續(xù)性(Con):在DNA序列中,如果相同堿基連續(xù)重復(fù)出現(xiàn),則其生化反應(yīng)將難以控制,在序列設(shè)計(jì)中要盡量避免相同堿基的連續(xù)出現(xiàn)。連續(xù)性約束可表示為:

(5)發(fā)卡(Hp):DNA序列可能發(fā)生自雜交,并形成環(huán)狀結(jié)構(gòu),一般發(fā)卡結(jié)構(gòu)是希望避免的。一個(gè)DNA分子可能出現(xiàn)的發(fā)卡數(shù)量可以通過(guò)以下公式進(jìn)行估計(jì):

其中,Hp(p,r,s,Dj)表示在序列Dj中,開(kāi)始于位置p,環(huán)長(zhǎng)為r,莖長(zhǎng)為s的發(fā)卡數(shù)。令KHp表示發(fā)卡數(shù)量的可接受范圍,則發(fā)卡約束可表示為:

(6)解鏈溫度(Tm):即在DNA變性過(guò)程中, 50%的DNA雙鏈變成單鏈時(shí)的溫度,其計(jì)算可采用最近鄰模型[16]。令Tm(Dj)表示序列Dj的Tm值,Tmgoal表示Tm的目標(biāo)值,kTm表示可接受的Tm值范圍,則Tm約束可表示為:

在上述約束條件中,相似性約束與移位測(cè)度約束反映了DNA序列及其逆補(bǔ)序列之間公共子序列的共享程度,反映了DNA編碼序列之間的相互關(guān)系;其他熱力學(xué)與二級(jí)結(jié)構(gòu)類約束則為施加于DNA序列自身的約束,是一種個(gè)體約束,反映了DNA編碼序列自身的性質(zhì)。另外,Gibbs自由能可以通過(guò)其他約束的組合來(lái)替代,因此,這里不考慮Gibbs自由能約束[12]。

2.2 優(yōu)化模型

由于DNA分子在溶液中可以相對(duì)移動(dòng)與自由擴(kuò)散,對(duì)于編碼序列集合C,DNA序列的特異性識(shí)別能力取決于彼此間的最小相似性,DNA編碼序列間發(fā)生錯(cuò)誤雜交的可能性取決于彼此間的最小移位測(cè)度,因此這里分別取集合C中序列的相似性與移位測(cè)度的最小值作為目標(biāo)函數(shù),其定義為:

將連續(xù)性約束fCon(Dj)、發(fā)卡約束fHp(Dj)、GC含量約束fGC(Dj)與Tm值約束fTm(Dj)作為優(yōu)化模型的約束條件。

于是,DNA編碼問(wèn)題可以轉(zhuǎn)化尋找DNA序列集合C?{A,C,G,T}?,使得對(duì)?Dj∈C,滿足如下的最大值多目標(biāo)優(yōu)化問(wèn)題:

3 本文算法設(shè)計(jì)

上述定義在DNA雙鏈集合中引入了h距離,使其成為距離空間。盡管h距離定義于雙鏈DNA集合上,但若將DNA序列及其逆補(bǔ)序列視為由單鏈DNA序列構(gòu)成的等價(jià)類,則可以將h距離引入到單鏈DNA集合。對(duì)于序列Dj與Dk,定義單鏈DNA序列的h距離為:

其中,hd同時(shí)反映了序列Dj與Dk在相似性與移位測(cè)度2個(gè)度量方面的相似程度。

本文將式(11)作為DNA序列間的相似性度量,利用基于聚類小生境的小種群遺傳算法,對(duì)優(yōu)化模型式(9)進(jìn)行求解。一般在基于進(jìn)化算法或多目標(biāo)優(yōu)化的DNA編碼問(wèn)題求解方法中[9-10,12-13],大多將編碼集合C作為個(gè)體,即將DNA編碼序列連接后作為個(gè)體,本文直接將DNA編碼序列作為種群個(gè)體,個(gè)體編碼采用4進(jìn)制整數(shù),即將堿基{A,C,G,T}編碼為{0,1,2,3},則DNA編碼序列可以視為一個(gè)4元碼,遺傳算法的種群編碼為4進(jìn)制整數(shù)矩陣Pm×n,其中,n表示個(gè)體長(zhǎng)度;m表示種群規(guī)模,算法輸出Pm×n的子式CM×n作為DNA編碼的結(jié)果,M表示DNA編碼序列的數(shù)量,同時(shí)也是聚類過(guò)程中分類的個(gè)數(shù)。

個(gè)體適應(yīng)度函數(shù)為優(yōu)化模型式(9)中目標(biāo)函數(shù)與約束條件的線性組合,定義如下:

其中,fi∈{fSm,fHM,-fGC,-fCon,-fHp,-fTm};αi為權(quán)重系數(shù)。

在遺傳算法中采用如下遺傳算子:

(1)模交叉算子(Modular Arithmetic Crossover Operator,MAXO):以概率pMAXO隨機(jī)選擇Pm×n的兩行作為父代個(gè)體,通過(guò)模4的加法與減法得到2個(gè)子代個(gè)體。

(2)多點(diǎn)交叉算子(MultipointCrossover Operator,MXO):以概率pMXO隨機(jī)選擇Pm×n的兩行,隨機(jī)選擇l個(gè)位點(diǎn)進(jìn)行交叉。

(3)子式變異算子(Minor Mutation Operator, MMO):以概率pMMO隨機(jī)選擇Pm×n的子式,將其上整數(shù)值隨機(jī)替換為其余堿基對(duì)應(yīng)的整數(shù)值。

(4)逆密碼子變異算子(Reverse Codon Mutation Operator,RMO):令密碼子長(zhǎng)度為r,以概率pRMO隨機(jī)選擇Pm×n的k×r級(jí)子式,將k×r級(jí)子式按行翻轉(zhuǎn)。

(5)逆補(bǔ)密碼子變異算子(Reverse Complementary Codon Mutation Operator,RCMO):令密碼子長(zhǎng)度為r,以概率pRCMO隨機(jī)選擇Pm×n的k×r級(jí)子式,將對(duì)應(yīng)整數(shù)值按模4取補(bǔ)后再按行翻轉(zhuǎn)。

(6)選擇算子(Selection Operator,SO):為降低選擇誤差,采用無(wú)回放余數(shù)隨機(jī)選擇法(Remainder Stochastic Sampling with Replacement,RSSR)[17]。

算法終止條件為連續(xù)進(jìn)化500代后停止。算法流程如圖1所示。為了擴(kuò)大算法搜索空間,在算法執(zhí)行過(guò)程使用種群膨脹,膨脹規(guī)模至多為初始種群規(guī)模的5倍。

圖1 小種群遺傳算法流程

在一般基于進(jìn)化計(jì)算的DNA編碼問(wèn)題求解方法中,大多將C作為個(gè)體,若采用同樣的編碼方式,

則其種群編碼為m×(n×M)階矩陣Pm×(n×M),其存儲(chǔ)復(fù)雜度大致為小種群遺傳算法的M倍。衡量進(jìn)化算法復(fù)雜度的一種方式是考察每代種群中適應(yīng)度函數(shù)的計(jì)算次數(shù)及其計(jì)算復(fù)雜度,在上述算法中,適應(yīng)度的計(jì)算復(fù)雜度主要來(lái)自于Sm與HM這2個(gè)約束條件的計(jì)算,對(duì)于包含m個(gè)個(gè)體的種群,每個(gè)個(gè)體Sm與HM的計(jì)算次數(shù)為m2,因此在每一代種群中應(yīng)用適應(yīng)度進(jìn)行個(gè)體評(píng)估時(shí)的計(jì)算復(fù)雜度可以視為O(m3)。

4 實(shí)驗(yàn)結(jié)果與比較

本文算法用Matlab語(yǔ)言實(shí)現(xiàn),算法參數(shù)設(shè)置如表1所示,DNA序列的Tm值計(jì)算采用Matlab中Bioinformatics Toolbox中的相應(yīng)函數(shù)。

表1 算法參數(shù)設(shè)置

理論上,相似性與移位測(cè)度的值越大,則DNA序列之間發(fā)生錯(cuò)誤雜交的可能性越低;GC含量與Tm值的分布越集中、連續(xù)性值越低,則DNA序列理化性質(zhì)的一致性越好;發(fā)卡的值越低則DNA序列出現(xiàn)二級(jí)結(jié)構(gòu)的可能性越低。基于上述考慮,提出以下DNA編碼評(píng)估標(biāo)準(zhǔn):選擇編碼序列集合的最小相似性(minSm)與最小移位測(cè)度(minHM)作為評(píng)估項(xiàng),以反映DNA編碼序列的特異性識(shí)別能力;選擇GC含量與Tm值的標(biāo)準(zhǔn)差(σ(GC),σ(Tm)),選擇發(fā)卡與連續(xù)性的和(sumCon,sumHp)作為評(píng)估項(xiàng),以反映DNA分子理化性質(zhì)的一致性。為說(shuō)明算法的有效性,將實(shí)驗(yàn)結(jié)果與目前最新的DNA編碼優(yōu)化結(jié)果——文獻(xiàn)[13]中的結(jié)果進(jìn)行比較,比較結(jié)果如表2～表7所示,編碼評(píng)估項(xiàng)的比較如圖2～圖4所示。

表2 文獻(xiàn)[13]中長(zhǎng)度為20的7個(gè)DNA編碼結(jié)果

表3 本文長(zhǎng)度為20的7個(gè)DNA編碼結(jié)果

表4 文獻(xiàn)[13]中長(zhǎng)度為20的14個(gè)DNA編碼結(jié)果

表5 本文長(zhǎng)度為20的14個(gè)DNA編碼結(jié)果

表6 文獻(xiàn)[13]中長(zhǎng)度為15的20個(gè)DNA編碼結(jié)果

表7 本文長(zhǎng)度為15的20個(gè)DNA編碼結(jié)果

圖2 長(zhǎng)度為20的7個(gè)DNA編碼評(píng)估項(xiàng)比較

圖3 長(zhǎng)度為20的14個(gè)DNA編碼評(píng)估項(xiàng)比較

圖4 長(zhǎng)度為15的20個(gè)DNA編碼評(píng)估項(xiàng)比較

由上述比較結(jié)果可知,在所有的評(píng)估項(xiàng)上,本文算法均可以獲得更好的解,尤其是在連續(xù)性方面可以獲得較大改善,且序列Tm值與GC含量分布更為集中,說(shuō)明DNA序列理化性質(zhì)具有更好的一致性,由于DNA序列的長(zhǎng)度較短,因此2種算法在發(fā)卡評(píng)估項(xiàng)上的結(jié)果相同。

在文獻(xiàn)[13]中種群規(guī)模為3 000,本文算法的初始種群在3種編碼情形中分別為20,30,60,考慮到算法運(yùn)行過(guò)程中的種群膨脹,種群規(guī)模至多為100, 150,300,另外,文獻(xiàn)[13]中的種群個(gè)體對(duì)應(yīng)為一個(gè)DNA編碼集合,即M個(gè)長(zhǎng)度為n的DNA序列的連接為一個(gè)個(gè)體,本文種群個(gè)體僅為一個(gè)長(zhǎng)度為n的DNA序列,因此本文算法的計(jì)算量要小得多,計(jì)算效率更好。

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

本文基于聚類小生境技術(shù),利用小種群遺傳算法求解DNA編碼問(wèn)題。小種群遺傳算法的成功應(yīng)用說(shuō)明了DNA編碼問(wèn)題可以視為一個(gè)多模函數(shù)的優(yōu)化問(wèn)題。在一般聚類分析中,類的個(gè)數(shù)是一個(gè)難于預(yù)先確定的量,由于DNA編碼中已確定需要的DNA編碼序列數(shù)量,因此聚類過(guò)程中類的個(gè)數(shù)是預(yù)先選定的。如果不預(yù)先指定類的個(gè)數(shù),則可以預(yù)期在同等約束條件下得到更多的DNA編碼序列。今后將結(jié)合局部搜索方法及自適應(yīng)方法,進(jìn)一步提高DNA編碼問(wèn)題求解的效率。

[1] Adleman L.MolecularComputationofSolutionto Combinatorial Problems[J].Science,1994,266(5187): 1021-1023.

[2] Ignatova Z,Martinez-Perez I,Zimmermann K H.DNA計(jì)算模型[M].郗 方,王淑棟,強(qiáng)小利,譯.北京:清華大學(xué)出版社,2010.

[3] Garzon M H,DeatonRJ.CodewordDesignand Information Encoding in DNA Ensembles[J].Natural Computing,2004,3(3):253-292.

[4] Baum E B.DNA Sequences Useful for Computation: USA,EP0772135A1[P].1997-05-07.

[5] Garzon M,Neathery P,Deaton R J,et al.A New Metric for DNA Computing[C]//Proceedings of the 2nd Annual Genetic Programming Conference.San Francisco,USA: Morgan Kaufmann,1997:472-487.

[6] Phan V,Garzon M.On Codeword Design in Metric DNA Spaces[J].Natural Computing,2009,8(3):571-588.

[7] Sager J,Stefanovic D.Designing Nucleotide Sequences for Computation:A Survey of Constraints[C]//Proceedings of the11th InternationalMeeting on DNA Computing. London,UK:Springer-Verlag,2006:275-289.

[8] Penchovsk Y R,Ackermann J.DNA Library Design for Molecular Computation[J].Journal of Computational Biology,2003,10(2):215-229.

[9] Wang Wei,Zheng Xuedong,Zhang Qiang,et al.The Optimization of DNA Encoding Based on GA/SA Algorithm[J].Progress in Natural Science,2007,17(6):739-744.

[10] 張 強(qiáng),王 賓,張 銳,等.基于動(dòng)態(tài)遺傳算法的DNA序列集合設(shè)計(jì)[J].計(jì)算機(jī)學(xué)報(bào),2008,31(12):2193-2199.

[11] 王向紅,劉文斌,朱翔鷗,等.DNA計(jì)算中的單模板編碼方法改進(jìn)研究[J].電子學(xué)報(bào),2009,37(12): 2720-2724.

[12] Shin S Y,LeeIH,KimD,etal.Multiobjective EvolutionaryOptimizationofDNASequencesfor Reliable DNA Computing[J].IEEE Transactions on Evolutionary Computation,2005,9(2):143-158.

[13] Chaves-González J M,Vega-RodríguezMA.DNA Strand Generation for DNA Computing by Using a Multi-objective Differential Evolution Algorithm[J]. BioSystems,2014,116:49-64.

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

[15] Pedrycz W.基于知識(shí)的聚類:從數(shù)據(jù)到信息粒[M].于福生,譯.北京:北京師范大學(xué)出版社,2008.

[16] Santalucia J J R,Hicks D.The Thermodynamics of DNA Structural Motifs[J].Annual Review of Biophysics and Biomolecular Structure,2004,33:415-440.

[17] 周 明,孫樹(shù)棟.遺傳算法原理及應(yīng)用[M].北京:國(guó)防工業(yè)出版社,1999.

編輯 陸燕菲

Optimization of DNA Coding Based on Clustering Niche Genetic Algorithm

ZHENG Xuedong
(Key Laboratory of Advanced Design and Intelligent Computing,Ministry of Education,Dalian University,Dlian116622,China)

The optimization of DNA coding plays an important role in DNA computing.In this paper,the constraints of the optimization of DNA coding are described,an h distance is introduced over the set of single DNA strands and a clustering-based niche technique is applied to construct the micro-genetic algorithm which is used to solve the problem of the optimization of DNA coding.In the algorithm,a similarity function between different DNA sequences is defined based on the h distance.The base letters are encoded by quaternary integers,the DNA coding sequences are encoded by the vector of quaternary integers as individuals and the population is encoded by the matrix of quaternary integers.Several genetic operators are constructed based on modulo 4 arithmetic operation and the concrete computing results are presented.Experimental results show that compared with the latest results,the algorithm can get better DNA coding sequences and improve the efficiency of computation.

DNA computing;DNA coding;genetic algorithm;clustering analysis;niche;modular operation

鄭學(xué)東.基于聚類小生境遺傳算法的DNA編碼優(yōu)化[J].計(jì)算機(jī)工程,2015,41(2):135-140.

英文引用格式:Zheng Xuedong.Optimization of DNA Coding Based on Clustering Niche Genetic Algorithm[J]. Computer Engineering,2015,41(2):135-140.

1000-3428(2015)02-0135-06

:A

:TP301.6

10.3969/j.issn.1000-3428.2015.02.026

國(guó)家自然科學(xué)基金資助項(xiàng)目(31170797,31370778,61103057,61370005);遼寧省教育廳科研基金資助項(xiàng)目(L2011218);長(zhǎng)江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃基金資助項(xiàng)目(IRT1109)。

鄭學(xué)東(1977-),男,講師、博士,主研方向:DNA計(jì)算。

2014-01-28

:2014-04-03E-mail:xuedongzheng@163.com