摘 要：在生物學(xué)研究中，需要對(duì)基因進(jìn)行分類，以獲得對(duì)種群固有結(jié)構(gòu)的認(rèn)識(shí)，有效鑒別基因表示數(shù)據(jù)的模式是研究DNA序列的重要基礎(chǔ)。在已有最大樹聚類理論基礎(chǔ)上，引入模糊聚類思想，提出了最大樹基因聚類算法，同時(shí)將該方法用于基因的聚類分析，實(shí)驗(yàn)結(jié)果表明它們是有效可行的。

關(guān)鍵詞：最大生成樹；模糊聚類；簇；相關(guān)系數(shù)；基因

中圖分類號(hào)：TP311

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2015）005-0068-02

作者簡(jiǎn)介：劉芳（1979-），女，遼寧沈陽人，碩士，沈陽理工大學(xué)理學(xué)院講師，研究方向?yàn)閼?yīng)用數(shù)學(xué)與計(jì)算機(jī)輔助幾何設(shè)計(jì)。

0 引言

近年來，隨著人們對(duì)生命科學(xué)的深入研究，開發(fā)出許多用于基因分析的工具[2]。利用這些工具，在不同的試驗(yàn)條件下，人們能夠?qū)Τ汕先f個(gè)基因進(jìn)行實(shí)時(shí)監(jiān)控，以研究由于環(huán)境變化引起的基因變化。因此，首先對(duì)大量的基因表示數(shù)據(jù)進(jìn)行分類，有效地鑒別基因表示數(shù)據(jù)的模式是研究DNA序列的重要基礎(chǔ)。

聚類分析是統(tǒng)計(jì)學(xué)的一個(gè)分支，聚類算法能從空間數(shù)據(jù)庫中直接發(fā)現(xiàn)一些有意義的聚類結(jié)構(gòu)。聚類分析以相似性為基礎(chǔ)，在一個(gè)聚類中的模式比不在同一聚類中的模式之間具有更多相似性。聚類分析算法有劃分法、層次法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法等。但傳統(tǒng)的聚類分析把每個(gè)待辨識(shí)的對(duì)象嚴(yán)格地劃分到某個(gè)類中，這種硬劃分的界線是分明的。而客觀世界中存在大量界限不分明的聚類問題，它們的類屬和性態(tài)存在著中介性，適合軟劃分。Zadeh提出的模糊集理論[3]為這種軟劃分提供了有力的分析工具，人們開始用模糊方法處理聚類問題，并稱之為模糊聚類分析。常用的模糊聚類方法有傳遞閉包法、動(dòng)態(tài)直接聚類法、最大樹法[2]、基于攝動(dòng)的模糊聚類方法FCMBP、系統(tǒng)聚類法、模糊C-均值法和模糊ISODATA算法。

本文把最大生成樹法用于模糊聚類分析，最大生成樹可以將數(shù)據(jù)聚類轉(zhuǎn)換成樹分割問題，通過刪除最大生成樹中某些具有最短距離的邊，將最大生成樹分為若干子樹。本文討論數(shù)據(jù)集的最大生成樹表示，以及相應(yīng)的聚類分析方法，并將其用于基因分類。

1 用生成樹表示數(shù)據(jù)

2 最大生成樹聚類算法

楊國(guó)惠[4]等人提出改進(jìn)的中心聚類算法，本文在此基礎(chǔ)上又提出最大生成樹的基因聚類算法，同時(shí)通過實(shí)例驗(yàn)證了此算法可以得到較好結(jié)果。算法描述如下：具有較長(zhǎng)邊的兩個(gè)點(diǎn)應(yīng)屬于同一個(gè)簇，具有較短邊的兩個(gè)點(diǎn)應(yīng)屬于不同的簇，并將被分割。由推論1，通過清除最大生成樹中具有最小距離的k-1條邊可得到k個(gè)簇，只要不同簇之間點(diǎn)的邊距離小于簇內(nèi)點(diǎn)的邊距離，這k個(gè)簇則是全局最優(yōu)解。但是，當(dāng)不同簇沒有用短距離邊而是一系列長(zhǎng)距離邊連接，或者當(dāng)存在“噪聲”和孤立點(diǎn)數(shù)據(jù)時(shí)，該方法可能得不到最好的聚類結(jié)果。為了自動(dòng)決定應(yīng)該進(jìn)行多少次有效分割，可在分割算法中檢測(cè)新產(chǎn)生的子樹是否為孤立點(diǎn)，通過消除孤立點(diǎn)并增加有效分割次數(shù)，最終獲得正確的k個(gè)簇。

2.1 算法程序?qū)崿F(xiàn)

開始

輸入：數(shù)據(jù)集data和聚類數(shù)目K

begin

weight←compute_weight（data）；{計(jì)算距離矩陣}

t←{1，2，3，…，data_number}；

m=0；

查找weight中的最大值所在的行列值（x，y）；

while（m～= data_number-cluster_number）

begin

if（t（x）～=t（y））

begin

m=m+1；

tree（1，m）=x（1）；

tree（2，m）=y（1）；

tmin=min（t（x（1）），t（y（1）））；

tmax=max（t（x（1）），t（y（1）））；

for j=1：datanumber

if（t（j）==tmax）

t（j）=tmin；

end

weight（x，y） ←∞；

查找weight中的最大值所在的行列值（x，y）；

end

由tree得到聚類結(jié)果cluster；

計(jì)算聚類誤差平方和cluster_err；

計(jì)算q值；

end

輸出：聚類cluster、誤差平方和cluster_err，q值；

結(jié)束

3 實(shí)驗(yàn)結(jié)果與評(píng)價(jià)

現(xiàn)選擇酵母數(shù)據(jù)集[5]，此數(shù)據(jù)集中每個(gè)基因有79個(gè)屬性（或79維），選擇4個(gè)聚類共68個(gè)基因，這4個(gè)聚類分別為protein degradation（聚類C）、glycolysis（聚類E）、protein synthesis（聚類F）、 protein chromatin（聚類H）。

這個(gè)實(shí)驗(yàn)的目的是將最大生成樹基因聚類算法應(yīng)用到基因聚類中，同時(shí)說明該算法是可行、有效的。為了評(píng)價(jià)計(jì)算結(jié)果，使用以下定義。

誤差平方和J（k）的定義如下：

J（k）=∑ki=1∑d∈Tid-center（Ti）2（5）

對(duì)于用戶選擇的目標(biāo)函數(shù)和一個(gè)整數(shù)值K，計(jì)算最優(yōu)k聚類k∈[1，K]，然后比較這些值。設(shè)J（k）代表選擇的目標(biāo)函數(shù)最佳k聚類的值，里面的k∈[2，K-1]，q（k）的最大值作為最自然的聚類數(shù)：

q（k）=J（k-1）-J（k）J（k）-J（k+1）（6）

距離測(cè)度采用公式（2）。

從圖像中可以看到最大生成樹基因聚類算法的最佳聚類數(shù)是4，分類的結(jié)果完全一致（見圖1）[1]。

4 結(jié)語

本文在已有最大樹聚類理論基礎(chǔ)上，引入模糊聚類思想，提出了最大樹基因聚類算法，對(duì)基因數(shù)據(jù)的聚類分析有重要的實(shí)踐價(jià)值。特別對(duì)于生物學(xué)DNA序列信息、蛋白質(zhì)結(jié)構(gòu)信息的分類更具有意義。

參考文獻(xiàn)：

[1] YING XU， VICTOR OLMAN， DONG XU.Clustering gene expression data using a graph-theoretic approach： an application of minimum spanning trees[J]. Bioinformatics， 2002， 18（4）：526-545.

[2] HATHAWAY R J，BEZDEK J C.Optimization of clustering criteria by reformulation[J].IEEE Transactions Fuzzy Systems，1995，3（2）：241-245.

[3] ZADEH L A. Fuzzy sets [J].Information and contral，1965（8）：338-353.

[4] 楊國(guó)惠，周春光，等. 最小生成樹用于基因表示數(shù)據(jù)的聚類算法[J].計(jì)算機(jī)研究與發(fā)展，2003，40（10）：1431-1435.

[5] M B EISEN，P T SPELLMAN，P O BROWN，et al.Cluster analysis and display of gene-wide expression patterns[J]. The National Academic of Science，N W，1998.

（責(zé)任編輯：黃 ?。?