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

鄭學(xué)東

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

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

鄭學(xué)東

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

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

DNA計算;DNA編碼;遺傳算法;聚類分析;小生境;模運算

1 概述

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

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

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

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

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

2.1 約束條件

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

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

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

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

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

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

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

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

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

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

2.2 優(yōu)化模型

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

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

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

3 本文算法設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 小種群遺傳算法流程

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

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

4 實驗結(jié)果與比較

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

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

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

表2 文獻[13]中長度為20的7個DNA編碼結(jié)果

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

表4 文獻[13]中長度為20的14個DNA編碼結(jié)果

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

表6 文獻[13]中長度為15的20個DNA編碼結(jié)果

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

圖2 長度為20的7個DNA編碼評估項比較

圖3 長度為20的14個DNA編碼評估項比較

圖4 長度為15的20個DNA編碼評估項比較

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

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

5 結(jié)束語

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

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

[2] Ignatova Z,Martinez-Perez I,Zimmermann K H.DNA計算模型[M].郗 方,王淑棟,強小利,譯.北京:清華大學(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] 張 強,王 賓,張 銳,等.基于動態(tài)遺傳算法的DNA序列集合設(shè)計[J].計算機學(xué)報,2008,31(12):2193-2199.

[11] 王向紅,劉文斌,朱翔鷗,等.DNA計算中的單模板編碼方法改進研究[J].電子學(xué)報,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編碼問題及其復(fù)雜性研究[J].計算機應(yīng)用研究,2008,25(11):3264-3267.

[15] Pedrycz W.基于知識的聚類:從數(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] 周 明,孫樹棟.遺傳算法原理及應(yīng)用[M].北京:國防工業(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].計算機工程,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

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

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

2014-01-28

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