基于遺傳算法的DNA序列聚類可靠性評估

孫 杰, 李 重

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

?

基于遺傳算法的DNA序列聚類可靠性評估

孫 杰, 李 重

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

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

DNA序列；聚類分析；進化樹；Bootstrap；可靠性

0 引 言

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

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

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

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

1 方法設計

1.1 序列相似性分析

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

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

本文通過軟件包MEGA用ClustalW算法先對DNA序列間的相似性進行了分析，然后使用適當?shù)亩攘繕藴视嬎愕玫搅薉NA序列之間的距離矩陣。

1.2 Bootstrap改進方法

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

標準Bootstrap方法直接應用在生物序列聚類可靠性評估中存在兩個缺點[20]。

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

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

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

為了更合理地模擬自然進化，本文在進行重采樣時僅改變原始DNA序列中一定比例的堿基，并且在置換堿基時將其臨近堿基序列考慮進來。另外，本文在置換堿基時引入自然進化準則，使用遺傳算法(genetic algorithm)模擬具有相關性堿基之間的變化過程。在模擬過程中，本文首先以某一待置換堿基為中心構建堿基窗口(一定長度的堿基序列)；然后對該堿基窗口應用遺傳算法的選擇、交叉和變異運算，以模擬生物序列的自然進化；最后對遺傳運算結束后的堿基窗口依據(jù)適當原則選出堿基，以替換原始序列中的堿基。具體過程如下：

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

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

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

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

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

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

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

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

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

(1)

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

c) 通過序列比對結果計算出相似距離矩陣。

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

改進Bootstrap方法的主要流程如圖1所示。

圖1 改進的Bootstrap方法流程

1.3 聚類可靠性計算

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

2 結果和討論

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

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

表2 11個H5N1病毒的HA基因序列

表3 29個H5N2病毒的HA基因序列

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

(a) 標準Bootstrap方法

(b) Subset Bootstrap方法

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

(a) 標準Bootstrap方法

(b) Subset Bootstrap方法

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

圖4 對29個H5N2病毒的HA基因序列使用本文方法得到的聚類可靠性結果

方法可靠性平均值實驗數(shù)據(jù)1實驗數(shù)據(jù)2實驗數(shù)據(jù)3本文方法98.00097.87597.769SubsetBootstrap93.00094.75095.885標準Bootstrap84.00090.75093.231

3 結 語

本文首先利用多序列比對方法分析DNA序列之間的相似性，并構造相似距離矩陣；然后在相似距離矩陣基礎上用UPGMA進行聚類，同時構建進化樹顯示聚類結果；最后使用基于遺傳算法的改進評估方法對聚類結果進行可靠性分析。本文對給出的3組DNA數(shù)據(jù)用相同聚類方法構建進化樹，并用標準Bootstrap、Subset-Bootstrap和本文方法對每組數(shù)據(jù)構建的進化樹進行了可靠性評估。實驗結果表明，本文提出的方法優(yōu)于標準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.

(責任編輯： 康 鋒)

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)絡出版日期： 2017-04-25

國家自然科學基金項目(11671009)；浙江省自然科學基金項目(LY14A010032)

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

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

O29

A

1673- 3851 (2017) 03- 0461- 06