閆 磊,馬 健,董 輝,高 夢

(亳州職業(yè)技術(shù)學(xué)院 信息工程系,安徽 亳州 236800)

基于遺傳算法與模擬退火算法在多重DNA序列比對中的應(yīng)用研究

閆 磊,馬 健,董 輝,高 夢

(亳州職業(yè)技術(shù)學(xué)院 信息工程系,安徽 亳州 236800)

序列比對是將蛋白質(zhì)中的基因或氨基酸進行對齊的動作,目的是要找出兩序列的相似程度,而多重序列比對則是同時比對多個DNA或蛋白質(zhì)序列,找出此序列群組中最佳的比對結(jié)果.本研究結(jié)合遺傳算法及模擬退火算法,先利用遺傳算法優(yōu)化種群的概念,隨著世代演進逐漸產(chǎn)生近似最佳解,再利用模擬退火算法進行小區(qū)塊內(nèi)的比對修正.實驗結(jié)果顯示,利用遺傳算法與模擬退火算法的結(jié)合,使得遺傳算法在跳脫局部最佳解的時候能有更大空間移動,而且也讓模擬退火算法能有效解決經(jīng)由遺傳算法初步比對之后所產(chǎn)生的不良區(qū)域.兩種算法結(jié)合的序列比對結(jié)果比任何單一算法的結(jié)果好,因此可以提升整體比對效果,將來能夠為生物學(xué)家在判斷未知序列功能時提供適當?shù)膸椭?

序列比對;多重序列比對;遺傳算法;模擬退火算法

0 引言

對生物學(xué)家而言,探索蛋白質(zhì)的序列對于細胞功能的影響、推測未知蛋白序列的功能、或比較不同的兩個生物中的相似基因之間的差異時,序列的比對都成為不可或缺的一項重要技術(shù).因此近年來在生物學(xué)中,序列比對成為一項重要的技術(shù)之一,對于蛋白質(zhì)序列的比對、蛋白質(zhì)結(jié)構(gòu)的預(yù)測、DNA及MRNA的比對以及利用蛋白質(zhì)序列搜尋DNA序列等方面都具有廣泛的應(yīng)用.而由序列比對所拓展的多重序列比對,對于生物學(xué)家而言更是一項困難且具挑戰(zhàn)性的任務(wù),因為多重序列比對其計所需的時間復(fù)雜度將隨著序列數(shù)量的增加而呈指數(shù)性的成長,所以現(xiàn)在有許多算法應(yīng)用在此領(lǐng)域.

對于只有兩條序列的比對,利用動態(tài)程序規(guī)劃可以達到最好的結(jié)果.然而利用動態(tài)程序規(guī)劃算法雖然能夠得到較好的結(jié)果,但在序列數(shù)量以及長度都增加的同時,對于計算機的計算資源會急劇的提高[1].此外,過去的研究也有利用遺傳算法結(jié)合動態(tài)程序規(guī)劃的方式進行比對,但仍有許多算法在處理這種問題上具有其優(yōu)點,如模擬退火算法在處理解空間較小的問題上具有良好的表現(xiàn).本研究使用沒傳算法及模擬退火算法所結(jié)合的算法來進行比對,并且對遺傳算法以及模擬退火算法分別進行比對結(jié)果來比較,最后將模擬退火算法的概念引入遺傳算法中進行比對,使得遺傳算法在脫良局部最佳解的時候能有更大空間的移動,因此達到對比分數(shù)更高的序列比對[2].

本研究利用了遺傳算法及模擬退火算法,先進行兩者應(yīng)用于多重序列比對的結(jié)果,再利用遺傳算法輸出的結(jié)果作為模擬退火算法所需序列的基礎(chǔ)輸入序列進行比對的調(diào)整,經(jīng)過兩種算法的運算之后,希望能夠與過去專家所提出的研究能夠達到相近的結(jié)果,并且與動態(tài)程序規(guī)劃進行比對的結(jié)果能夠相近.

1 序列比對

圖1 未插入間隔于插入間隔序列比對的比較

生物序列比對是一種比較兩個或多個DNA、RNA或蛋白質(zhì)序列,并嘗試找出序列中的一連串或單一的對應(yīng)字符的方法.最常見是將兩條序列并排成兩行,將序列中相同或相似的區(qū)段置于相同的字段,而無法比對的字符則在各自的序列中利用插入間隔或產(chǎn)生錯誤.在最佳比對的情況下,插入間隔(gap)“-”可以讓序列具有更好的比對結(jié)果,而間隔的出現(xiàn)就表示在序列演化的過程中發(fā)生了刪除或插入的情況[3].如圖1(a)所示,兩個DNA序列的比對在還沒插入“-”之前,序列A與序列B具有許多的比對錯誤的部分,在圖1(b)的部分即由插入了“-”而使得整組序列達到比較好的比對結(jié)果.

1.1 全局比對

全局比對是嘗試比對在序列中的每一個元素,即其比對是從序列的最前端到序列的最末端,目的是要找出兩序列的相似程度.Needleman和Wunsch于1970年所提出的動態(tài)程序規(guī)劃是一種序列全局比對的算法,且是首次將動態(tài)程序規(guī)劃應(yīng)用于序列比對領(lǐng)域上所開發(fā)出的一種方法,如圖2(a)為全局比對[4].

1.2 區(qū)域比對

區(qū)域比對是尋找兩序列中最相似的子序列或能夠達到最高比對分數(shù)的序列片斷,其目的是找出特定的基因片段或功能序列,Smith和Waterman于1981年所提出的動態(tài)程序規(guī)劃便是一種序列區(qū)域比對的算法,如圖2(b)為區(qū)域比對.

(a)全局序列比對 (b)區(qū)域序列比對

2 算法

2.1 遺傳算法

遺傳算法(genetic algorithm)最早在1960年由Holland 所提出,直到1975年Holland所著作的“Adaptation in Natural and Artificial System”奠定了遺傳算法的基礎(chǔ).主要是利用模仿自然界中生物的演化過程作為求解問題的一種方法,通過基因的選擇、母代與子代的篩選,以及使用適應(yīng)函數(shù)來仿真達爾文進化論中物競天擇的部分.簡單來說,遺傳算法可說是一種不斷嘗試錯誤、淘汰不良母代以及選擇優(yōu)良后代的一種過程.

對于過去研究人員利用遺傳算法來進行序列比對的處理的方式,由于單純使用遺傳算法在序列比對問題常常會產(chǎn)生次最佳解,因此通常都結(jié)合了多種方法,如表1所示.利用遺傳算法解決序列比對問題的步驟包括:初始化序列、產(chǎn)生母群體并且進行競爭式選擇、進行交配、進行突變、刪除間隔字段、取代族群中的個體與結(jié)束演化等方面.

表1 應(yīng)用遺傳算法于序列比對的研究

2.2 模擬退火算法

模擬退火算法的概念是從物理學(xué)中所延伸出來,主要是指模擬固體加熱至高溫之后,其組成的結(jié)構(gòu)會變成液態(tài)結(jié)構(gòu),并且此時結(jié)構(gòu)分子的活動力較強,分子可以隨機跳動的距離也較大.隨著溫度的下降,組成的結(jié)構(gòu)分子也逐漸穩(wěn)定下來,此時可以跳動的距離也逐漸縮小,形成這個階段的熱平衡,然后重復(fù)進行降溫、結(jié)晶的動作并排列成固體狀態(tài),而最后穩(wěn)定的狀態(tài)也就是最佳解[5].此方法中最重要的部分即為溫度的調(diào)控,若溫度下降過快則可能會導(dǎo)致產(chǎn)生區(qū)域最佳解.盡管模擬退火算法對于優(yōu)化問題求解的過程較緩慢,過去仍有許多研究已經(jīng)應(yīng)用于多重序列比對的領(lǐng)域,利用模擬退火算法解決序列比對問題的步驟包括:初始化序列、適應(yīng)成本的計算、溫度及降溫的參數(shù)設(shè)定、間隔跳動.

2.3 遺傳算法與模擬退火算法結(jié)合

圖3 遺傳算法與模擬退火算法結(jié)合流程圖

由于遺傳算法的求解過程中需要產(chǎn)生挑選可用的母代族群,且族群數(shù)量也是進行遺傳算法時必須的參數(shù),而模擬退火算法則是比較更新前與更新后彼此狀態(tài)的成本差異,就產(chǎn)出的解數(shù)量來說,遺傳算法的族群中每個染色體都代表著一個解,而模擬退火算法每次針對一個解進行修正.因此在結(jié)合這兩種算法時,本研究先利用遺傳算法產(chǎn)出模擬退火算法所需的初始序列,接著進行模擬退火算法中的移動方法來尋找是否有表現(xiàn)更好的解存在[6].圖3為結(jié)合兩種算法之后的比對流程.

3 實驗結(jié)果與分析

3.1 實驗資料來源

本研究采用某生物信息中心的部分數(shù)據(jù),在收集的數(shù)據(jù)資料中選取8個數(shù)據(jù)集,為了整理出與過去文獻中所提到不同的間隔插入方式,先進行序列之間彼此差異程度的計算,方法是計算數(shù)據(jù)集中各個序列中四種字符的總數(shù)以及最大差距,并且利用最長與最短序列的差距來計算出所需插入間隔的數(shù)量,各個數(shù)據(jù)集的差距如表3.利用表2中的序列資料及表3的序列內(nèi)容分析,可以發(fā)現(xiàn)部分的數(shù)據(jù)集中如S3、S7,各個序列之間字符的彼此差距數(shù)量并無非常明顯,且數(shù)據(jù)集中最長序列減去最短序列的差距也相差不多,因此本研究在實驗設(shè)計中加入了由此兩項數(shù)值所計算出的間隔插入數(shù)量.

表2 DNA序列原始數(shù)據(jù)

表3 各個序列的字符差距最大數(shù)目與平均差距

續(xù)表3

注:表3中A,T,G,C表示堿基

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

進行遺傳算法以及模擬退火算法時,其中的參數(shù)設(shè)定將會影響到多重序列比對的結(jié)果.因此在此階段先將各個算法所需的參數(shù)做分組配置,作為實驗的分組依據(jù),同時并參考了過去的文獻作為參數(shù)設(shè)定的依據(jù).表4為遺傳算法所需各種參數(shù)如族群大小、交配率、各個突變操作數(shù)的突變率及矩陣延伸長度的設(shè)定,其中Max代表序列群組中長度最長的序列,Min代表序列群組中長度最短之序列, extension代表整個序列群組中四種字元最大最小值的差異,利用表3中的數(shù)據(jù)計算所得.表5為模擬退火算法中接受率、初始溫度、凝固溫度以及降溫參數(shù)的設(shè)定.

表4 遺傳算法數(shù)設(shè)定

表5 模擬退火算法參數(shù)設(shè)定

3.3 實驗結(jié)果與分析

(1)遺傳算法與動態(tài)規(guī)劃算法預(yù)測結(jié)果分析

通過上面算法的分析,本文先使用遺傳算法與動態(tài)規(guī)劃算法組合對DNA多重序列進行比對.首先設(shè)置遺傳算法參數(shù),利用交叉操作產(chǎn)生實驗數(shù)據(jù),再利用動態(tài)規(guī)劃算法對遺傳算法進行優(yōu)化,在較小范圍隨機產(chǎn)生組態(tài),并對每一組進行優(yōu)化,提高對DNA序列比對的效率,如表6所示.

表6 遺傳算法與動態(tài)規(guī)劃算法DNA序列預(yù)測結(jié)果

(2)遺傳模擬退火算法對DNA序列比對分析

本研究首先使用遺傳算法進行多重序列比對,利用表4中的參數(shù)設(shè)定,各個組態(tài)分別利用交叉參數(shù)設(shè)置產(chǎn)生實驗組別,共產(chǎn)生 27個實驗組態(tài),并選取S2對每個組別各進行五次之后得出最佳的參數(shù)設(shè)置.利用此參數(shù)進行8次實驗且比較之后所得出的最佳配對分數(shù)、平均配對分數(shù)以及平均比對時間,具體如表7所示.而由此結(jié)果得到在本研究的流程中,對于遺傳算法最佳參數(shù)設(shè)計分別是:交配率為80%、突變率為20%、族群大小為20條、世代數(shù)量為15,000代以及矩陣延伸長度為Max×1.

表7 遺傳算法的多重序列比對結(jié)果

接著第二階段進行本研究所使用的模擬退火算法進行多重序列比對,利用表5的參數(shù)設(shè)定,各個組態(tài)分別采取交叉參數(shù)設(shè)置產(chǎn)生實驗組別,并利用數(shù)據(jù)集S1進行8次實驗后得出的最佳參數(shù)設(shè)置,且用此參數(shù)對各數(shù)據(jù)集進行五次實驗之后所得出的最佳配對分數(shù)、平均配對分數(shù)以及比對時間，具體如表8所示.由此表得到的模擬退火算法最佳參數(shù)設(shè)計分別是初始溫度為100℃,降溫參數(shù)為 3℃,接受率為80%.

表8 模擬退火算法的多重序列比對結(jié)果

兩種算法演算完之后,接著進行第三階段的流程.利用遺傳算法進行比對所得到的解序列作為下一個模擬退火算法流程中所需的初始序列,并改變第二階段模擬退火算法中間隔跳動操作數(shù)作用的位置與范圍,而其參數(shù)設(shè)定分別采用遺傳算法以及模擬退火算法的最佳參數(shù)設(shè)置,其整體的比對結(jié)果如表9所示.

表9 遺傳算法結(jié)合模擬退火算法的多重序列比對結(jié)果

總之,通過兩種算法對DNA序列比對的實驗結(jié)果表明,本研究利用遺傳算法與模擬退火算法結(jié)合在多重序列比對上能夠達到不錯的修正結(jié)果,在數(shù)據(jù)集S1與S5中甚至能夠達到相當?shù)谋葘Y(jié)果.在遺傳算法中所必須被設(shè)定的各項信息,如間隔插入數(shù)量、突變率以及交配率等,都與產(chǎn)出的結(jié)果相關(guān),若能夠加強在遺傳算法中各個操作數(shù)的使用方法以及執(zhí)行程序,對于近似最佳解的收斂將具有相當程度的改善.

4 結(jié) 語

本研究利用遺傳算法的物競天擇的概念,隨著世代演進所逐漸產(chǎn)生的近似最佳解,接著再利用模擬退火算法進行小區(qū)塊內(nèi)的比對修正.實驗結(jié)果表明,利用遺傳算法與模擬退火算法的結(jié)合,其比對結(jié)果都比任何單一算法的結(jié)果好,通過結(jié)合也可讓模擬退火算法有效的解決經(jīng)由遺傳算法初步比對之后所產(chǎn)生的不良區(qū)域,進而修正且更進一步提升整體比對的效果.

[1]朱彥廷.用遺傳算法求最小生成樹[J].瓊州學(xué)院學(xué)報,2012,19(2):32-35.

[2]馬健.決策樹算法對電子商務(wù)交易信任機制的應(yīng)用研究[J].河北北方學(xué)院學(xué)報,2015,31(5):36-39.

[3]張冰龍,徐建敏,江浩.基于模擬退火的DNA遺傳優(yōu)化小波多模盲均衡算法[J].電子技術(shù)應(yīng)用,2016, 42(2):88- 91.

[4]李志亮,羅芳.基于初始值優(yōu)化的灰色馬爾科夫鏈預(yù)測模型研究[J].海南熱帶海洋學(xué)院學(xué)報,2016,23(5):55 -59.

[5]崔光照,李小廣,張勛才,等.基于改進的粒子群遺傳算法的DNA編碼序列優(yōu)化[J].計算機學(xué)報, 2010, 33(2):311-316.

[6]王哲河,林越,張僑.Dijkstra算法在三亞旅游線路規(guī)劃中的應(yīng)用[J].瓊州學(xué)院學(xué)報,2015,22(5):98-102.

(編校：曾福庚)

Application of Genetic Algorithm and SimulatedAnnealing Algorithm in Multiple DNA Sequences

YAN Lei, MA Jian, DONG Hui, GAO Meng

(Department of Information Engineering, Bozhou Vocational and Technical College, Bozhou Anhui 236800, China)

The goal of sequence alignment—the alignment of genes or amino acids in proteins—is to uncover the similarity of two sequences.However, multiple sequence alignment is the comparison between multiple DNA sequences or protein sequences in order to discover the optimal comparing between the sequences groups.In the current study, genetic algorithm and simulated annealing methods were used to optimize the population concept by genetic algorithm.With the generation evolution, the approximate optimal solution was gradually generated.The experimental results show that the combination of genetic algorithm and simulated annealing methods enables the genetic algorithm to have more space to move when the local optimal solution is obtained, and the simulated annealing method can effectively solve the genetic algorithm for the bad regions.The combination of the two algorithms is better than the results of any single algorithm, so it can improve the overall alignment effect and will provide the biologist with appropriate help in judging the unknown sequence function in the future.

sequence alignment; multiple sequence alignment; genetic algorithm; simulated annealing method

格式：閆磊,馬健,董輝,等.基于遺傳算法與模擬退火算法在多重DNA序列比對中的應(yīng)用研究[J].海南熱帶海洋學(xué)院學(xué)報,2017，24(2)：64-69.

2017-02-15

安徽省教育廳自然科學(xué)研究重點課題(KJ2016A493);安徽省亳州市產(chǎn)業(yè)創(chuàng)新團隊科研項目(亳組[2015]20號-2);亳州職業(yè)技術(shù)學(xué)院院級課題 (BYK1511)

閆磊(1984-),男,回族,安徽亳州人,亳州職業(yè)技術(shù)學(xué)院信息工程系助教,研究方向為數(shù)據(jù)挖掘、人工智能方向.

TP18

A

2096-3122(2017) 02-0064-06

10.13307/j.issn.2096-3122.2017.02.13