基于Memetic算法的DNA序列數(shù)據(jù)壓縮方法

譚 麗 孫季豐 郭禮華

?

基于Memetic算法的DNA序列數(shù)據(jù)壓縮方法

譚 麗*孫季豐 郭禮華

(華南理工大學(xué)電子與信息學(xué)院 廣州 510641)

該文提出一種基于CPMA(Collaborative Particle swarm optimization-based Memetic Algorithm) 算法的DNA序列數(shù)據(jù)壓縮方法，CPMA分別采用綜合學(xué)習(xí)粒子群優(yōu)化(Comprehensive Learning Particle Swarm Optimization, CLPSO)算法和動(dòng)態(tài)調(diào)整的混沌搜索算子(Dynamic Adjustive Chaotic Search Operator, DACSO)進(jìn)行全局搜索和局部搜索。該文采用CPMA尋找全局最優(yōu)的基于擴(kuò)展操作的近似重復(fù)矢量(Extended Approximate Repeat Vector, EARV)碼書，并用此碼書壓縮DNA序列數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明，CPMA比其它優(yōu)化算法有很大的改善，對(duì)文中采用的大部分測試函數(shù)，其解都非常接近全局最優(yōu)點(diǎn)；對(duì)于DNA基準(zhǔn)測序序列，與文中所列的經(jīng)典DNA序列壓縮算法相比，基于CPMA算法的壓縮性能得到了顯著提升。

DNA序列壓縮；Memetic算法；擴(kuò)展的近似重復(fù)矢量(EARV)；粒子群優(yōu)化(PSO)；動(dòng)態(tài)混沌局部搜索

1 引言

DNA(DeoxyriboNucleic Acid)是由多個(gè)核苷酸頭尾相連而成的生物大分子化合物，是儲(chǔ)存、復(fù)制和傳遞遺傳信息的主要物質(zhì)基礎(chǔ)[1]。隨著人類DNA序列測定工程的快速發(fā)展，DNA序列數(shù)據(jù)壓縮技術(shù)的研究已經(jīng)成為人們關(guān)注的熱點(diǎn)之一。如何在有限的存儲(chǔ)資源內(nèi)有效儲(chǔ)存急劇膨脹的DNA序列數(shù)據(jù)，用較小的存儲(chǔ)空間存放較大的DNA序列數(shù)據(jù)是計(jì)算機(jī)專家和生物學(xué)家面臨的新課題。

由于DNA序列數(shù)據(jù)的特殊性，使用傳統(tǒng)的壓縮算法并不是很理想。由此出現(xiàn)了許多專門針對(duì)DNA序列的壓縮算法，如GenCompress[2], DNApack[3], GeNML[4]等。這些算法大部分都屬于基于替代的壓縮算法，主要是利用了DNA序列數(shù)據(jù)中的冗余特性 (如直接重復(fù)、鏡像、反轉(zhuǎn)和互補(bǔ)回文)，使用了基于字典或其它更為簡略的表達(dá)方式去替代存儲(chǔ)匹配的DNA序列子串，以達(dá)到壓縮的目的。然而DNA序列數(shù)據(jù)壓縮算法的性能評(píng)價(jià)標(biāo)準(zhǔn)[5]表明，已有的DNA壓縮算法存在耗時(shí)長，資源消耗大，壓縮性能不穩(wěn)定等問題。針對(duì)以上問題，紀(jì)震等人[6]于2010年首次將DNA序列數(shù)據(jù)的生物信息學(xué)特征和生物學(xué)含義引入到壓縮處理中，打破了以往僅從數(shù)據(jù)構(gòu)成特點(diǎn)入手的DNA序列壓縮算法模式。文獻(xiàn)[7]提出一種在線DNA壓縮機(jī)算法(DNA Sequence Compressor, DNASC)，該算法從水平和垂直方向?qū)NA序列數(shù)據(jù)進(jìn)行在線壓縮，最大特點(diǎn)是基于替代和統(tǒng)計(jì)的混合算法。2012年，文獻(xiàn)[8]又提出基于自配置單粒子優(yōu)化的DNA序列壓縮算法(Self-Configuration Single Particle Optimizer, SCSPO)，采用自配置結(jié)構(gòu)的粒子群優(yōu)化算法優(yōu)化碼書，然后利用此碼書壓縮DNA序列數(shù)據(jù)，從而達(dá)到較好的壓縮效果；該算法成功地將智能優(yōu)化算法應(yīng)用于DNA序列數(shù)據(jù)的壓縮過程。

本文借鑒SCSPO算法思想，提出了另外一種基于Memetic算法的DNA序列數(shù)據(jù)的壓縮方法(Collaborative Particle swarm optimization-based Memetic Algorithm, CPMA)。CPMA算法將綜合學(xué)習(xí)粒子群優(yōu)化算法 (Comprehensive Learning Particle Swarm Optimizer, CLPSO)[9]作為全局搜索，同時(shí)設(shè)計(jì)出一種動(dòng)態(tài)調(diào)整的混沌搜索算子(Dynamic Adjustive Chaotic Search Operator, DACSO)作為局部搜索，兩者引入到Memetic算法框架協(xié)同進(jìn)化，找出全局最優(yōu)的基于擴(kuò)展操作的近似重復(fù)矢量(Extended Approximate Repeat Vector, EARV)碼書，用于DNA序列數(shù)據(jù)的壓縮處理。

2 基于擴(kuò)展操作的近似重復(fù)矢量(EARV)碼書模型

(3)字符串刪除(Delete string)：記為(Ds, pos,len)，表示刪除序列子串中從pos開始的長度為len的字符串。，采用ARV編碼所需的編輯操作比特?cái)?shù)目=len，則-= (len -2)′+5′len-3，因len>1，所以(-)>0，即<；

(4)字符交換(Exchange)：記為(, pos1, pos2)，表示交換序列子串中pos1位置和pos2位置的字符。=3+2′，采用ARV編碼所需的編輯操作比特?cái)?shù)目=2，則計(jì)算可得-=7>0，即<；

(5)反序(Inversion)：記為(Inv, pos, len)，其中pos為待反序串的起始位置，len為待反序串的長度。=3+2′，采用ARV編碼所需的編輯操作比特?cái)?shù)目=len，因len>1，有<。

從以上定義及分析可知，EARV比ARV編碼所需的比特?cái)?shù)更少。

假設(shè)有如下一段DNA序列：

圖1中的EARV編碼后的4個(gè)參數(shù)分別代表相對(duì)位置，重復(fù)模式種類，編輯距離和編輯操作。假設(shè)第1個(gè)堿基片段“AATCTG”在序列(*)中的絕對(duì)位置為1，在模式下對(duì)模式串“AACTG”的第3個(gè)位置前插入堿基“T”就可以得到堿基片段“AATCTG”，該近似重復(fù)矢量可表示為{1,,1,(Insc, 3,T)}；同樣在序列(*)2絕對(duì)位置處的第2個(gè)堿基片段“GCCAA”，近似重復(fù)矢量標(biāo)記為{2-1,,1,(, 2,C)}，表示模式串“AACTG”在鏡像匹配下將第2個(gè)堿基替換為堿基“C”，2-1表示第2個(gè)堿基片段“GCCAA”相對(duì)于第1個(gè)堿基片段“AATCTG”的位置。序列(*)中其余3個(gè)近似片段的EARV編碼過程類似。

圖1 EARV碼書中的近似匹配實(shí)例

3 基于Memetic算法的DNA序列數(shù)據(jù)壓縮方法

與單純的進(jìn)化算法相比，Memetic算法往往能以更少的計(jì)算代價(jià)，得到具有更高精確度的解，在解決復(fù)雜、高維、大規(guī)模問題時(shí)具有明顯的優(yōu)勢[11]，近年來受到了國內(nèi)外學(xué)者的重視。考慮到Memetic算法是基于種群全局搜索和個(gè)體局部搜索的混合方法，本文提出了一種基于CPMA的DNA序列數(shù)據(jù)壓縮方法。

3.1 粒子編碼和適應(yīng)度函數(shù)的計(jì)算

將每個(gè)EARV按順序連接，構(gòu)造CPMA尋優(yōu)粒子的位置矢量，對(duì)其進(jìn)行粒子編碼，如圖2所示，其中,分別表示碼書中EARV的長度和數(shù)量。

圖2 使用EARV碼書模型構(gòu)造尋優(yōu)第i個(gè)粒子

適應(yīng)度函數(shù)的計(jì)算過程如圖3所示，先將尋優(yōu)粒子位置矢量離散切分為含有EARV的碼書，接著用AGREP[12](Approximate Global search Regular Expression and Print out the line)近似搜索DNA原始序列中含有的EARV，最后將DNA序列數(shù)據(jù)的壓縮率(Bit Per Base, BPB)作為CPMA的適應(yīng)度函數(shù)值：

其中base表示待壓縮的DNA序列中堿基個(gè)數(shù)，bit為編碼這些堿基所需的比特?cái)?shù)目。適應(yīng)度函數(shù)值越小，說明對(duì)DNA序列數(shù)據(jù)的壓縮率越低，即壓縮性能就越好。

式(1)的bit計(jì)算如式(2)：

對(duì)式(2)進(jìn)一步說明如下：

(1)存儲(chǔ)編碼所用的碼書，需要(2) bit；

(3)ed表示編輯操作的個(gè)數(shù)。為描述一個(gè)編輯操作所需的平均比特?cái)?shù)目，各編輯操作所使用的比特?cái)?shù)目在第2節(jié)已做分析；

(4)mt表示與碼書中的某模式串形成“匹配”的基本堿基個(gè)數(shù)。base-mt表示未形成“匹配”的堿基總個(gè)數(shù)，每個(gè)堿基的編碼采用2 bit的基本編碼。

初始化一粒子群，包含ps個(gè)粒子，一個(gè)粒子代表一個(gè)碼書，維度為。則尋優(yōu)粒子位置矢量離散切分為含有EARV的碼書過程如下：

3.2 全局搜索

在CPMA算法中，采用CLPSO作為全局搜索策略，以保證粒子種群的多樣性。CLPSO算法的速度和位置更新公式[9]如式(4)至式(7)：

(5)

其中為粒子速度矢量，為位置矢量。變量為當(dāng)前更新粒子的序號(hào)，為粒子的維數(shù)(0<<),為迭代次數(shù)；為慣性權(quán)重；rand為[0,1]范圍內(nèi)的均勻隨機(jī)數(shù)；為學(xué)習(xí)因子；f()表示粒子在第維的學(xué)習(xí)對(duì)象。式(5)和式(7)分別控制粒子的速度和位置范圍為[min,max], [min,max]。

其中pbest和pbest+1分別表示第個(gè)粒子在和+1次更新后的局部最優(yōu)位置。

依次考察粒子的第維速度值V，與停滯速度閾值V作比較，若V<V，則用混沌搜索算子(Chaotic Search Operator, CSO)對(duì)粒子進(jìn)行局部搜索。為了從當(dāng)前種群中挑選出合適的粒子進(jìn)行局部搜索，本文采用DACSO的方法，在上一次的局部搜索過程中，若搜索出較多的更優(yōu)粒子，則在下一次的搜索中，增加其搜索比重。本文中的局部搜索主要針對(duì)活潑粒子，采取的策略是：設(shè)定活躍系數(shù)ca和引入差值系數(shù)cd。這兩個(gè)系數(shù)分別動(dòng)態(tài)調(diào)整和混沌搜索次數(shù)，以使優(yōu)秀粒子被賦予更多的搜索機(jī)會(huì)，使非優(yōu)秀粒子減少搜索機(jī)會(huì)，以使局部搜索占用的計(jì)算開銷更有意義。其中第個(gè)粒子的活躍系數(shù)ca定義為式(9)。

其中act表示上一次的局部搜索中粒子尋優(yōu)成功的次數(shù)。

CPMA算法的具體步驟如表1所示。

3.3 局部搜索

考慮到將局部搜索策略應(yīng)用到每一個(gè)粒子上進(jìn)行搜索，會(huì)大大增加算法的運(yùn)行時(shí)間成本，本文采用了DACSO的局部搜索方法。在DACSO中通過cd去動(dòng)態(tài)調(diào)整混沌搜索次數(shù)，使其在較少的計(jì)算次數(shù)內(nèi)獲得更大的性能提升。差值系數(shù)cd定義為式(10)

其中dis=|(pbest)-(gbest)。同時(shí)本文還引進(jìn)動(dòng)態(tài)收縮半徑的機(jī)制，并在收縮區(qū)域內(nèi)隨機(jī)產(chǎn)生粒子來替代性能較差的粒子，如式(11)：

表1 CPMA算法的具體步驟

其中隨著進(jìn)化迭代次數(shù)的增加而動(dòng)態(tài)地變小，其值越小說明DACSO的搜索范圍越小；服從期望值為0，方差為1的高斯分布。設(shè)置混沌初始值cx1= rand(01)，混沌搜索半徑的初值1=(max-min)/2，令=1, DACSO的局部搜索方法步驟如表2所示。

表2 DACSO的局部搜索方法步驟

整體上來說，CPMA算法根據(jù)式(8)從群體中選出備用粒子再進(jìn)行局部搜索。隨著迭代的進(jìn)行，局部搜索DACSO的頻率呈上升趨勢，全局搜索CLPSO根據(jù)DACSO的反饋進(jìn)行粒子間的信息交流，再將結(jié)果作用于式(8)，選定新一代即將進(jìn)行局部搜索的粒子。

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

4.1 參數(shù)設(shè)置

本實(shí)驗(yàn)將CPMA與其它4種PSO改進(jìn)算法(CLPSO[9], CEPSO9[14], ISPO[15], SCSPO[8])分別對(duì)19個(gè)高維測試函數(shù)集[16]和11條DNA基準(zhǔn)測序序列[17]進(jìn)行實(shí)驗(yàn)。其中，19個(gè)高維測試函數(shù)具有不同的特點(diǎn)，如單峰或高峰函數(shù)、隨著維度的增加是否更加容易被優(yōu)化等；11條DNA基準(zhǔn)測序序列來源于美國基因數(shù)據(jù)庫(GenBank)，包含了不同物種不同功能的DNA數(shù)據(jù)片段，能夠有效評(píng)估壓縮算法對(duì)含有不同特征的DNA序列的壓縮能力。我們?cè)O(shè)置各算法對(duì)19個(gè)高維測試函數(shù)分別在維度=100和=500各執(zhí)行25次，且每次執(zhí)行中函數(shù)的最大計(jì)算次數(shù)MaxFEs為5000′, 5種比較算法的參數(shù)設(shè)置如表3所示。

表3各算法的參數(shù)設(shè)置

算法參數(shù) CLPSO[9]|ps|=10, w:0.9~0.4, c=1.49445, m=8 CEPSO9[14]|ps|=10, w=0.8, c1=c2=2 ISPO[15]J=30, a=150, p=10 SCSPO[8]|ps|=10, w=0.5, c1=c2=2, M=10, N=30 CPMA|ps|=10,fs=1E-6,Vs=1E-4,T=200,cnt=100

表3中，CPMA算法中的全局搜索CLPSO參數(shù)0,1,,的設(shè)置同文獻(xiàn)[9]；實(shí)驗(yàn)中為更好地選擇進(jìn)行局部搜索的粒子，一般取f<1E-3；經(jīng)考察測試函數(shù)在迭代中各粒子的變化趨勢，發(fā)現(xiàn)連續(xù)不變或極小變化的次數(shù)一般小于1E+3所以<1E+3; CPMA算法中粒子各維速度的更新主要是在全局搜索CLPSO中進(jìn)行，到進(jìn)化中后期其值將變得非常小，V>1E-7則可改善CPMA在進(jìn)化中前期LS搜索率過低的問題；cnt的取值在1E+2左右能較好地平衡全局和局部搜索。除此之外，粒子的位置搜索范圍[min,max]設(shè)置見文獻(xiàn)[16]。

4.2 19個(gè)高維測試函數(shù)

5種PSO改進(jìn)算法在=100和=500下對(duì)19個(gè)高維測試函數(shù)的平均誤差值對(duì)比結(jié)果分別見表4和表5。做“顯著性水平”的判斷是為了說明算法之間的差異是否屬于機(jī)會(huì)變異，即是否具有統(tǒng)計(jì)上的顯著差異，由此來幫助分析算法的性能。本文顯著性水平測試是在各個(gè)函數(shù)上，將不同算法運(yùn)行25次產(chǎn)生的適應(yīng)值數(shù)據(jù)序列，進(jìn)行雙尾配對(duì)樣本t檢驗(yàn)(two-tailed paired t-test)，其中顯著性水平因子= 0.05。表4和表5中符號(hào)“?”表示統(tǒng)計(jì)顯著優(yōu)勝值，其實(shí)驗(yàn)結(jié)果值小于近似零處理。

由表4和表5數(shù)據(jù)可知，與其它4種優(yōu)化算法相比，CPMA算法在測試函數(shù)1,6,7,9～12,15,16,18和19上的平均誤差值均取得最佳結(jié)果；相對(duì)CLPSO算法，CPMA算法在大部分測試函數(shù)上都能達(dá)到較好的結(jié)果(除3,5以外)，尤其在部分函數(shù)(1,6,7,10,15和19)的優(yōu)化上達(dá)到或非常接近理論最優(yōu)值，顯示出局部搜索DACSO較好的性能，同時(shí)，在函數(shù)2,3,8,13和17上，兩個(gè)算法的優(yōu)化性能相當(dāng)；CEPSO9算法是5種改進(jìn)算法中優(yōu)化效果最差的算法，其所有的平均誤差值都遠(yuǎn)大于其它算法的優(yōu)化結(jié)果，故CEPSO9算法應(yīng)用于優(yōu)化高維多模函數(shù)時(shí)有待進(jìn)一步改進(jìn)；SCSPO算法的平均誤差值優(yōu)化結(jié)果全部優(yōu)于ISPO算法的優(yōu)化結(jié)果，這主要是因?yàn)镾CSPO算法是在ISPO算法基礎(chǔ)上添加了自適應(yīng)處理機(jī)制，從而使得高維多模函數(shù)的優(yōu)化性能得以提升。但與CPMA算法比較，在19個(gè)高維測試函數(shù)中除了2,3,8,13,14和17以外，其優(yōu)化性能都不及CPMA算法。配對(duì)t檢驗(yàn)結(jié)果表明，相對(duì)其它算法CPMA在函數(shù)1,6,7,10,15和19上是統(tǒng)計(jì)顯著的，具有統(tǒng)計(jì)學(xué)意義。

表4各算法在=100的平均誤差值優(yōu)化結(jié)果

函數(shù)CLPSOCEPSO9ISPOSCSPOCPMA F17.03E-072.60E+056.87E+027.54E-020.00E+00? F24.82E+011.51E+027.30E+013.81E-01?1.18E+02 F33.23E+021.87E+118.16E+075.00E+024.33E+03 F49.87E+011.63E+036.46E+021.20E+001.39E+00 F51.42E-05?2.52E+037.52E-012.24E-011.77E-01 F66.62E+002.11E+011.80E+012.19E+000.00E+00? F73.28E-045.51E+025.99E-106.87E-020.00E+00? F81.77E+042.18E+055.17E+047.08E-01?9.07E+04 F95.10E+011.14E+035.63E+025.82E+006.49E-01 F104.33E-051.37E+048.28E+011.96E-010.00E+00? F117.74E+011.18E+035.75E+024.98E+007.67E-01 F128.12E+002.31E+053.28E+028.17E-016.03E-03? F132.46E+021.11E+113.21E+076.35E+011.31E+02 F143.00E+011.13E+035.29E+021.84E+002.06E-01 F151.86E-044.74E+031.99E+017.34E-020.00E+00? F162.92E+011.04E+054.58E+022.13E+001.48E-02? F171.26E+027.45E+094.35E+066.91E+001.81E+02 F181.13E+015.03E+023.20E+021.64E+004.28E-01 F194.72E-051.36E+046.13E+018.84E-020.00E+00?

表5各算法在=500的平均誤差值優(yōu)化結(jié)果

函數(shù)CLPSOCEPSO9ISPOSCSPOCPMA F19.26E-022.15E+061.50E+037.15E-020.00E+00? F26.88E+012.03E+022.88E+023.96E-01?1.56E+02 F35.54E+022.49E+124.26E+071.27E+036.17E+03 F41.35E+021.04E+041.55E+031.86E+002.00E+00 F59.40E-05?1.77E+043.93E+001.79E-014.89E-01 F66.94E-022.20E+018.98E+012.02E-010.00E+00? F72.36E-032.76E+031.37E-097.27E-020.00E+00? F85.25E+046.10E+068.46E+046.73E-01?3.18e+06 F91.70E+026.30E+031.41E+035.56E+008.56E-01 F102.50E-049.94E+042.00E+021.77E-010.00E+00? F112.31E+026.30E+031.39E+035.42E+003.47E+00 F123.93E+011.92E+061.51E+037.41E-011.44E-01 F132.23E+027.42E+112.91E+071.50E+027.23E+03 F142.39E+017.99E+031.43E+031.22E+002.07E+00 F154.62E-042.21E+045.08E+018.35E-020.00E+00? F169.55E+011.09E+061.35E+032.15E+002.02E-01 F172.27E+022.59E+119.99E+068.85E+003.51E+02 F182.77E+013.27E+038.74E+021.43E+006.60E-01 F191.75E-047.64E+041.54E+021.11E-010.00E+00?

4.3 DNA基準(zhǔn)測序序列

假設(shè)5種PSO改進(jìn)算法對(duì)11條DNA基準(zhǔn)測序序列優(yōu)化碼書大小均為=8,=32，優(yōu)化時(shí)均執(zhí)行30次且MaxFEs設(shè)置為2×105。實(shí)驗(yàn)使用各算法在基準(zhǔn)測序序列上的壓縮率作為評(píng)價(jià)指標(biāo)，并與傳統(tǒng)經(jīng)典DNA序列壓縮算法(如Gencompress[2](Gen),DNAcompress[18](DNAc),DNApack[3](DNAp), GeNML[4])進(jìn)行對(duì)比，結(jié)果如表6所示。

表6表明，相對(duì)于其它壓縮算法，本文提出的CPMA算法對(duì)DNA基準(zhǔn)測序序列的壓縮率(BPB)最小。同時(shí)5種優(yōu)化算法與經(jīng)典的DNA序列數(shù)據(jù)壓縮算法相比，對(duì)DNA序列的壓縮率得到了提高，并且不同序列的壓縮效果也比較穩(wěn)定。

5 結(jié)論

本文提出一種基于Memetic算法的DNA序列數(shù)據(jù)壓縮方法，即CPMA算法。該方法采用CLPSO, DACSO的全局搜索和局部搜索相結(jié)合的Memetic算法尋找EARV碼書，然后用此碼書壓縮DNA序列數(shù)據(jù)。CPMA算法不僅對(duì)標(biāo)準(zhǔn)復(fù)合測試函數(shù)具有較好的優(yōu)化性能，而且對(duì)DNA基準(zhǔn)測序序列具有較好的壓縮率；同時(shí)，相比于經(jīng)典的DNA序列數(shù)據(jù)的壓縮算法，將優(yōu)化算法應(yīng)用于DNA序列壓縮，其壓縮性能有較大提升。

表6各算法對(duì)11條DNA基準(zhǔn)測序序列的壓縮率比較

序列GenDNAcDNApGeNMLCLPSOCEPSO9ISPOSCSPOCPMA CHNTXX1.61461.61271.61031.61021.61011.61211.61301.60091.5616 CHMPXX1.67301.67161.66021.66131.66101.69111.70891.62161.5995 MPOMTCG1.90581.89201.89321.88221.88051.89321.90211.77761.6192 HUMGHCSA1.09691.02721.03901.01241.33281.65201.64161.19211.0109 HUMHBB1.82041.78971.77711.75131.66111.80391.79021.62701.5197 HUMHSABCD1.81921.79511.73941.71321.72131.80081.80541.68281.6176 HUMDYSTROP1.92311.91161.90881.91261.90211.91121.91891.84421.7182 HUMHPRTB1.84661.81651.78861.75871.60121.78051.81241.59321.5126 VACCG1.76141.75801.75831.76491.65861.73291.74361.58331.5272 HEHCMVCG1.84701.84921.83461.83971.76391.81721.84111.66311.6059 SCCHRIII1.94861.95181.83311.94371.74371.89031.91591.59891.5388 均值1.75061.73411.71301.71371.68511.78051.79031.61681.5301

[1] Witold K. Towards cognitive analysis of DNA[C]. 2010 9th IEEE International Conference on Cognitive Informations, Beijing, 2010: 6-7.

[2] Chen X, Kwong S, and Li Ming. A compression algorithm for DNA sequences and its applications in genome comparison[C]. Proceedings of the 10th Workshop on Genome Informatics, Tokyo, 1999: 51-61.

[3] Behzadi B and Fessant F L. DNA compression challenge revisited: a dynamic programming approach[C]. Proceedings of the 16th Annual Symposium on Combinatorial Pattern Matching, Jeju Island, 2005: 190-200.

[4] Korodi G and Tabus I. An efficient normalized maximum likelihood algorithm for DNA sequence compression[J]., 2005, 23(1): 3-34.

[5] Chern B G, Ochoa I, Manolakos A,.. Reference based genome compression[C]. 2012 IEEE Information Theory Workshop, Lausanne, 2012: 427-431.

[6] 紀(jì)震, 周家銳, 朱澤軒, 等. 基于生物信息學(xué)特征的DNA序列數(shù)據(jù)壓縮算法[J]. 電子學(xué)報(bào), 2011, 39(5): 991-995.

Ji Zhen, Zhou Jia-rui, Zhu Ze-xuan,.. Bioinformatics features based DNA sequence data compression algorithm[J]., 2011, 39(5): 991-995.

[7] Kamta N M, Anupam A, Edries A,.. An efficient horizontal and vertical method for online DNA sequence compression[J]., 2010, 3(1): 39-46.

[8] Ji Zhen, Zhou Jia-rui, Zhu Ze-xuan,.. Self-configuration single particle optimizer for DNA sequence compression[J]., 2013, 17(4): 675-682.

[9] Liang J J, Qin A K, Suganthan P N,.. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J]., 2006, 10(3): 281-295.

[10] Zhu Ze-xuan, Zhou Jia-rui, Ji Zhen,.. DNA sequence compression using adaptive particle swarm optimization- based memetic algorithm[J]., 2011, 15(5): 643-658.

[11] Wang Hong-feng, Moon I K, Yang S,.. A memetic particle swarm optimization algorithm for multimodal optimization problems[J]., 2012, 197: 38-52.

[12] Li Hong-jian, Ni Bing, Wong Man-hon,.. A fast CUDA implementation of agrep algorithm for approximate nucleotide sequence matching[C]. 2011 IEEE 9th Symposium on Application Specific Processors, San Diego, 2011: 74-77.

[13] Long Min and Tan Li. A chaos-based data encryption algorithm for image/video[C]. 2010 2nd International Conference on MultiMedia and Information Technology, Kaifeng, 2010: 172-175.

[14] Bilal Alatas, Erhan Akin, and A Bedri Ozer. Chaos embedded particle swarm optimization algorithms[J]., 2009, 40(4): 1715-1734.

[15] 紀(jì)震, 周家銳, 廖惠連, 等. 智能單粒子優(yōu)化算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2010, 33(3): 556-561.

Ji Zhen, Zhou Jia-rui, Liao Hui-lian,.. A novel intelligent single particle optimizer[J]., 2010, 33(3): 556-561.

[16] Lozano M, Molina D, and Herrera F. Editorial scalability of evolutionary algorithms and other metaheuristics for large-scale continuous optimization problems[J]., 2011, 15(11): 2085-2087.

[17] Benson D A, Karch-Mizrachi I, Lipman D J,.. GenBank[J]., 2011, 39: D32-D37.

[18] Chen X, Li M, Ma B,.. DNACompress: fast and effective DNA sequence compression[J]., 2002, 18(12): 1696-1698.

譚 麗： 女，1984年生，博士生，研究方向?yàn)樯镄畔W(xué)、圖像與視頻處理、計(jì)算智能.

孫季豐： 男，1962年生，教授，博士生導(dǎo)師，研究方向?yàn)閳D像與視頻處理、自組織通信網(wǎng).

郭禮華： 男，1978年生，副教授，研究方向?yàn)閳D像理解、圖像分析、模式識(shí)別.

DNA Sequence Data Compression Method Based on Memetic Algorithm

Tan Li Sun Ji-feng Guo Li-hua

(,,510641,)

A DNA sequence compression method based on Collaborative Particle swarm optimization-based Memetic Algorithm (CPMA) is proposed. CPMA adopts the Comprehensive Learning Particle Swarm Optimization (CLPSO) as the global search and a Dynamic Adjustive Chaotic Search Operator (DACSO) as the local search respectively. In CPMA, it looks for the global optimal code book based on Extended Approximate Repeat Vector (EARV), by which the DNA sequence is compressed. Experimental results demonstrate better performance of HMPSO than the other optimization algorithms, and it is very close to the global optimization point in most of the test functions adopted by the paper. The compression performance of the method based on CPMA is markedly improved compared to many of the classical DNA sequence compression algorithms.

DNA sequence compression; Memetic algorithm; Extended Approximate Repeat Vector (EARV); Particle Swarm Optimization (PSO); Dynamic chaotic local search

中國分類號(hào)：TP391

A

1009-5896(2014)01-0121-07

10.3724/SP.J.1146.2013.00303

2013-03-12收到，2013-07-27改回

國家自然科學(xué)基金(60902087)和廣州市科委新星計(jì)劃項(xiàng)目(2010A 090100016)資助課題

譚麗 t.li07@mail.scut.edu.cn