基于聚類小生境遺傳算法的DNA編碼優化

鄭學東

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

基于聚類小生境遺傳算法的DNA編碼優化

鄭學東

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

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

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

1 概述

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

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

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

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

2 DNA編碼的相關約束與優化模型

2.1 約束條件

本文采用的相關約束具體如下:

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

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

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

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

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

(5)發卡(Hp):DNA序列可能發生自雜交,并形成環狀結構,一般發卡結構是希望避免的。一個DNA分子可能出現的發卡數量可以通過以下公式進行估計:

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

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

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

2.2 優化模型

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

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

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

3 本文算法設計

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

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

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

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

其中,fi∈{fSm,fHM,-fGC,-fCon,-fHp,-fTm};αi為權重系數。

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

(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的子式,將其上整數值隨機替換為其余堿基對應的整數值。

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

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

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

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

圖1 小種群遺傳算法流程

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

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

4 實驗結果與比較

本文算法用Matlab語言實現,算法參數設置如表1所示,DNA序列的Tm值計算采用Matlab中Bioinformatics Toolbox中的相應函數。

表1 算法參數設置

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

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

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

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

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

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

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

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

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

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

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

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

5 結束語

本文基于聚類小生境技術,利用小種群遺傳算法求解DNA編碼問題。小種群遺傳算法的成功應用說明了DNA編碼問題可以視為一個多模函數的優化問題。在一般聚類分析中,類的個數是一個難于預先確定的量,由于DNA編碼中已確定需要的DNA編碼序列數量,因此聚類過程中類的個數是預先選定的。如果不預先指定類的個數,則可以預期在同等約束條件下得到更多的DNA編碼序列。今后將結合局部搜索方法及自適應方法,進一步提高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].郗 方,王淑棟,強小利,譯.北京:清華大學出版社,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] 張 強,王 賓,張 銳,等.基于動態遺傳算法的DNA序列集合設計[J].計算機學報,2008,31(12):2193-2199.

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

[15] Pedrycz W.基于知識的聚類:從數據到信息粒[M].于福生,譯.北京:北京師范大學出版社,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] 周 明,孫樹棟.遺傳算法原理及應用[M].北京:國防工業出版社,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

鄭學東.基于聚類小生境遺傳算法的DNA編碼優化[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

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

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

2014-01-28

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