基于遺傳算法的DNA序列聚類可靠性評(píng)估

孫 杰, 李 重

(浙江理工大學(xué)理學(xué)院，杭州 310018)

?

基于遺傳算法的DNA序列聚類可靠性評(píng)估

孫 杰, 李 重

(浙江理工大學(xué)理學(xué)院，杭州 310018)

聚類分析是分子生物學(xué)家推斷同源序列進(jìn)化關(guān)系的常用技術(shù),評(píng)估聚類的可靠性是聚類分析的重要內(nèi)容。Bootstrap是評(píng)估聚類可靠性的一種統(tǒng)計(jì)方法，它替換DNA序列的所有核苷酸堿基以進(jìn)行采樣分析。在Bootstrap方法的基礎(chǔ)上，提出了一種評(píng)估DNA序列聚類可靠性的改進(jìn)方法。該方法首先按照一定比例隨機(jī)抽取原始DNA序列的部分堿基，然后對(duì)抽取的每個(gè)堿基利用遺傳算法進(jìn)行替換。提出的方法考慮了堿基之間的相關(guān)性，得到的樣本更接近于原始序列，且更符合生物漸進(jìn)進(jìn)化的結(jié)果。使用該方法對(duì)DNA序列聚類構(gòu)建的進(jìn)化樹進(jìn)行可靠性評(píng)估。實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)可靠性評(píng)估的準(zhǔn)確率得到了提高，表明該方法可行、有效。

DNA序列；聚類分析；進(jìn)化樹；Bootstrap；可靠性

0 引 言

序列比對(duì)[1]通過(guò)排列DNA、RNA或蛋白質(zhì)序列的方式，識(shí)別可以描述序列間的功能、結(jié)構(gòu)以及進(jìn)化關(guān)系的相似序列區(qū)域[2]。它一般決定了許多生物信息學(xué)技術(shù)及程序的分析結(jié)果[3]，影響著很多序列比較研究的結(jié)論和生物解釋，是DNA聚類分析等研究中的一個(gè)重要內(nèi)容。

隨著基因數(shù)量的增加，對(duì)它們進(jìn)行有效分析變得更加困難，而聚類分析是解決這一問(wèn)題的實(shí)用方法。聚類分析能夠有效處理基因表達(dá)數(shù)據(jù)，是生物多樣性研究經(jīng)常用到的一種方法。在DNA聚類分析中，聚類是把相似序列以靜態(tài)分類的方法劃分入不同的組中，使得組內(nèi)的序列比不同組中的更相近。通常，聚類方法可以分為劃分聚類[4]和層次聚類[5]。劃分聚類方法根據(jù)一些優(yōu)化準(zhǔn)則將數(shù)據(jù)分成M(通常是預(yù)先設(shè)定的值)組。k-means以及k-medoids方法是劃分聚類中比較典型的方法。層次聚類算法通過(guò)構(gòu)建一個(gè)嵌套聚類的分層集合實(shí)現(xiàn)聚類。在分層集合中最頂層的類包含所有的數(shù)據(jù)對(duì)象，而最底層的類只包含單個(gè)的數(shù)據(jù)對(duì)象[6]。層次聚類通過(guò)在層次結(jié)構(gòu)的每個(gè)層級(jí)上顯示合并的兩個(gè)集群，同時(shí)顯示集群之間的距離，提供了一種自然的形式來(lái)圖形化表示數(shù)據(jù)集。

聚類可靠性(也稱確定性或穩(wěn)定性)用于描述聚類分析的置信度。如何衡量?jī)蓚€(gè)聚類的相似度是評(píng)估聚類可靠性的關(guān)鍵內(nèi)容。Bootstrap是由Felsenstein[7]引入的一種評(píng)估聚類可靠性的方法，現(xiàn)已被生物學(xué)家廣泛接受和使用。該方法是一種非參數(shù)統(tǒng)計(jì)方法，用于評(píng)估統(tǒng)計(jì)估計(jì)的準(zhǔn)確性。Bootstrap通過(guò)垂直替換的方式獲得樣本，可以模擬生物進(jìn)化過(guò)程中序列堿基的置換、插入和刪除，它對(duì)分子序列的一般做法是重采樣整個(gè)序列[8]。通過(guò)執(zhí)行Bootstrap得到的聚類可靠性通常以百分比的形式顯示在樹狀圖中[9]。另外，在聚類可靠性評(píng)估中，還有一些基于Bootstrap的改進(jìn)方法，如Block Bootstrap方法[10]、Subsampling Bootstrap方法等。

本文提出了一種評(píng)估DNA序列聚類可靠性的方法。該方法在標(biāo)準(zhǔn)Bootstrap方法的基礎(chǔ)上，進(jìn)行了如下改進(jìn)：按照一定的比率在DNA序列中抽取堿基數(shù)據(jù)；對(duì)抽取的每個(gè)堿基構(gòu)建一定長(zhǎng)度的堿基窗口并應(yīng)用遺傳算法對(duì)堿基進(jìn)行置換。本文采用該方法對(duì)不同物種(beta-globulin DNA sequences, H5N1，H5N2)的DNA序列聚類進(jìn)行可靠性評(píng)估實(shí)驗(yàn)，以驗(yàn)證該方法的有效性。

1 方法設(shè)計(jì)

1.1 序列相似性分析

從比對(duì)序列數(shù)目的角度看，序列比對(duì)可劃分為兩類：雙序列比對(duì)和多序列比對(duì)。雙序列比對(duì)通常以動(dòng)態(tài)規(guī)劃算法為理論基礎(chǔ)。一般動(dòng)態(tài)規(guī)劃算法可以擴(kuò)展到多于兩個(gè)序列的情況，但是隨著核酸數(shù)據(jù)的增長(zhǎng)，基于動(dòng)態(tài)規(guī)劃的多序列比對(duì)問(wèn)題就會(huì)變得非常復(fù)雜，這時(shí)基于SP(逐對(duì)加和)比對(duì)模型的多序列比對(duì)就成了一個(gè)NP問(wèn)題[11]。對(duì)多序列比對(duì)問(wèn)題的研究仍然是一個(gè)具有挑戰(zhàn)性的任務(wù)。啟發(fā)式算法是當(dāng)前大部分多序列比對(duì)所采用的算法。迭代比對(duì)和漸進(jìn)比對(duì)是兩種典型的基于啟發(fā)式算法的多序列比對(duì)方法。

迭代比對(duì)算法以迭代方式優(yōu)化多序列比對(duì)，逐步改進(jìn)比對(duì)結(jié)果，直至不能獲得更合理的比對(duì)結(jié)果。根據(jù)改進(jìn)策略，迭代比對(duì)算法可以劃分為確定型和隨機(jī)型兩種，其中確定型算法[12]最簡(jiǎn)單。Prrp[13]、隱馬爾可夫模型(HMM)[14]、模擬退火[15]以及遺傳算法[16]等是隨機(jī)迭代算法中的典型方法。漸進(jìn)比對(duì)算法根據(jù)序列間由近及遠(yuǎn)的進(jìn)化關(guān)系，用雙序列比對(duì)算法對(duì)序列或子比對(duì)結(jié)果進(jìn)行比對(duì)，重復(fù)這一過(guò)程直至所有序列都得到比對(duì)。它的優(yōu)點(diǎn)是所需時(shí)間較短、所占內(nèi)存較少[17]。T-Coffee[18]和ClustalW[19]等是基于漸進(jìn)比對(duì)算法并被廣泛使用的多序列比對(duì)算法，其中使用最廣的是ClustalW算法。

本文通過(guò)軟件包MEGA用ClustalW算法先對(duì)DNA序列間的相似性進(jìn)行了分析，然后使用適當(dāng)?shù)亩攘繕?biāo)準(zhǔn)計(jì)算得到了DNA序列之間的距離矩陣。

1.2 Bootstrap改進(jìn)方法

在得到不同物種DNA序列間的距離矩陣后，本文對(duì)DNA序列進(jìn)行聚類分析，并通過(guò)相應(yīng)樹狀圖(進(jìn)化樹)直觀地將進(jìn)化關(guān)系顯現(xiàn)出來(lái)。本文使用層次聚類中非加權(quán)組平均法(unweighted pair-group method with arithmetic mean,UPGMA)進(jìn)行聚類，利用Bootstrap方法對(duì)構(gòu)建的進(jìn)化樹的可靠性進(jìn)行評(píng)估檢驗(yàn)。

標(biāo)準(zhǔn)Bootstrap方法直接應(yīng)用在生物序列聚類可靠性評(píng)估中存在兩個(gè)缺點(diǎn)[20]。

首先，標(biāo)準(zhǔn)Bootstrap通過(guò)替換原始序列的所有核苷酸堿基得到新的樣本，它假設(shè)這樣得到的所有樣本是等可能的。但是生物進(jìn)化過(guò)程是漸進(jìn)的，即進(jìn)化后的DNA序列更接近于原始序列，因此標(biāo)準(zhǔn)的Bootstrap方法并不適合模擬DNA序列的進(jìn)化過(guò)程。為了改善這一缺陷，Zhang等[6]提出了Subset Bootstrap方法：首先在原始數(shù)據(jù)矩陣中按設(shè)定比例隨機(jī)抽取列(記錄這些列的位置)的子集；然后，對(duì)抽取的列的子集應(yīng)用標(biāo)準(zhǔn)的Bootstrap方法；最后將變化后的子集插回到原始數(shù)據(jù)矩陣中。插回的位置對(duì)應(yīng)從原始數(shù)據(jù)矩陣中抽取時(shí)的位置，這樣得到的新數(shù)據(jù)矩陣就是一個(gè)Subset Bootstrap樣本。實(shí)際上Subset Bootstrap方法是通過(guò)在原始DNA序列中隨機(jī)替換部分核苷酸堿基來(lái)實(shí)現(xiàn)生物進(jìn)化模擬的，但是它忽略了一條DNA序列中核苷酸堿基之間的相關(guān)性。

其次，標(biāo)準(zhǔn)Bootstrap方法假設(shè)DNA序列之間的核苷酸堿基相互獨(dú)立[8]。在生物信息學(xué)中，一個(gè)普遍規(guī)律是序列決定結(jié)構(gòu)，結(jié)構(gòu)決定功能。因此在序列中堿基間的排列關(guān)系對(duì)生物信息具有一定的影響。所以，假設(shè)一條DNA序列的核苷酸堿基之間具有獨(dú)立性存在問(wèn)題。Bootstrap在相關(guān)型數(shù)據(jù)上的應(yīng)用是一個(gè)熱點(diǎn)研究領(lǐng)域，這一領(lǐng)域的常用方法是Subsampling以及Block Bootstrap方法。Subsampling方法從原始序列隨機(jī)選取一定長(zhǎng)度的連續(xù)片段作為新樣本。它具有相當(dāng)普遍的實(shí)用性，但缺點(diǎn)是收斂速度較差[20]，并且樣本長(zhǎng)度小于原始序列長(zhǎng)度。Block Bootstrap方法生成一個(gè)Block(連續(xù)序列片段)集合，每次從Block集合中隨機(jī)選擇一個(gè)Block替換原始序列中的部分片段。該方法對(duì)相關(guān)型數(shù)據(jù)很有用，但缺點(diǎn)是沒(méi)有改變Block中的堿基。

由以上分析可知，Subsampling和Block Bootstrap都不是合適的重采樣方法。

為了更合理地模擬自然進(jìn)化，本文在進(jìn)行重采樣時(shí)僅改變?cè)糄NA序列中一定比例的堿基，并且在置換堿基時(shí)將其臨近堿基序列考慮進(jìn)來(lái)。另外，本文在置換堿基時(shí)引入自然進(jìn)化準(zhǔn)則，使用遺傳算法(genetic algorithm)模擬具有相關(guān)性堿基之間的變化過(guò)程。在模擬過(guò)程中，本文首先以某一待置換堿基為中心構(gòu)建堿基窗口(一定長(zhǎng)度的堿基序列)；然后對(duì)該堿基窗口應(yīng)用遺傳算法的選擇、交叉和變異運(yùn)算，以模擬生物序列的自然進(jìn)化；最后對(duì)遺傳運(yùn)算結(jié)束后的堿基窗口依據(jù)適當(dāng)原則選出堿基，以替換原始序列中的堿基。具體過(guò)程如下：

a) 計(jì)算采樣比例：計(jì)算DNA序列兩兩之間的進(jìn)化率(對(duì)齊的兩序列不同堿基總數(shù)與序列長(zhǎng)度的比值，長(zhǎng)度不同時(shí)取短序列長(zhǎng)度作為分母)Rij(i=1,2, …,n-1,j=i+1, …,n,n為序列的總數(shù))，并計(jì)算Rij的平均值。本文取平均進(jìn)化率作為采樣比例。

b) 按照采樣比例，從每條DNA序列中選取不同列的堿基。對(duì)選出的每個(gè)堿基構(gòu)造堿基窗口，利用遺傳算法置換這個(gè)堿基。具體操作如下：

b1) 對(duì)于從一條DNA序列中選出的每個(gè)堿基，構(gòu)造堿基窗口W(左右各擴(kuò)展一定個(gè)數(shù)堿基的連續(xù)序列片段)。從除W所在序列以外的每條序列中選出與W相似度(堿基窗口對(duì)齊后相同堿基的總數(shù))最大的堿基窗口Wi(i=1, …,n-1)。將選出的n-1個(gè)堿基窗口作為遺傳算法的初始種群。

b2) 對(duì)初始種群執(zhí)行“選擇”運(yùn)算：設(shè)W所在序列與剩余序列的相似度總和為sum,與剩余序列中第i條序列的相似度為Si(i=1, …,n-1)。將比值Si/sum作為第i條序列中選出的窗口在初始種群中被選擇的概率。“選擇”運(yùn)算選出的新種群與初始種群個(gè)數(shù)相同。

b3) 對(duì)選出的新種群進(jìn)行“交叉”運(yùn)算：在進(jìn)行“交叉”之前要對(duì)堿基窗口進(jìn)行編碼。由于核苷酸堿基的種類只有A、T、G、C 4種，所以只需要2位二進(jìn)制數(shù)即可對(duì)一個(gè)堿基編碼。這樣A、T、G、C可編碼為00、01、10、11。

“交叉”是根據(jù)某一概率對(duì)隨機(jī)配對(duì)的種群進(jìn)行的。若堿基窗口長(zhǎng)度為L(zhǎng)，則編碼序列長(zhǎng)度為2L。令編碼序列兩個(gè)相鄰堿基之間的位置為位點(diǎn)，則長(zhǎng)為2L的編碼序列有2L-1個(gè)位點(diǎn)。交叉位點(diǎn)可從1, …,2L-1中隨機(jī)選取。本文采用單點(diǎn)交叉的方法進(jìn)行交叉，即交換配對(duì)的編碼序列交叉位點(diǎn)之后的二進(jìn)制數(shù)據(jù)。

b4) 對(duì)“交叉”后的編碼序列進(jìn)行“變異”運(yùn)算：“變異”運(yùn)算根據(jù)某一變異概率進(jìn)行。對(duì)于長(zhǎng)為2L的編碼序列，它的每個(gè)位置都有突變的可能，所以突變位點(diǎn)可從1, …,2L中隨機(jī)選取。選出突變位點(diǎn)后將該位點(diǎn)的編碼數(shù)值取反。

b5) 對(duì)數(shù)據(jù)解碼，將編碼序列恢復(fù)為堿基序列。循環(huán)執(zhí)行步驟b2)，b3)，b4)。將最終得到的堿基窗口保存。

比較式(1)的計(jì)算結(jié)果與堿基編碼轉(zhuǎn)換成的4個(gè)十進(jìn)制數(shù)值，選出最接近計(jì)算結(jié)果的十進(jìn)制數(shù)值所對(duì)應(yīng)的堿基。將所選的堿基替換W中心位置所對(duì)應(yīng)的原始序列中的堿基。這樣變換得到一個(gè)新的DNA序列樣本。

(1)

其中：Vi為執(zhí)行遺傳運(yùn)算后Wi中心位置堿基對(duì)應(yīng)編碼轉(zhuǎn)換成的十進(jìn)制數(shù)值。

c) 通過(guò)序列比對(duì)結(jié)果計(jì)算出相似距離矩陣。

d) 根據(jù)產(chǎn)生的相似距離矩陣進(jìn)行聚類分析，并構(gòu)建進(jìn)化樹。

改進(jìn)Bootstrap方法的主要流程如圖1所示。

圖1 改進(jìn)的Bootstrap方法流程

1.3 聚類可靠性計(jì)算

本文在Bootstrap采樣過(guò)程中，每次都對(duì)采樣數(shù)據(jù)進(jìn)行重新聚類并構(gòu)建進(jìn)化樹。進(jìn)化樹的每個(gè)分支用DNA序列的子集表示。若采樣總次數(shù)為S，某子集重復(fù)出現(xiàn)的次數(shù)為t，則比值t/S為該子集在統(tǒng)計(jì)檢驗(yàn)中的有效性。具體來(lái)說(shuō)，用Zi=(Zi1,Zi2, …,Zig)表示進(jìn)化樹中某一分支包含的DNA序列的子集，其中i= 1, …,m,m為聚類形成的進(jìn)化樹所包含的總分支數(shù)，g為DNA序列總數(shù)，Zi1,Zi2, …,Zig對(duì)應(yīng)數(shù)據(jù)集中按序排列的DNA序列。Zig取值為0和1，0表示第i個(gè)子集中不包含第g條DNA序列， 1表示包含。用相同方法對(duì)原始數(shù)據(jù)集聚類并構(gòu)建進(jìn)化樹，并用同樣的方式進(jìn)行表示。將采樣數(shù)據(jù)與原始數(shù)據(jù)的集合表示進(jìn)行比對(duì)，若有相同的分支出現(xiàn)，則將該分支對(duì)應(yīng)的重復(fù)次數(shù)加1。在S次Bootstrap采樣并重新聚類的過(guò)程中，記子集Zi出現(xiàn)的次數(shù)為t，則比值t/S可以表示進(jìn)化樹中第i條分支有效性的統(tǒng)計(jì)檢驗(yàn)結(jié)果，即該分支的聚類可靠性。

2 結(jié)果和討論

本文對(duì)給定的DNA序列分別應(yīng)用標(biāo)準(zhǔn)Bootstrap、SubsetBootstrap以及本文方法進(jìn)行了實(shí)驗(yàn)，并且對(duì)比了實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)中所用序列數(shù)據(jù)從NCBI網(wǎng)站[http://www.ncbi.nlm.nih.gov/]上選取。本文對(duì)3組實(shí)驗(yàn)數(shù)據(jù)進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)1選取了8個(gè)物種的β-球蛋白基因的第一個(gè)外顯子(Exon)，如表1所示，數(shù)據(jù)中各物種對(duì)應(yīng)序列所含堿基個(gè)數(shù)介于86～105之間。為了完整地顯示實(shí)驗(yàn)結(jié)果以及方便地評(píng)估聚類可靠性，實(shí)驗(yàn)數(shù)據(jù)2從109個(gè)H5N1病毒的HA(hemagglutinin)基因序列[6]中挑選了11個(gè)序列。所選序列的長(zhǎng)度和序列碼如表2所示。實(shí)驗(yàn)數(shù)據(jù)3是挑選自H5N2病毒的29條HA基因序列。所選序列的長(zhǎng)度和序列碼如表3所示。

表1 8個(gè)物種的β-球蛋白基因的第一個(gè)外顯子(Exon)序列

表2 11個(gè)H5N1病毒的HA基因序列

表3 29個(gè)H5N2病毒的HA基因序列

本文利用Mega軟件，首先使用UPGMA方法對(duì)基于ClustalW得到的距離矩陣構(gòu)建了進(jìn)化樹，然后用3種不同Bootstrap方法計(jì)算了聚類可靠性，并對(duì)可靠性結(jié)果進(jìn)行了比較。圖2(a)、圖3(a)為分別對(duì)實(shí)驗(yàn)數(shù)據(jù)1和2應(yīng)用標(biāo)準(zhǔn)的Bootstrap方法構(gòu)建的進(jìn)化樹。圖2(b)、圖3(b)分別為對(duì)實(shí)驗(yàn)數(shù)據(jù)1和2使用Subset Bootstrap方法構(gòu)建的進(jìn)化樹。圖2(c)、圖3(c)分別為對(duì)實(shí)驗(yàn)數(shù)據(jù)1和2使用本文提出方法得到的進(jìn)化樹。圖4為對(duì)實(shí)驗(yàn)數(shù)據(jù)3使用本文提出方法得到的進(jìn)化樹。表4比較了不同Bootstrap方法得到的聚類可靠性平均值。由表4可以看出，本文方法所得可靠性結(jié)果優(yōu)于標(biāo)準(zhǔn)Bootstrap方法和Subset Bootstrap方法。

(a) 標(biāo)準(zhǔn)Bootstrap方法

(b) Subset Bootstrap方法

(c) 本文方法圖2 3種不同方法對(duì)8個(gè)物種的聚類可靠性結(jié)果

(a) 標(biāo)準(zhǔn)Bootstrap方法

(b) Subset Bootstrap方法

(c) 本文方法圖3 3種不同方法對(duì)11個(gè)H5N1病毒的HA基因序列的聚類可靠性結(jié)果

圖4 對(duì)29個(gè)H5N2病毒的HA基因序列使用本文方法得到的聚類可靠性結(jié)果

方法可靠性平均值實(shí)驗(yàn)數(shù)據(jù)1實(shí)驗(yàn)數(shù)據(jù)2實(shí)驗(yàn)數(shù)據(jù)3本文方法98.00097.87597.769SubsetBootstrap93.00094.75095.885標(biāo)準(zhǔn)Bootstrap84.00090.75093.231

3 結(jié) 語(yǔ)

本文首先利用多序列比對(duì)方法分析DNA序列之間的相似性，并構(gòu)造相似距離矩陣；然后在相似距離矩陣基礎(chǔ)上用UPGMA進(jìn)行聚類，同時(shí)構(gòu)建進(jìn)化樹顯示聚類結(jié)果；最后使用基于遺傳算法的改進(jìn)評(píng)估方法對(duì)聚類結(jié)果進(jìn)行可靠性分析。本文對(duì)給出的3組DNA數(shù)據(jù)用相同聚類方法構(gòu)建進(jìn)化樹，并用標(biāo)準(zhǔn)Bootstrap、Subset-Bootstrap和本文方法對(duì)每組數(shù)據(jù)構(gòu)建的進(jìn)化樹進(jìn)行了可靠性評(píng)估。實(shí)驗(yàn)結(jié)果表明，本文提出的方法優(yōu)于標(biāo)準(zhǔn)Bootstrap方法和Subset-Bootstrap方法。

[1] BLACKBURNE B P, WHELAN S. Class of multiple sequence alignment algorithm affects genomic analysis[J]. Molecular Biology and Evolution, 2013, 30(3): 642-653.

[2] VIJAYAKUMAR S, BHARGAVI A, PRASEEDA U, et al. Optimizing sequence alignment in cloud using hadoop and mpp database[C]//Cloud Computing (CLOUD), 2012 IEEE 5th International Conference on. IEEE, 2012: 819-827.

[3] KEMENA C, NOTREDAME C. Upcoming challenges for multiple sequence alignment methods in the high-throughput era[J]. Bioinformatics, 2009, 25(19): 2455-2465.

[4] JAIN A K, MURTY M N, FLYNN P J. Data clustering: a review[J]. ACM Computing Surveys (CSUR), 1999, 31(3): 264-323.

[5] CILIBRASI R L, VITáNYI P M B. A fast quartet tree heuristic for hierarchical clustering[J]. Pattern Recognition, 2011, 44(3): 662-677.

[6] ZHANG S, LI Z, BELAND K, et al. Model-based clustering with certainty estimation: implication for clade assignment of influenza viruses[J]. BMC Bioinformatics, 2016, 17(1): 287-296.

[7] FELSENSTEIN J. Confidence limits on phylogenies: an approach using the bootstrap[J]. Evolution, 1985,39(4): 783-791.

[8] EFRON B, HALLORAN E, HOLMES S. Bootstrap confidence levels for phylogenetic trees[J]. Proceedings of the National Academy of Sciences, 1996, 93(23): 13429-13429.

[9] TEKLEWOLD A, BECKER H C. Geographic pattern of genetic diversity among 43 Ethiopian mustard (Brassica carinata A. Braun) accessions as revealed by RAPD analysis[J]. Genetic Resources and Crop Evolution, 2006, 53(6): 1173-1185.

[10] KREISS J P, PAPARODITIS E. Bootstrap methods for dependent data: A review[J]. Journal of the Korean Statistical Society, 2011, 40(4): 357-378.

[11] APOSTOLICO A, GIANCARLO R. Sequence alignment in molecular biology[J]. Journal of Computational Biology, 1998, 5(2): 173-196.

[12] WANG Y, LI K B. An adaptive and iterative algorithm for refining multiple sequence alignment[J]. Computational Biology and Chemistry, 2004, 28(2): 141-148.

[13] GOTOH O. Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments[J]. Journal of Molecular Biology, 1996, 264(4): 823-838.

[14] KROGH A, BROWN M, MIAN I S, et al. Hidden Markov models in computational biology: Applications to protein modeling[J]. Journal of Molecular Biology, 1994, 235(5): 1501-1531.

[15] HOSEINI P, SHAYESTEH M G. Efficient contrast enhancement of images using hybrid ant colony optimisation, genetic algorithm, and simulated annealing[J]. Digital Signal Processing, 2013, 23(3): 879-893.

[16] KAIWARTYA O, PRAKASH S, SAHU D P, et al. Multiple sequence alignment using genetic algorithm and non-dominant sorting genetic algorithm-ii (nsga ii) and variants[J]. Journal of Bioinformatics and Intelligent Control, 2014, 3(4): 294-299.

[17] NOTREDAME C. Recent progress in multiple sequence alignment: a survey[J]. Pharmacogenomics, 2002, 3(1): 131-144.

[18] NOTREDAME C, HIGGINS D G, HERINGA J. T-Coffee: A novel method for fast and accurate multiple sequence alignment[J]. Journal of Molecular Biology, 2000, 302(1): 205-217.

[19] CHAICHOOMPU K, KITTITORNKUN S. Multithreaded ClustalW with improved optimization for intel multi-core processor[C]// International Symposium on Communications and Information Technologies. IEEE, 2006:590-594.

[20] HALL P, JING B. On sample reuse methods for dependent data[J]. Journal of the Royal Statistical Society. Series B (Methodological), 1996,58(4): 727-737.

(責(zé)任編輯： 康 鋒)

Reliability Evaluation of DNA Sequence Clustering Based on Genetic Algorithm

SUNJie,LIZhong

(School of Sciences, Zhejiang Sci-Tech University, Hangzhou 310018 , China)

Cluster analysis is a commonly used method for molecular biologists to infer the evolutionary relationship of homologous sequences. Evaluating the reliability of clustering is an important part of cluster analysis. Bootstrap is a statistical method for evaluating the reliability of clustering, which replaces all the nucleotide bases of DNA sequences for sampling analysis. On the basis of Bootstrap method, an improved method to evaluate the reliability of DNA sequence clustering is proposed. The method first randomly extracts a certain proportion of nucleotide bases from the original DNA sequence, and then uses the genetic algorithm to replace each of the extracted bases. The proposed method takes into account of the correlation between the bases, and the samples obtained are closer to the original sequence and more in line with the results of biological evolution. The method was used to evaluate the reliability of the phylogenetic tree constructed by DNA sequence clustering. The experimental results show that the accuracy of reliability assessment is improved, indicating that the method is feasible and effective.

DNA sequence; cluster analysis; phylogenetic tree; Bootstrap; reliability

10.3969/j.issn.1673-3851.2017.05.024

2016-11-11 網(wǎng)絡(luò)出版日期： 2017-04-25

國(guó)家自然科學(xué)基金項(xiàng)目(11671009)；浙江省自然科學(xué)基金項(xiàng)目(LY14A010032)

孫 杰(1987-)，男，河南淮陽(yáng)人，碩士研究生，主要從事計(jì)算機(jī)圖形、生物信息可視化方面的研究。

李 重，E-mail：lizhong@zstu.edu.cn

O29

A

1673- 3851 (2017) 03- 0461- 06