相似性度量在基因表達聚類分析中的應(yīng)用研究

1、論文發(fā)表專家一8 國學(xué)朮發(fā)叢網(wǎng)www,qikanwangnt相似性度量在基因表達聚類分析中的應(yīng)用研究摘要：聚類分析是基因表達數(shù)據(jù)分析研究的主要技術(shù)之一，其算 法的基本出發(fā)點在于根據(jù)對象間相似度將對象劃分為不同的類， 選 擇適當(dāng)?shù)南嗨菩远攘繙?zhǔn)則是獲得有效聚類結(jié)果的關(guān)鍵。 采用預(yù)處理 過的基因數(shù)據(jù)集在不同相似性度量準(zhǔn)則下進行的不同聚類算法的 聚類分析，并得到聚類結(jié)果評價。其中算法本身的缺陷及距離相似 性度量的局限性都是影響結(jié)果評價的因素， 為了獲得更有效的聚類 結(jié)果，改進相關(guān)聚類算法并提出了一種比例相似性度量準(zhǔn)則。關(guān)鍵詞：dna微陣列；聚類分析；相似性度量；基因表達dna微陣列(dna micro

2、array)技術(shù)的日益成熟導(dǎo)致了基因表達數(shù)據(jù)不斷擴大，尤其在近十幾年內(nèi)更以指數(shù)形式增長。如何分析 和處理大量的基因表達數(shù)據(jù)，從中提取有用的生物學(xué)或醫(yī)學(xué)信息，已成為后基因組時代研究的瓶頸12。由于基因芯片產(chǎn)生巨量的表達譜數(shù)據(jù)，數(shù)據(jù)挖掘技術(shù)已經(jīng)被廣泛的應(yīng)用到基因表達譜的許 多方面，并取得成功。聚類分析是基因表達數(shù)據(jù)分析研究的主要技 術(shù)之一 2 3,并且作為一種有效的數(shù)據(jù)分析工具，已廣泛地應(yīng)用于圖像處理、信息檢索、數(shù)據(jù)挖掘等領(lǐng)域。目前，作為研究基因表達數(shù)據(jù)的主要技術(shù)之一的聚類分析算法有 很多種，如分層聚類(hierarchical clustering),k均俏聚類(k_means clusteri

3、ng)，自組織映射(self organizing maps, soms),主成分分析(principal component analysis,pca)等等。但由于匸交發(fā)表專家一LB 國學(xué)朮發(fā)叢網(wǎng)不同聚類算法， 甚至同一聚類算法使用不同參數(shù)， 一般都會產(chǎn)生不 同的聚類結(jié)果。因此，在對數(shù)據(jù)處理過的基因表達矩陣聚類分析時，選擇合適的聚類相似性準(zhǔn)則至關(guān)重要，同時也是獲得合理、精確的 聚類結(jié)果的關(guān)鍵。1dna微陣列dna微陣列(dna microarray),也叫基因芯片。它將幾十個到上 百萬個不等的稱之為探針的核苷酸序列固定在微小的(約1 cm2)玻璃或硅片等固體基片或膜上，該固定有探針的基片就稱

4、之為dna微陣列。1.1基因表達數(shù)據(jù)的獲得和表示在不同的實驗環(huán)境條件或是不同的時間點，通過對基因芯片的掃 描，可以得到不同的實驗數(shù)據(jù)， 所以這些數(shù)據(jù)是基因在一定實驗條 件下或一段時間內(nèi)的表達情況。經(jīng)過對這些數(shù)據(jù)表達進行預(yù)處理和 標(biāo)準(zhǔn)化后，產(chǎn)生得到的微陣列數(shù)據(jù)也就是基因表達數(shù)據(jù)。微陣列基因表達數(shù)據(jù)主要為數(shù)值型，并以矩陣的方式存儲，“行”為各個基因在不同環(huán)境條件下或不同時間點的表達情況，“列”是同一環(huán)境或時間下一個樣本所有基因的表達譜。每一個元素代表第i個基因在第j個樣本中的表達水平。1.2基因數(shù)據(jù)的研究現(xiàn)狀與已經(jīng)發(fā)展了幾十年的結(jié)構(gòu)基因組學(xué)相比，基因表達譜的生物信 息學(xué)僅處于起步階段。現(xiàn)階段基因芯

5、片所遇到的挑戰(zhàn)并不在于表達論文發(fā)表專咅一01國SF/KJSB網(wǎng)wwwqikan訓(xùn)日ng.n巳t芯片實驗技術(shù)本身，而是發(fā)展實驗設(shè)計方法及數(shù)據(jù)分析4。實驗 數(shù)據(jù)的預(yù)處理、標(biāo)準(zhǔn)化的方式，度量相似性的方式以及所選擇的聚 類方法都會對分析結(jié)果產(chǎn)生影響。面對海量的基因數(shù)據(jù)，聚類算法 也不只是拘泥于傳統(tǒng)的k均值算敢，層次聚類算法上，而是向著 多元化、專門化、復(fù)雜化的方向發(fā)展。2聚類相似性研究在日常生活中進行識別時也總是利用相似性概念，但是人們又很 難對“相似”或“不相似”做出明確的定量表述， 因此通常所說的 相似性只具有定性的或不確定的性質(zhì)。 怎樣對相似性概念給以明確 的定量表述是模式識別工作者要解決的任務(wù)

6、之一。2.1相似性度量兩個樣本間的相似性或離散度的測量稱為相似性度量，簡稱相似 度。聚類通常按照樣本間的相似性進行分組， 因此如何描述對象間 相似性是聚類分析的一個重要問題。聚類分析按照樣本之間的親疏遠近程度進行分類。為了使類分得 合理，必須描述樣本之間的親疏遠近程度?？坍嬀垲悩颖局g的親 疏遠近程度主要有以下2類函數(shù)：(1)距離函數(shù)。可以把每個樣本看作高維空間中的一個點，進 而使用某種距離來表示樣本之間的相似性，距離較近的樣本性質(zhì)較 相似，距離較遠的樣本則差異較大。(2)相似系數(shù)函數(shù)。兩個樣本愈相似，則相似系數(shù)值愈接近1;論文發(fā)表專家一m國學(xué)朮發(fā)叢網(wǎng)www.qikanwa ng.na樣本愈不

7、相似，則相似系數(shù)值愈接近0。這樣就可以使用相似系數(shù)值來刻畫樣本性質(zhì)的相似性。d(i, j)是樣本i和樣本j之間相似性的量化表示，通常它是個非負(fù)的數(shù)值，一般地，距離函數(shù)有如下數(shù)學(xué)要求：(1)d(i, j)0:距離是個非負(fù)的數(shù)值；d(i, i)=0: 一個對象與自身的距離是0;d(i,j)=:d(j, i):距離函數(shù)具有對稱性；d(i, j)d(j,h)+d(h,i):從對象i到對象j的直接距離不會大于途經(jīng)任何其他對象h的距離(三角不等式)。如何選擇相似性的度量方法是一個相當(dāng)復(fù)雜的問題，因為相似度 的選擇可以在很大程度上影響聚類算法的輸出5。目前，有很多 相似性度量應(yīng)用到基因表達數(shù)據(jù)分析當(dāng)中。例如

8、：歐式距離、曼哈 坦距離、pearson相關(guān)系數(shù)、無中心pearson相關(guān)系數(shù)(對應(yīng)兩個 數(shù)據(jù)向量之間角度的余弦值)、spearman的排列相關(guān)系數(shù)等。在基 因表達數(shù)據(jù)聚類分析中，相似度普遍采用pears on相關(guān)系數(shù)和歐氏 距離6 7。在上述的幾個相似性度量中，歐幾里德距離和曼哈坦距離滿足前 述4個要求。但是其他幾個度量標(biāo)準(zhǔn)是基于相關(guān)系數(shù)的函數(shù)，它們并不完全滿足距離函數(shù)的要求。通常用相關(guān)系數(shù)r定義距離d為:d=1-r。這樣，所有的基于相關(guān)系數(shù)的相似性度量標(biāo)準(zhǔn)都使用這個定義而被轉(zhuǎn)化為距離。但是注意這種距離函數(shù)并不滿足二角不等2.1.1歐氏距離設(shè)有兩個基因樣本xi,xj，這兩個樣本可能在同一類中

9、，也可能 在不同的類中，因此，可以計算同一個類內(nèi)樣本與樣本之間的距離，也可以計算屬于不同類樣本與樣本之間的距離。歐氏距離測量空間 中兩個點的絕對距離，故同時考慮了矢量的方向和幅度。 則基因樣 本xi和xj之間的歐氏距離定義：di,j(xi,xj)=(xixj)t(xixj)二刀nk=1(xikxjk)2di,j越小，則兩個樣本距離越近，就越相似。2.1.2pearson相關(guān)系數(shù)pearson相關(guān)系數(shù)也是一種相似性測量， 大的相關(guān)系數(shù)意味著相 似性程度高。pearson相關(guān)系數(shù)從本質(zhì)上說是測量兩個表達矢量所 指方向的相似性?；驑颖緓i和xj之間的pearson相關(guān)系數(shù)定義:r(xi,yj)=刀

10、nm=1(xi,mi)(yj,myj)刀ni=1(xi,mi)2刀nj=1(yj,myj)2式中：i,yj分別為基因i和j在n個實驗條件 下的平均表達水平；pearson相關(guān)系數(shù)取值于-1,1,兩個相同的基因樣本的相關(guān)系數(shù)為1,相關(guān)系數(shù)為0的兩個基因樣本被認(rèn)為是 不相關(guān)的，而相關(guān)系數(shù)為-1的兩個基因樣本是反相關(guān)的8。2.2類相似性度量層次聚類算法有兩個關(guān)鍵問題，首先是如何選取類間相似性度 量，它是由兩tnii學(xué)朮友叢網(wǎng)wwwqikanwang.n論文發(fā)表專家一l類聚合為一類的依據(jù)；其次是聚合過程應(yīng)該停留在哪匸交發(fā)表專家一m國學(xué)朮發(fā)叢網(wǎng)一級上，這與最終聚合成幾類有關(guān)，也與聚類相似性有關(guān)。如前面

11、所述，根據(jù)不同的相似性度量標(biāo)準(zhǔn)(這里為某一距離標(biāo)準(zhǔn)或是相關(guān) 系數(shù))， 可以有不同的層次聚類方法。在層次聚類算法中需要計算 兩個類之間的相似度度量。常見的類間距相似性有最短距離法層次 聚類、最長距離法層次聚類、平均距離法層次聚類和重心法層次聚 類。(1)最短距離。規(guī)定兩個類間相距最近的兩個點之間的距離，為兩個類的相似度。則簡單連接定義為：di,j=mi n(di,j), dij=xixj,xi3i,xj3j式中dij是3i中任意一點與wj中任意一點 的歐式距離。(2)最長距離。規(guī)定兩個類間相距最遠的兩個點之間的距離，為 兩個類的相似度。則完全連接定義為：di,j=max(di,j), dij=x

12、ixj, xi3i,xj3j式中dij是3i中任意一點與3j中任意一點 的歐式距離。(3)平均距離。計算兩類之間所有樣品的距離，求和，取距離的均值作為兩類間的距離。則平均連接定義為：di,j=1 ninj刀xi3ixj3jxixj式中ni,nj分別是3i,3j類中的樣品的個數(shù)。(4)重心連接。各類中所有樣品的平均值作為類的重心，用兩類的重心間的距離作為兩類距離，則重心連接定義為：di,j=x(3i)x(3j)式中：x(3i)=1 ni刀x3ix,x(3j) = 1njEx3j x分別是3i,3j類所有樣品的平均值，ni,nj分別是3i、3j類匸交發(fā)表專家一LB 國學(xué)朮發(fā)叢網(wǎng)中的樣品的個數(shù)。3聚

13、類算法研究對基因表達矩陣的分析，往往是比較矩陣行和列的相似性或差 別，如果發(fā)現(xiàn)兩個行相似，貝何以推測它們對應(yīng)的基因具有協(xié)同調(diào) 節(jié)和功能相關(guān)性。通過在不同水平的比較，可以發(fā)現(xiàn)哪些基因具有 不同的表達，并且可以研究不同化合物對它們的影響。聚類分析的 首要目標(biāo)是將表達譜相似的基因歸納成類，然后聚焦于那些可能參 與某些生物過程的基因群，對這些類進行生物學(xué)注釋，同時獲得新 的生物學(xué)知識9。聚類分析技術(shù)是目前基因表達分析研究的主要計算技術(shù)之一，其 算法的基本出發(fā)點在于根據(jù)對象間相似度將對象劃分為不同的類。指將一組樣本按其相互間的相似程度歸入幾個子類，根本思想是確 定類群,使同一類內(nèi)的各樣本間差異最小，而不

14、同類間的差距最大。(1)層次聚類算法。 層次聚類算法可分為自上而下和自下而上 兩種方向進行，根據(jù)不同的方向，層次聚類方法可以分為凝聚的層 次聚類和分裂的層次聚類。自底向上的層次方法是首先將每個聚類樣本自成一個類，根據(jù)一 定的類間相似性度量標(biāo)準(zhǔn)計算兩個類間的距離。然后反復(fù)地將距離 最近的兩類合并為一類，并重新計算類間距離，直到達到某個終止 條件或只剩一個類。自上而下的層次方法是首先將所有聚類樣本看成一類，然后按照論文發(fā)表專家一8 國學(xué)朮發(fā)舌網(wǎng)www,qikanwang.nEt一定的類間相似性度量進行不斷分解為越來越小的聚類， 直到所有 聚類各成一類或滿足某一終止條件。（2）k均值算法。k均值算法

15、把n個觀察樣本分成k個類， 必須先指定類數(shù)k和迭代次數(shù)或收斂條件。 開始先指定k個質(zhì)心， 根據(jù)一定的相度性度量將每一個樣本分配到最接近或”相似”的質(zhì)心，形成一類，從而類內(nèi)的相似性高，類間的相似性低。然后以每 一類的觀察樣本的均值矢量作為這一類的新質(zhì)心，重新分配，反復(fù) 迭代直到類收斂（類的質(zhì)心不變）或達到最大的迭代次數(shù)。（3） 自組織映射（soms）。自組織映射算法是一種高維可視化的無監(jiān)督學(xué)習(xí)方法，描述輸入數(shù)據(jù)集的原型矢量也稱作為模型矢量或 權(quán)重矢量，同時將高維輸入空間連續(xù)映射到低維的網(wǎng)格上。這個網(wǎng) 格由一定數(shù)目的神經(jīng)元組成。給網(wǎng)格節(jié)點（神經(jīng)元）賦予一定權(quán)重，來表示類的質(zhì)心，計算一種距離確定各輸

16、入矢量的匹配節(jié)點，并由輸入矢量調(diào)整匹配節(jié)點及其鄰域的權(quán)重。經(jīng)過反復(fù)學(xué)習(xí)，模擬矢量 以有序的方式描述數(shù)據(jù)的概率分布。訓(xùn)練好的soms網(wǎng)格節(jié)點上已分配好相應(yīng)的基因表達譜，節(jié)點的權(quán)重矢量代表相應(yīng)類內(nèi)表達譜的 平均，且相鄰節(jié)點表示相似的類，類差別越大，其節(jié)點相距越遠。3.1聚類算法結(jié)果分析3.1.1聚類結(jié)果評價不同的聚類算法應(yīng)用于同一個基因表達數(shù)據(jù)時往往得到差別很 大的結(jié)果，怎樣去判定聚類結(jié)果好壞。為了解決這個問題，人們提匸交發(fā)表專家一LB 國學(xué)朮發(fā)叢網(wǎng)出了好幾種聚類指數(shù)來評價用聚類方法得出的劃分結(jié)果。對基因表 達數(shù)據(jù)聚類結(jié)果的評價在實驗當(dāng)中是必不可少的，聚類結(jié)果評價主 要是指用客觀的定量的方式對不同

17、的聚類算法在聚類過程中得到 的結(jié)果進行質(zhì)量、可靠性的評價。外部確認(rèn)是把實驗得到的聚類結(jié)果與數(shù)據(jù)集的另一種分割的“金 標(biāo)準(zhǔn)”去比較來評價聚類結(jié)果。 因為有個已經(jīng)事先分好的“金標(biāo)準(zhǔn)” 作為依據(jù)去比較聚類結(jié)果，所以外部評價比較有利于對數(shù)據(jù)集的聚 類質(zhì)量進行獨立無偏的評價。在基因表達數(shù)據(jù)聚類分析中，一般采 用rand指數(shù)(rand index)去評價聚類結(jié)果與外部“金標(biāo)準(zhǔn)”的一 致性。在基因表達聚類分析中，rand指數(shù)(rand index)被廣泛用來評價 聚類結(jié)果與外部標(biāo)準(zhǔn)的一致性。設(shè)s與r為一個數(shù)據(jù)集的兩種獨立 劃分，若a為s和r中都屬于同一類的個體對數(shù)，b為s中屬于同 一類而v中不屬同一類的個體

18、對數(shù)，c為r中屬于同一類而s中不 屬于同一類的個體對數(shù)，d為s和r中都不屬于同一類的個體對數(shù)，則rand指數(shù)定義為(a+d)/(a+b+c+d)。如果兩種劃分的聚類數(shù)不相 同，rand指數(shù)也能很好的檢測不同劃分的吻合度。rand指數(shù)在01之間，其數(shù)值越大，兩種劃分的一致程度越高。當(dāng)rand指數(shù)為1時，表示兩種聚類完全相同。3.1.2結(jié)果與分析論文發(fā)表專家一L8 國學(xué)朮發(fā)叢網(wǎng)由于分析各種聚類算法的實際效果需要已知類別的基因的表達數(shù)據(jù)，所以本文選用了酵母孢子化數(shù)據(jù)集（spor）。本文選用在減數(shù) 分裂早期、中期和末期的10個時間點測量了每一條基因mrna轉(zhuǎn)錄 水平變化，并對比研究了生長期細胞ndt8

19、0異常表達和缺失導(dǎo)致的 基因表達變化，共得到10個實驗樣品的表達。 選取其中分別屬于6個不重疊功能表達模式的161條基因表達譜組成數(shù)據(jù)集（記為spor數(shù)據(jù)集，161X10表達矩陣），并以這6個功能類作為外部標(biāo)準(zhǔn)類。在經(jīng)過以2為底對數(shù)化預(yù)處理之后，此數(shù)據(jù)集在進行聚類結(jié)果分析。如表1所示，該數(shù)據(jù)集經(jīng)過對數(shù)化預(yù)處理之后，分別以pearson相關(guān)系數(shù)和歐氏距離作為相似性度量準(zhǔn)則進行多種聚類算法得到 的rand指數(shù)。表1不同相似性度量下不同聚類算法的rand指數(shù)聚類方法pears on相關(guān)系數(shù)歐氏距離最短距離法層次聚類0.00800.012 4最長距離法層次聚類0.395 80.337 7平均距離法層次

20、聚 類0.39770.173 3重心法層次聚類0.415 40.051 1k均俏聚類0.403 20.408 7自組織映射聚類0.404 50.467 4由表1可得到最短距離法的層次聚類的結(jié)果明顯較差于其他三類距離層次聚類。k均個聚類算法11以歐式麗肉作為相似性征則的 聚類結(jié)果稍好于pears on相關(guān)系數(shù)的聚類結(jié)果。自組織映射聚類中 的以歐式距離作為相似性準(zhǔn)則的聚類結(jié)果明顯更優(yōu)?？傮w而言，對 兩種不同的相似性準(zhǔn)則的結(jié)果，k均俏聚類和soms聚類結(jié)果顯著論文發(fā)表專家一m國學(xué)朮發(fā)叢網(wǎng)www,qikan訓(xùn)日優(yōu)于分層聚類，soms聚類結(jié)果稍好于k得到這種結(jié)論的原因有很多種，其中聚類算法本身和相似性度

21、量都存在的問題：層次聚類雖然方法簡單，但有時在選擇分裂或合并點時都有困難 存在，因為一旦將一組個體分裂或合并，后續(xù)的類將在新類的基礎(chǔ) 上產(chǎn)生，而不能取消己經(jīng)完成的分裂或合并，也不能在類間對個體 進行調(diào)整。層次聚類分析不適于基因表達譜可能相似的復(fù)雜數(shù)據(jù)。在k均借聚艾算法在開始疋陵初始化血心確定聚類數(shù)不同的初始化質(zhì)心方法得到不同的聚類結(jié)果，由于有多種初始化k類的可能,故難于選擇最優(yōu)化的結(jié)果。對有些實驗，無法確定預(yù)期的類數(shù)， 而且也沒有很好的方法來選擇算法應(yīng)該運行的確切迭代次數(shù)。此外k均他算法對噪聲和京用數(shù)據(jù)比較械感，因為這類數(shù)據(jù)口能會影 響到各個聚類的均值。自組織映射聚類算法中節(jié)點的初始權(quán)重是隨機

22、產(chǎn)生的，使得算法 結(jié)果有一定的不確定性。網(wǎng)絡(luò)連接權(quán)的初始狀態(tài)、算法中的參數(shù)選 擇對網(wǎng)絡(luò)的收斂性能有較大影響。當(dāng)輸入數(shù)據(jù)較少時，訓(xùn)練的結(jié)果 通常依賴于樣本的輸入順序。本文中應(yīng)用的相似性度量是通過樣本間的距離確定的。然而數(shù)據(jù) 源中的兩個對象實際中是否相似與這兩個對象之間的距離并不是 完全對應(yīng)的。 對象間的距離表示的是對象的相近程度，而相似不僅 依賴于對象間的相近程度，還依賴于對象內(nèi)在的性質(zhì)，而距離不能論文發(fā)表專樂一B 國學(xué)朮發(fā)丟網(wǎng)反映這樣的特征。3.2聚類算法問題分析基于上述層次聚類不適合處理大量復(fù)雜數(shù)據(jù)，k均個力法屮，必須預(yù)先選擇類數(shù)作為先驗值，soms聚類算法對初始輸入?yún)?shù)的敏 感性和可能達到

23、局部最小10,相似性度量準(zhǔn)則的局限性等問題。 可以做出通過嘗試一些新的方法來解決這些問題。首先，不能局限 在傳統(tǒng)的聚類方法中，可以采用一些改進算法，如模糊k均俏算法，通過soms算法對基因表達數(shù)據(jù)進行聚類，再用層次聚類將每個 類對應(yīng)的神經(jīng)元權(quán)值二次聚類等新的算法， 都在一定程度上克服原 有的缺陷提高了基因聚類的效能。其次，需提出一種更確切的反映 對象相似的計算方法，并且要求簡單易行。在某些情況下，如果兩 個屬性的比例來代替距離表示對象的相似性，將更準(zhǔn)確地反映事物 間的相似程度。圖1是包含一個數(shù)據(jù)集中4個基因在5個屬性上的 表達值。圖1模式相似性示意圖可以看出，圖1中任何兩個基因的距離都 比較遠

24、，如果用基于距離的聚類算法不可能把4條基因聚類在同一類中，但實際上，這4個模式表現(xiàn)出的是一種非常近似的“平行” 模式。在這種情況下，兩個屬性的比例將更準(zhǔn)確地反映事物間的相 似程度。利用距離定義的相似度，當(dāng)兩個對象越接近，即距離越接 近于0,相似度越大。而基于比例的相似度定義中，比例越接近于1,二者的相似度越大。論文發(fā)表專家一m國手朮友叢網(wǎng)4結(jié)語綜上所述，基因表達數(shù)據(jù)分析研究的主要技術(shù)是聚類分析。而在 進行聚類算法分析數(shù)據(jù)時，作為聚類參數(shù)的相似性度量準(zhǔn)則的選 擇，是對獲得聚類結(jié)果評價的一個重要的因素。在聚類分析中主要 采用pears on相關(guān)系數(shù)和歐式距離作為相似性度量準(zhǔn)則。 本文采用 預(yù)處理過

25、的基因表達數(shù)據(jù)集試驗結(jié)果顯示相似度的選擇對結(jié)果影 響顯著，不同的聚類算法需要選擇不同的相似性度量準(zhǔn)則才能獲得更有效的聚類結(jié)果。針對距離作為相似性度量準(zhǔn)則的局限，提出一 種精確的相似性計算方法：基于比例的模式相似性度量。從模式相 似性的角度聚類生物數(shù)據(jù)，逐漸成為近年來數(shù)據(jù)挖掘在生物信息中 的研究焦點。參考文獻1brahma a, vilo j. gene expression data analysisj.febs letters, 2000, 480(1): 172jiang d, tang c, zhang a. clusteranalysis for gene expressi on data j. ieee tra nsacti ons on kno wledgeanddata engin eeri ng, 2004, 16(11): 13703amir b,friedman n,yakhini z. class