基于MST的基因數據社團挖掘算法

劉飛

（寶雞文理學院 物理與信息技術系，陜西 寶雞 721016）

隨著高通量測序技術的發展，產生了大量的基因表數據。這就需要一些方法來分析這些數據，得出這些數據包含的潛在信息[1]。因此對大量的基因表示數據和微生物網絡進行社團挖掘，有效地鑒別基因表示數據的模式是研究DNA序列的重要基礎。利用統計學、生物信息學和計算機科學提供一些理論和方法，解決生物信息學中海量微生物數據的計算和信息處理問題越來越受到人們的重視。人們發現許多真實網絡中都存在著一個重要的特性——社團（即模塊）結構，即整個網絡是由若干個社團構成的，這些社團具有內緊外松的結構特征[2-4]。例如在生物網絡中可根據各個基因節點不同的功能特性劃分為不同的社團，每個社團內部節點間連接相對緊密，各個社團之間的連接卻相對稀疏。

現在有很多用于處理基因表達數據社團挖掘的算法，如Eisen等人[5]應用分層的平均邊社團挖掘算法對酵母基因網絡進行分析；Ben-Dor和Yakhini等人[6]開發的CAST算法；K-平均值算法；自組織映算法；主成分分析算法等。使用不同的數據分析技巧和不同社團挖掘算法對同樣一個基因數據集會產生不同的效果。這些算法被實踐證明性能確實非常優越，但也存在一些不足，很多算法沒有證明自己的社團分割是否是最優的。本文我們介紹一種基于最小生成樹(minimum spanning trees,MST)的算法，用于處理基因表數據的社團挖掘。這種算法將基因表達數據的模塊挖掘問題轉換為樹的分割問題，通過刪除樹中一些特定意義的邊，將最小生成樹分成若干個子樹，每個子樹就是一個社團模塊。本文通過實驗證明了該社團模塊挖掘算法的優越性。

1 最小生成樹的相關定義

設G=(V,E,W)是一個連通圖，V是G中點的所有集合，E是G中邊的所有集合，W是邊的權值。一個圖的生成樹指的是它的最小連通圖，包含所有頂點，圖中邊的個數比點的個數少一，如若再多一條則會形成回路。而最小生成樹[7]指的是所有生成樹中各邊權值之和最小的那棵生成樹，根據最小生成樹的性質，普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法可以非常便捷地計算出一個連通圖的最小生成樹。下面分別介紹這兩種算法：

普里姆算法，假設N=(V,{E})是連通網，TE為最小生成樹中邊的集合。

1)初始化一個新的圖，圖中包含原連通圖的所有節點，但是沒有邊，即U={u0}(u0∈V),TE=Φ；

2)在所有u∈U,v∈V-U的邊中選一條權值最小的邊（u0，v0）并入集合 TE，同時將 v0并入 U；

3)重復上述步驟2），當U=V時循環結束。

此時，TE 中必含有 n-1條邊，則 T=（V，{TE}）為 N 的最小生成樹。

克魯斯卡爾算法，假設N=(V,{E})是連通網，將網中所有的邊按照權值從小到大排序：

1)將連通網中的每一個頂點看成一個集合，則有n個集合；

2)從權值最小的邊開始選取，所選邊的頂點處在不同的兩個集合中，把這條邊放到生成樹邊的集合中，并把這條邊的兩個頂點合并。

3)重復上述步驟2),當所有的頂點并入一個集合時，結束操作。

可以看出，普利姆算法逐步增加U中的頂點，可稱為“加點法”。克魯斯卡爾算法逐步增加生成樹的邊，與普里姆算法相比，可稱為“加邊法”。利用Prim算法或者Kruskal算法可計算出一個連通網絡的最小生成樹如圖1所示。

圖1 一個連通網絡及其MSTFig.1 A connect network and its minimum spanning tree

2 基因表達數據的生成樹表示方法

使用最小成生樹來表示一個基因表達數據集，把多維基因表示數據的社團模塊挖掘問題轉化為最下生成樹的分割問題。 權圖G(D)=(V，E)，其中點集合V=｛didi∈D }，di=(di1，di2，…，dim)表示i個基因，每個基因由m個屬性。邊集E=｛di,dj對于 di，dj∈D 且 i≠j}(這里的邊集可以表示基因相似或相異程度的一個度量)。顯然權圖G(D)=(V，E)是一個完全圖，圖中每一條邊(u，v)∈E可以表示為兩個基因之間的相似程度或相異程度 ρ(u，v)，u和 v之間的權值 ρ(u，v)可采用皮爾遜相關系數或者歐幾里德距離等其他距離度量方法。下面分別介紹這幾種方法，其中dˉi表示di的平均值。

1)皮爾遜相關系數

2)歐幾里德距離

3)斯皮爾曼相關系數

圖2(a)是一個基因數據的完全網絡，它們之間的邊可以通過上述方法計算得到，圖2(b)是其用Prim算法或者Kruskal算法計算得出的最小生成樹，從圖中可以看出分成了3個社團，同一社團中的數據點用較短的樹邊連接，而不同社團間的數據點由長的樹邊連接。在一個社團內部相鄰點之間的距離小于不同社團之間點的距離。那么通過清除G(D)的最小生成樹中具有最大距離的S-1條邊，網絡就可以分成S個社團。

圖2 一個基因的完全網絡及其最小生成樹Fig.2 A gene complete network and its minimum spanning tree

3 基于MST的社團挖掘算法

不同的社團挖掘算法需要不同的評價準則函數，為了獲得最佳的社團劃分結果，在這里將敘述了3種評價準則函數和它們對應的社團挖掘算法。

1)去除MST長邊的社團挖掘算法

一個最為簡單的評價準則函數就是去掉MST中S-1條長邊，而形成S個子樹，使得所有子樹的邊權值之和最小。這個評價準則函數的根據如下：如果兩個點之間的權值很小，則它們應該屬于同一社團（子樹），反之亦然。但是當不同社團之間的連接邊的權值很小時，或者存在一些噪聲或者孤立點時，這種判斷方法就不盡理想了[8]。為了避免這種情況，可在此社團挖掘算法劃分中判斷新的社團是否為孤立點，通過消除孤立點來提高這種社團挖掘算法的精度。

2)重復社團挖掘算法

把所得的最小生成樹（MST）分割成S個子樹Ti｛，它所依據的評價準則函數如下：

重復社團挖掘算法使得任意一個社團的中心和團內基因點之間邊的權值之和最小，用不同的度量方法時，中心center(Ti)會有不同的值。此外我們還可以采用平方誤差評價準則函數，其評價準則函數如下：

重復社團挖掘算法以任意一個最小生成樹的S分割開始，首先計算每一個子樹的中心值，然后重復下面步驟：把相鄰的兩個社團（一般通過長邊相連）合并為一個社團，在新的社團中去除所有的邊，通過評價準則函數（4）來進行最優二社團劃分。

3)改進的重復社團挖掘算法

改進的重復社團挖掘算法是一種面向中心的社團劃分方法，同樣以任意一個最小生成樹的S分割開始，并計算每一個子樹的中心值 center(Ti)，i=1，2，…，S。 刪除最小生成樹中的所有邊，對于最小生成樹中的任意結點dj，計算

當 I′值最小時的 I=i，即 dj距離 center(Ti)最近，那么 dj應該屬于子樹Ti中的結點。與評價準則函數(4)相比，這個改進的重復社團挖掘算法更容易獲得全局最優解。

4 實驗仿真

實驗用的仿真數據為Sherlock等人[9]的基因表達數據，這個數據集包含500多個基因，每個基因有18個屬性。使用第2個社團挖掘算法，歐幾里德距離作為距離度量。圖3顯示采用第2種算法時最佳S社團挖掘值對社團數目S的關系，可以看到當S從1到6時社團挖掘值顯著改善，之后隨著S值增加改善率下降。因此整個基因數據集分為6個社團比較理想。

圖3 基因表達數據的準則函數與社團數目對照圖Fig.3 The chart of criterion function and community number for gene expression data

隨機生成80個數據，每個數據有20個屬性，構造它的最小生成樹并使用上面的社團挖掘算法進行社團劃分。用重復社團挖掘算法和改進的重復社團挖掘算法對S選擇不同值時，計算出它們總的誤差平方和如圖4所示。可以看出改進后的社團挖掘算法性能有一定提升，當S為5時得到最佳的分團結果。

圖4 不同方法基因表達數據的準則函數與社團數目對照圖Fig.4 The chart of criterion function and community number with different methods for gene expression data

5 結束語

針對一些生物網絡的社團劃分問題，人們提出了很多行之有效的方法。然而使用MST表示多維基因表達數據集以解決基因表示數據的社團劃分問題，確實是一種嚴格且有效的方法，特別對于一些準則函數，這一算法能保證獲得全局最優解。將多維數據社團劃分問題轉換為最小生成樹的分割問題，可以解決各種生物學分析問題，如動植物系統分類、生物序列的特征識別、蛋白質家族分類等。同一社團內由類似的基因數據組成，研究和分析每個社團的結構和功能以及社團之間的關系，這對深刻認識諸多生物過程的本質有重要意義。

[1]Eric S lander.Array of hope[J].Nature Genetics,1999（21）:3-4.

[2]Girvan M，Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences，2002，99（12）：7821-7826.

[3]王艷,李應興,靳二輝.復雜網絡健壯社團挖掘算法[J].計算機工程與應用,2012,48(31):36-39.WANG Yan,LI Ying-xing,JIN Er-hui.Novel algorithm for robustcommunity in complex networks [J].Computer Engineering and Applications,2012,48(31):36-39.

[4]Brandes U,Delling D,Gaertler M,et al.On modularity clustering [J].Knowledge and Data Engineering,IEEE Transactions on,2008,20(2):172-188.

[5]Eisen M B,Spellman P T,Brown P O,et al.Cluster analysis and display ofgenome-wide expression patterns[J].Proceedings of the National Academy of Sciences,1998,95(25):14863-14868.

[6]Ben-Dor A,Shamir R,Yakhini Z.Clustering gene expression patterns[J].Journalofcomputationalbiology,1999,6(3-4):281-297.

[7]Frank Dehne,JohnIacono,Jorg-Rudiger Sack.Algorithms and Data Structures [M].Springer-Verlag Berlin and Heidelberg GmbH&Co.K,Edition.2011.

[8]Ramonell K M,Zhang B,Ewing R M,et al.Microarray analysis of chitin elicitation in Arabidopsis thaliana[J].Molecular Plant Pathology,2002,3(5):301-311.

[9]Sherlock G.Analysis of large-scale gene expression data[J].Current Opinion in Immunology,2000,12(2):201-205.