層次聚類在進化樹構建中的應用

李國寶，業 寧

(南京林業大學 信息科學與技術學院，南京 210037)

0 引言

從達爾文時代開始，人類對生物起源的研究加以重視，各種生物進化學說相繼被提出。由于生物進化歷史是沒有文字記載的，后人只能通過史前生物的化石等片面信息來盡可能準確的模擬生物進化的順序，這就可能會形成錯誤的生物進化推斷歷史。隨著20世紀中期生物遺傳信息研究取得突破進展，人類通過生物的遺傳物質來研究其進化歷史成為可能。

現代生物學用生物進化樹來描述生物之間進化關系，兩種(或者多種)生物如果在同一層節點，則表明該組生物進化距離較近(即從同一祖先進化而來的可能性較大)[1]；反之，表明這些生物之間的生物差異性較大。

生物進化樹可以根據其是否按照進化距離構建來分類，這樣就有基于進化距離構建的方法和基于統計特征或者生物離散特征構建的方法?；谶M化距離的構建方法主要有最近鄰法[2]，UPGMA法等；基于統計方法的構建主要有最大似然法(Maximum likelihood)[3]；基于生物離散特征的構建方法主要是最大簡約法(Maximum Parsimony)[4]。

UPGMA方法是基于距離的進化樹構建方法，該方法思想是：將兩個進化距離最近的物種合成到一個復合物種組中,然后將新的距離矩陣中距離最小的兩個物種再次合成一個復合物種組,如此反復,直到所有的物種都被聚為一棵進化樹[5]。UPGMA方法的使用有一個前提，即假設一棵進化樹中所有物種的進化速率[6]是相同的。

NJ(Neighbor Joining Method, NJ)方法是距離法建樹中比較有實用價值的方法。與UPGMA相比，NJ方法不用假設進化樹中所有物種的進化速率相同，因此在大多數情況下比較令人信服。該方法思想是：通過確定距離最近的成對分類物種組來使進化樹的進化距離之和達到最小。在進行序列合并時,不僅要滿足待合并序列進化距離的相近,同時也要求待合并的序列與其它序列的近似距離較遠。本文實驗一中生成的進化樹將會與NJ方法生成的進化樹進行比較。

ML(Maximum Likelihood)方法于1981年被提出，該方法構建思想基于統計學。在預先選擇的進化模型下計算每一種進化樹生成的可能性，選擇最大可能性的進化樹即為最大似然樹。最大似然法在構建進化樹的準確度方面很高，但是在處理大數據量時效率比較低，并且對模型的依賴比較嚴重。

MP(Maximum Parsimony)方法依據各個位置上由一條生物序列突變成另一條生物序列所需最小數量突變來進行比較分析和聚類樹生成的,最終的進化樹是基于整條序列所需的突變總數的。

1 研究思想

層次聚類的基本思想是：通過迭代分類，把相似的樣本放在一層，直到樣本都被歸到某一層中[7]。具體的層次聚類算法分為兩種，從頂層到底層的方法和從底層到頂層的方法。

從頂層到底層的算法思想是：(1)先把樣本當作一個集合，從這個集合中取出2個(或者多個)最為相似的樣本，形成一顆二叉(或者多叉)形狀的樹，此時，集合剩下的樣本作為樹根節點，2個(或者多個)相似的節點作為第一層葉子節點；(2)再從樹根節點集合中選取一類相似的樣本作為第二層葉子節點，繼續擴展剛才生成的樹；(3)重復步驟2，直到根節點集合中樣本數為0；(4)按照2叉樹的生成規則整理生成的進化樹，保證結果是一棵2叉樹。

從底層到頂層的層次聚類方法與前者描述的由頂層至底層算法相似，只是在進化樹形成順序上是從葉子節點到根節點。

先通過序列比對計算生物之間的進化距離，然后運用層次聚類方法[8]對生物樣本進行分類，最終生成層次聚類結果以二叉樹形式表現。與基于距離的其他方法如NJ、UPGMA等進化樹構建方法以及基于統計的ML方法，基于生物表現特征的MP方法等生成的進化樹比較后驗證層次聚類方法的可行性，以及如何提高進化樹的準確率。

2 序列比對計算生物進化距離

進化距離的計算是通過比較DNA序列得到的。序列的比對有兩兩比對和多重比對之分。比對算法有blast，clustal，fasta等，本實驗采用的是多序列比對中的clustalw方法。

實驗一：8個物種線粒體DNA距離矩陣

由于線粒體DNA變異速率很慢，它們以每一百萬年百分之二點二的速度變異，因此選擇線粒體DNA作為研究對象是比較合理的。

本實驗將甘藍型油菜種子萌發出現胚根第1天的幼苗轉移至含有eBL(epi-Brassinolide)或BRZ的固體1/2 MS培養基上(方形皿)。eBL生理處理實驗在光照條件下進行，6種處理濃度分別為0、1 × 10-9、1 × 10-8、1 × 10-7、1 × 10-6和 1 × 10-5 mol/L，處理4 d后觀察不同濃度eBL對幼苗發育的影響。BRZ生理處理實驗在黑暗下進行，分為0和1 × 10-6 mol/L 兩個處理濃度，處理3 d后觀察BRZ對幼苗黑暗條件下發育的影響。

序列來自GenBank，詳細信息如表1所示。

表1 8 條線粒體 DNA 物種 GenBank 相關信息

由表1構建的距離矩陣見表2。

表2 8 個物種所對應的相似距離矩陣

實驗二：十一種脊椎動物序列數據的實驗

生物進化樹的好壞，主要看與它與生物真實的進化歷史差別多大。生物的真實進化史往往難以知曉，但是也有例外。表3給出的生物序列信息的真實進化樹可以用古生物學和形態學方面的數據來構建[9]。11種脊椎動物線粒體全DNA信息如表3。

表3 11 種脊椎動物的名稱及其線粒體全基因組 GenBank 編號

由表3構建的距離矩陣如表4所示。

表4 11種脊椎動物線粒體DNA的距離矩陣

續表4 11種脊椎動物線粒體DNA的距離矩陣

3 層次聚類生成生物進化樹

層次聚類的步驟：

(1)從n個序列樣本中選擇2個距離最小的放到集合s中，此時集合s和剩下的n-2個樣本作為n-1個候選樣本；

(2)從剩下的n-1個候選樣本中選擇2個距離最小的放到集合s1中，類似步驟1，此時n-2個候選樣本；

(3)重復步驟2，直到候選樣本樹為0；

(4)此時n個序列樣本層次聚類完成，通過層次號來逐層構建二叉樹。

實驗一通過層次聚類方法構建的進化樹見圖1。

圖1 8個物種層次聚類結果

對生成的聚類結果統一注釋后得到的進化樹見圖2。

圖2 實驗一的層次聚類生物進化樹

實驗二通過層次聚類的結果見圖3。

圖3 實驗二11種脊椎動物線粒體

實驗二層次聚類結果經過解釋后的生物進化樹見圖4。

圖4 實驗二11種脊椎動物的生物進化樹

4 對層次聚類生物進化樹的評價

由于生物的真實進化歷史無法得知，后人只能通過生物化石等信息來推斷生物最有可能形成的進化歷史。因此，對于構建的生物進化樹，不存在唯一的評價標準。不過，可以在確保數據準確的前提下，對多種方法構建的進化樹進行比較分析，如果多種方法構建的進化樹拓撲結構一致，則可以側面驗證構建方法的有效性。

實驗一中層次聚類構建的進化樹與最大似然法、NJ法構建的進化樹(見圖5)結構完全一致，因此可以驗證層次聚類在構建這8種生物線粒體DNA進化樹中的有效性。

圖5 最大似然法和最近鄰法構建的8種生物進化樹

實驗二中層次聚類構建的11種脊椎動物的進化樹和生物真實的進化樹拓撲結構有細微差別，見圖6。

圖6 11種脊椎動物的真實系統樹

經過查閱相關資料，作者發現這種進化樹結構差別源于所選取的序列長度較長。在計算相似距離時，序列越長，出現程序性錯誤的可能性就越大。

因此，本文的結論：在層次聚類產生進化樹時，盡可能選取長度較短的能夠代替生物進化信息的DNA序列，這樣可以生成較準確的進化樹。

參考文獻：

[1] SNEATH P, SOKAL R. Numerical taxonomy—the principles and practice of numerical classification[M].San Francisco:W. H. Freeman and Company, 1973.

[2] SAITOU N, NEI M. The neighbor-joining method: a new method for reconstructing phylogenetic trees[J].Mol Biol Evol, 1987(4):406-425.

[3] Felsentein J. Evolutionary trees from DNA sequences: a Maximum likelihood approach[J].J Mol Evol, 1981，17:368-376.

[4] Kimura M. Evolutionary rate at the molecular level[J].Nature,1968，217:624-626.

[5] 劉金桂.分數階超混沌系統的自適應函數投影同步[J].淮陰工學院學報，2012，21(1)：1-4.

[6] Zhaxybayeva, O. and W.F. Doolittle, Lateral gene transfer[J].Current Biology, 2011,21(7):242-246.

[7] 孫亂,陸祖宏,謝建明.生物信息學基礎[M].北京:清華大學出版社,2005.

[8] 丁淑妍.進化分析與結構預測中的若干問題研究[D].大連：大連理工大學,2012.

[9] 孫士保,秦克云.改進的k-平均聚類算法研究[J].計算機工程,2007,33(13):200-201.