基于MST的基因數(shù)據(jù)社團挖掘算法

劉飛

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

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

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

1 最小生成樹的相關(guān)定義

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

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

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

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

3)重復上述步驟2），當U=V時循環(huán)結(jié)束。

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

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

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

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

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

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

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

2 基因表達數(shù)據(jù)的生成樹表示方法

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

1)皮爾遜相關(guān)系數(shù)

2)歐幾里德距離

3)斯皮爾曼相關(guān)系數(shù)

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

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

3 基于MST的社團挖掘算法

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

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

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

2)重復社團挖掘算法

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

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

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

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

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

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

4 實驗仿真

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

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

隨機生成80個數(shù)據(jù)，每個數(shù)據(jù)有20個屬性，構(gòu)造它的最小生成樹并使用上面的社團挖掘算法進行社團劃分。用重復社團挖掘算法和改進的重復社團挖掘算法對S選擇不同值時，計算出它們總的誤差平方和如圖4所示?？梢钥闯龈倪M后的社團挖掘算法性能有一定提升，當S為5時得到最佳的分團結(jié)果。

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

5 結(jié)束語

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

[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]王艷,李應興,靳二輝.復雜網(wǎng)絡健壯社團挖掘算法[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.