基于小生境改進(jìn)的遺傳算法求解多序列比對(duì)問題

張繼成，羊秋玲

(1.長(zhǎng)江大學(xué)工程技術(shù)學(xué)院，湖北荊州434020；2.海南大學(xué)信息科學(xué)技術(shù)學(xué)院，海南海口570228)

ZHANG Jicheng1，YANG Qiuling2

(1.Yangtze University College of Technology & Engineering,Jingzhou 434020;2.College of Information Science & Technology,Hainan University,Haikou 570228)

?

基于小生境改進(jìn)的遺傳算法求解多序列比對(duì)問題

張繼成1，羊秋玲2

(1.長(zhǎng)江大學(xué)工程技術(shù)學(xué)院，湖北荊州434020；2.海南大學(xué)信息科學(xué)技術(shù)學(xué)院，海南?？?70228)

基于多核平臺(tái)設(shè)計(jì)了一個(gè)求解多序列比對(duì)問題的改進(jìn)遺傳算法。該算法采用一致性函數(shù)作為個(gè)體的適應(yīng)度函數(shù)，引進(jìn)小生境技術(shù)，維持種群進(jìn)化的多樣性，以改善算法的整體搜索能力?？紤]遺傳算法本身具有較好的并行性，對(duì)其各算子針對(duì)多核平臺(tái)進(jìn)行了并行化設(shè)計(jì)。通過對(duì)BAliBASE中的測(cè)試?yán)M(jìn)行測(cè)試，與已有的算法相比取得了更優(yōu)的結(jié)果，證明該算法是有效的。并行化設(shè)計(jì)使算法在多核平臺(tái)的運(yùn)行時(shí)間顯著縮短，加速效果明顯。

多序列比對(duì)；小生境遺傳算法；多核；并行

ZHANG Jicheng1，YANG Qiuling2

(1.Yangtze University College of Technology & Engineering,Jingzhou 434020;2.College of Information Science & Technology,Hainan University,Haikou 570228)

0　引言

生物序列分析的一個(gè)關(guān)鍵問題之一就是進(jìn)行多序列比對(duì)。運(yùn)用多序列比對(duì)可以發(fā)現(xiàn)序列采用何種模式，挖掘出更多的保守區(qū)域，同時(shí)也可以運(yùn)用到系統(tǒng)發(fā)育分析、結(jié)構(gòu)預(yù)測(cè)等方面。在當(dāng)前生物信息學(xué)中，眾多研究者開始研究多序列比對(duì)問題[1-4]。如果采用人工對(duì)比，則工作量相對(duì)復(fù)雜，同時(shí)也要兼顧生物序列中的功能具有不確定性，因此無法用生物意義對(duì)比對(duì)的效果進(jìn)行統(tǒng)一衡量，故人們把比對(duì)后各個(gè)序列之間差異的大小來主觀地作為衡量的標(biāo)準(zhǔn)。已有的計(jì)算差異性的數(shù)據(jù)模型主要有3種[5]：一致性函數(shù)(consensus functions)、比對(duì)和函數(shù)(sum-of-pairs functions)、樹函數(shù)(tree functions)。使用最普遍的是一致性函數(shù)，其分值一般簡(jiǎn)稱為SP值，本文亦將采用此函數(shù)作為遺傳算法的評(píng)價(jià)函數(shù)。遺傳算法作為一種高效、通用的智能算法，在優(yōu)化問題求解領(lǐng)域獲得了廣泛的應(yīng)用。而對(duì)于遺傳算法求解多序列比對(duì)問題，實(shí)現(xiàn)最完善的當(dāng)屬多序列比對(duì)軟件包SAGA[6]，它設(shè)計(jì)了22種不同的遺傳算子，并針對(duì)這些遺傳算子采取動(dòng)態(tài)調(diào)度的方案來控制它們的使用，具有較好的通用性。但由于其重點(diǎn)在于兼顧通用的效果，因此在求解性能上不甚理想，對(duì)于規(guī)模稍大的工作量則更加難以勝任。因此也出現(xiàn)了一些改進(jìn)的算法，如文獻(xiàn)[7]設(shè)計(jì)了一個(gè)基于GC-GM的多序列比對(duì)窮舉遺傳算法(簡(jiǎn)稱GC-GM-GA)，取得了一定的改進(jìn)效果。但GC-GM-GA仍然沒有克服遺傳算法的固有弱點(diǎn)，即過早收斂，這對(duì)求解質(zhì)量仍然有極大影響，并且其窮舉的策略，使算法本身復(fù)雜度增加，求解性能得不到保證。

為了提高對(duì)多序列比對(duì)問題的求解質(zhì)量，本文設(shè)計(jì)了一個(gè)基于小生境技術(shù)的改進(jìn)遺傳算法，以小生境維持種群的多樣性，達(dá)到防止算法過早收斂的目的，進(jìn)而獲得較好的求解效果。為了適應(yīng)當(dāng)前主流的多核平臺(tái)，設(shè)計(jì)了針對(duì)多核平臺(tái)的并行遺傳算法，使之有更好的執(zhí)行性能。通過對(duì)BAliBASE中的測(cè)試?yán)M(jìn)行測(cè)試，本文算法較已有算法求解質(zhì)量更高，且并行化的效果也很明顯，取得較好的加速比，從而證明算法的有效性。

1　問題描述

1.1多序列比對(duì)問題

1.2多序列比對(duì)問題優(yōu)化模型

多序列比對(duì)問題優(yōu)化模型主要用于描述多序列的差異性，如引言所述，一致性函數(shù)(consensus functions)、比對(duì)和函數(shù)(sum-of-pairs functions)、樹函數(shù)(tree functions)是最常用的3種主要用來計(jì)算差異性的數(shù)據(jù)模型。其中一致性函數(shù)會(huì)計(jì)算分值，分值的大小由當(dāng)前多序列比對(duì)M和雙序列比對(duì)庫之間有多少相同的信息來決定，而雙序列比對(duì)庫則可以通過現(xiàn)存的雙序列比對(duì)程序來產(chǎn)生，如果存在m條序列的雙序列比對(duì)庫，就不需要替代矩陣和空位罰分的選取。采用一致性函數(shù)的比對(duì)方法必須先建立雙序列比對(duì)庫，也就是m條序列的兩兩之間最佳比對(duì)結(jié)果，共有m(m-1)/2個(gè)雙序列比對(duì)。因此1個(gè)多序列比對(duì)M的一致性函數(shù)可以定義為

(1)

式中，把序列qi和qj在M中的雙序列比對(duì)記為Mij，其比對(duì)長(zhǎng)度記為L(zhǎng)ENS(Mij)，Mij與庫中qi和qj最佳比對(duì)的一致性結(jié)果記為SC(Mij)，其值的大小為對(duì)Mij中和庫中的殘基對(duì)進(jìn)行比較得出的一致性數(shù)目，序列qi和qj的相同度記為ij。假如Q的一個(gè)比對(duì)Q*滿足COST(Q*)=max(COST(M))，那么Q*為一個(gè)最優(yōu)比對(duì)，這個(gè)問題是一個(gè)NP完全問題[8]。對(duì)于這種情況，很多學(xué)者近年來都在研究用近似算法來解決多序列比對(duì)問題，也收獲了一定的成果，如文獻(xiàn)[7]設(shè)計(jì)的一個(gè)基于GC-GM的多序列比對(duì)窮舉遺傳算法。

1.3小生境技術(shù)

在生物學(xué)上，小生境的產(chǎn)生有著重要的影響，它是指在某種環(huán)境中的一種組織結(jié)構(gòu)或角色，它為新物種的產(chǎn)生創(chuàng)造了有利條件。遺傳算法中的小生境是指種群中以某種形式描述的個(gè)體間相似程度達(dá)到一定水平的個(gè)體的集合[9]。小生境常用的實(shí)現(xiàn)方法為排擠型[10]，其思想源自生物界中生物通過對(duì)有限資源的競(jìng)爭(zhēng)來獲取生存機(jī)會(huì)的現(xiàn)象。操作過程為：首先設(shè)置一排擠因子CF，在種群中隨機(jī)選取1/CF個(gè)個(gè)體用來組成排擠成員(其實(shí)大多數(shù)實(shí)現(xiàn)并非是隨機(jī)的選取個(gè)體，而是選擇按適應(yīng)度值大小降序排序后排名在前的1/CF個(gè))，其次比較排擠成員與新產(chǎn)生的個(gè)體的相似性，從而排擠掉一些適應(yīng)度值相對(duì)較小的個(gè)體。這樣種群中的個(gè)體也慢慢被分門別類，伴隨著排擠過程的進(jìn)行，一個(gè)個(gè)小的生存環(huán)境被產(chǎn)生，使種群豐富多彩。小生境的這種特性有效維持遺傳算法的多樣性，防止其過早收斂。

2　算法設(shè)計(jì)與實(shí)現(xiàn)

2.1小生境遺傳算法

遺傳算法發(fā)展較為成熟，具有穩(wěn)定的框架。本文設(shè)計(jì)算法在原有框架的基礎(chǔ)上，引進(jìn)小生境操作，在種群每次迭代后實(shí)施。為平衡小生境在遺傳算法在迭代過程中的作用，設(shè)計(jì)一個(gè)參數(shù)來控制調(diào)用小生境操作的次數(shù)。小生境遺傳算法如圖1所示。

圖1　小生境遺傳算法

基于設(shè)計(jì)的框架，針對(duì)多序列問題，算法的各算子實(shí)現(xiàn)如下：

1)種群初始化。算法個(gè)體采用二維編碼方式，通過隨機(jī)插入空位的方式改變由m條序列組成的序列組，并使各序列長(zhǎng)度均為h，m條序列分別稱為M1,M2,…,Mn，其組成了規(guī)模為n的種群。

2)選擇算子。算法采用了賭輪盤法結(jié)合精英策略選擇下一代，首先根據(jù)適應(yīng)度值排序，選取排名前10%的個(gè)體直接進(jìn)入下一代，其余個(gè)體通過賭輪盤法產(chǎn)生。

3)交叉算子。算法采用兩點(diǎn)交叉作為交叉算子，對(duì)任意的2條序列，隨機(jī)選擇序列的2點(diǎn)，然后將序列兩點(diǎn)間的基因位進(jìn)行交易。對(duì)生成的2個(gè)新個(gè)體，把適應(yīng)度值高的且與已生成的個(gè)體相異的一個(gè)個(gè)體保留下來。

4)變異算子。算法的變異算子設(shè)計(jì)為：考慮一致性函數(shù)一致性信息的目的，隨意選擇1條序列并從中選擇殘基，將此殘基對(duì)應(yīng)位置的其他殘基移到雙序列上形成新的個(gè)體。

5)評(píng)價(jià)函數(shù)。為實(shí)現(xiàn)多序列比對(duì)一致性的最大化，建立如下的評(píng)價(jià)函數(shù)：

f(M)=max(COST(M))

(2)

其意義在于f(M)的函數(shù)值越大，則多序列比對(duì)一致性越高，因此其與式(1)的目標(biāo)有著同一性。當(dāng)算法執(zhí)行結(jié)束時(shí)，則對(duì)應(yīng)了一致性最大的多序列組。

6)小生境操作。選擇操作前，按設(shè)定比例保存?zhèn)€體，并將其與變異操作后的種群合并以得到小生境操作的集合，然后計(jì)算兩兩個(gè)體間的差異性。本文中對(duì)應(yīng)2個(gè)序列不同符號(hào)個(gè)數(shù)，當(dāng)不相同符號(hào)數(shù)小于一定值時(shí)，被認(rèn)為同一小生境，此時(shí)根據(jù)適應(yīng)度值淘汰評(píng)價(jià)較差者。操作結(jié)束得到較為優(yōu)秀且差異性較大的種群，此過程不斷迭代至代數(shù)達(dá)到最大。

7)終止條件。設(shè)置1個(gè)最大迭代次數(shù)，當(dāng)算法循環(huán)的次數(shù)達(dá)到最大迭代次數(shù)則停止執(zhí)行。

2.2多核平臺(tái)算法的并行化設(shè)計(jì)

多核CPU現(xiàn)在已經(jīng)成為主流，對(duì)算法進(jìn)行多核平臺(tái)的并行化設(shè)計(jì)具有重要意義?？紤]設(shè)計(jì)的小生境遺傳算法具有良好的內(nèi)在并行性，其選擇、交叉、變異、個(gè)體評(píng)價(jià)及小生境操作均可并行計(jì)算，因此該算法非常適合在多核CPU上并行執(zhí)行。為提高計(jì)算效率，筆者將其設(shè)計(jì)成并行形式，如圖2所示。

圖2　多核平臺(tái)的并行小生境遺傳算法

3　實(shí)驗(yàn)

BAliBASE基準(zhǔn)多序列比對(duì)庫有144個(gè)，共分5類蛋白質(zhì)多序列比對(duì)測(cè)試?yán)?，該測(cè)試?yán)龓斐Ｓ糜诙嘈蛄斜葘?duì)程序的性能測(cè)試。通常衡量多序列比對(duì)程序的性能采用SPS(Sum of Pairs Score)和CS(Column Score)分值，殘基對(duì)準(zhǔn)確對(duì)齊的比率稱為SPS分值，所有序列準(zhǔn)確對(duì)齊的比率(即對(duì)齊多少列)稱為CS分值，兩者值越大則結(jié)果越優(yōu)。而為了方便比較，選擇測(cè)試用例時(shí)與文獻(xiàn)[7]一致，即在前2類中選擇前10個(gè)測(cè)試?yán)?，?類中選擇5個(gè)測(cè)試?yán)?。本文算法?biāo)記為NGA，文獻(xiàn)算法標(biāo)記為GC-GM，實(shí)驗(yàn)結(jié)果表1所示。

表1實(shí)驗(yàn)結(jié)果比較

參考比對(duì)SPS平均值CS平均值GC-GMNGAGC-GMNGARef1(10例)0.8730.8810.7980.798Ref2(10例)0.8070.8050.4650.470Ref3(5例)0.7830.7960.4850.486Ref4(5例)0.7610.7750.4980.500Ref5(5例)0.8420.8430.6980.702

從表1結(jié)果可知，NGA取得的結(jié)果除Ref2(10例)中SPS平均值略小于GC-GM外，其他的結(jié)果均優(yōu)于GC-GM。考慮遺傳算法本身具有一定隨機(jī)性，上述存在稍差的結(jié)果是可以接受的。因此總的來說，本文結(jié)果優(yōu)于文獻(xiàn)[7]的結(jié)果，這說明本文算法的有效性。

為驗(yàn)證并行化的有效性，對(duì)上述選取的測(cè)試用例分別用串行小生境遺傳算法(SNGA)與并行小生境遺傳算法(PNGA)進(jìn)行求解，并在Dell機(jī)架式服務(wù)器PowerEdge 2950 III(配置Intel Xeon E5405 CPU，四核)上執(zhí)行，對(duì)各問題分別求解5次最后時(shí)間，取平均值，最后通過加速比與效率衡量并行化的效果，結(jié)果如表2所示。

表2并行化實(shí)驗(yàn)結(jié)果

參考比對(duì)SNGA/sPNGA/s加速比效率Ref1(10例)10313033.40.85Ref2(10例)15254773.20.80Ref3(5例)8062443.30.83Ref4(5例)22156333.50.88Ref5(5例)12033653.30.83

從表2可知，算法并行化后取得了較好的加速比與計(jì)算效率，在包含4個(gè)CPU核芯的計(jì)算環(huán)境中，加速比達(dá)到了3以上，并行計(jì)算的加速效果明顯，這說明了對(duì)算法并行化設(shè)計(jì)的有效性。

4　結(jié)語

針對(duì)求解難度大的多序列比對(duì)問題，設(shè)計(jì)了一個(gè)改進(jìn)遺傳算法對(duì)其進(jìn)行求解。算法通過引進(jìn)小生境技術(shù)，維持種群進(jìn)化的多樣性，改善算法的整體搜索能力。最后通過對(duì)BAliBASE中的測(cè)試?yán)M(jìn)行測(cè)試，結(jié)果較相關(guān)文獻(xiàn)結(jié)果更優(yōu)。而考慮遺傳算法本身具有較好的并行性及當(dāng)前多核平臺(tái)的主流化，對(duì)算法進(jìn)行了并行化設(shè)計(jì)，取得較好的加速比。

[1]ATTWOOD T K,PARRY-SMITH D J.生物信息學(xué)概論[M].羅靜初，譯.北京:北京大學(xué)出版社,2002.

[2]吳璟莉,王華,梁彬彬.求解創(chuàng)建者序列重建問題的單親遺傳算法[J].計(jì)算機(jī)應(yīng)用與軟件,2012,29(10):71-74.

[3]鄒權(quán),郭茂祖,韓英鵬,等.多序列比對(duì)算法的研究進(jìn)展[J].生物信息學(xué),2010,8(4)：311-315.

[4]高峰,李防震,王珺,等.基于置換距離度量的蛋白質(zhì)多序列比對(duì)算法性能評(píng)估[J].中山大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,50(2):87-92.

[5]D GUSFIELD.Algorithms on strings,trees and sequences:computer science and computational biology[M].Cambridge:Cambridge University Press,1997.

[6]NOTREDAME C,HIGGINS D G.SAGA:Sequence alignment by genetic algorithm[J].Nucleic Acids Research,1996,24(8):1515-1524.

[7]張琎,張遠(yuǎn).基GC-GM的多序列比對(duì)窮舉遺傳算法[J].計(jì)算機(jī)應(yīng)用，2010,30(1)：146-149.

[8]WANG L,JIANG T.On the complexity of multiple sequence alignment[J].Journal of Computational Biology,1994(4):337-348.

[9]李雋穎,樓曉俊.基于小生境遺傳算法的分類優(yōu)化方法[J].計(jì)算機(jī)應(yīng)用研究，2012,29(5):1787-1790.

[10]李敏強(qiáng),寇紀(jì)淞,林丹,等.遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社,2004.

責(zé)任編輯：陳亮

An Improved Genetic Algorithm for Solving Multiple Sequence Alignment Problem Based on Niche Technology

An improved genetic algorithm based on the multi-core platform was presented for solving the multiple sequence alignment problem.The algorithm took consistency function as an individual fitness function,and introduced niche technology to maintain the diversity of population so as to improve the overall search capability of the algorithm.Considering the good parallelism of genetic algorithm,the operators were paralleled for the multi-core platform.BAliBASE test cases were used to test the algorithm,comparing with the existing algorithm.The better results showed that it was effective.Paralleling algorithm run significantly and reduced the running time on the multi-core platform with obvious acceleration effect.

multiple sequence alignment;niche genetic algorithm;multi-core;parallel

10.3969/j.issn.1671-0436.2016.04.008

2016- 07- 18

海南省重點(diǎn)研發(fā)資助項(xiàng)目(ZDYF2016153)；長(zhǎng)江大學(xué)工程技術(shù)學(xué)院基金項(xiàng)目資助(2016KY13)

張繼成(1984—)，男，碩士，講師。

TP301.6

A

1671- 0436(2016)04- 0034- 05