基于改進(jìn)標(biāo)記傳播算法的基因表達(dá)譜數(shù)據(jù)研究

葛芳，郭有強(qiáng)，王磊，馬程

(蚌埠學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系 安徽 蚌埠 233030)

基于改進(jìn)標(biāo)記傳播算法的基因表達(dá)譜數(shù)據(jù)研究

葛芳，郭有強(qiáng)，王磊，馬程

(蚌埠學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系 安徽 蚌埠 233030)

提出一種改進(jìn)的標(biāo)簽傳播算法，并將其應(yīng)用于基因表達(dá)譜數(shù)據(jù)分析中．首先使用概率矩陣表示基因表達(dá)數(shù)據(jù)，將少量樣本標(biāo)記為已知，同時(shí)定義一個(gè)標(biāo)記序列表示樣本的類(lèi)別屬性；然后通過(guò)迭代公式更新標(biāo)記序列，得到標(biāo)記序列的收斂解，并證明了該收斂解的唯一性；最后采用正負(fù)標(biāo)記的方式，根據(jù)標(biāo)記序列各分量的符號(hào)差異實(shí)現(xiàn)數(shù)據(jù)類(lèi)別的劃分．經(jīng)過(guò)癌癥數(shù)據(jù)集實(shí)驗(yàn)的驗(yàn)證，證明了提出的方法可以快速有效地實(shí)現(xiàn)基因表達(dá)數(shù)據(jù)的聚類(lèi)．

半監(jiān)督學(xué)習(xí)；概率轉(zhuǎn)移矩陣； 標(biāo)記傳播； 基因表達(dá)譜數(shù)據(jù)

DNA微陣列技術(shù)為腫瘤學(xué)提供了一種全新的研究手段．一次基因芯片實(shí)驗(yàn)可以獲得成千上萬(wàn)個(gè)基因的信息，而隨著DNA微陣列技術(shù)的進(jìn)步和儀器設(shè)備的更新，基因表達(dá)譜數(shù)據(jù)將不斷積累，這類(lèi)數(shù)據(jù)的主要特點(diǎn)是樣本少、維數(shù)高、冗余基因和噪聲多，因此，如何對(duì)這類(lèi)“新型”數(shù)據(jù)進(jìn)行分析，挖掘其中包含的有效信息，成為生物信息學(xué)研究的重點(diǎn)課題．

傳統(tǒng)的基因表達(dá)譜分析方法主要是對(duì)基因數(shù)據(jù)進(jìn)行信息基因選取或特征屬性提取后，再用相應(yīng)的分類(lèi)或聚類(lèi)方法對(duì)樣本進(jìn)行識(shí)別[1-2]．其中，聚類(lèi)是一種無(wú)監(jiān)督學(xué)習(xí)方法，傳統(tǒng)的聚類(lèi)方法，如K均值[3]、模糊C均值[4]和自組織映射[5]等，都要求數(shù)據(jù)呈球狀分布，且這些算法易陷入局部最優(yōu)．禤世麗[6]等人針對(duì)上述問(wèn)題，提出了基于粒子對(duì)(PPO)與差分進(jìn)化(DE)混合算法，并結(jié)合K-means進(jìn)行聚類(lèi).近年來(lái)，基于圖劃分理論的聚類(lèi)方法成為機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)．2001年，Meila和Shi[7]把圖的節(jié)點(diǎn)的相似性解釋為馬爾科夫鏈中的隨機(jī)游走，同時(shí)分析了這種隨機(jī)游走的概率轉(zhuǎn)移矩陣的特征向量，并提出了多個(gè)特征相似矩陣組合下的譜聚類(lèi)算法；2006年，Zhu[8]用高斯隨機(jī)場(chǎng)的方法處理半監(jiān)督學(xué)習(xí)問(wèn)題，提出了標(biāo)記傳播算法，并根據(jù)隨機(jī)游走對(duì)標(biāo)記傳播算法進(jìn)行了概率解釋?zhuān)?010年，Bai等人[9]將標(biāo)記傳播進(jìn)行了擴(kuò)展，提出了基于上下文分析的圖傳導(dǎo)算法，并將其應(yīng)用于圖像分割、形狀檢索和匹配等領(lǐng)域．

標(biāo)記傳播是一種基于圖的半監(jiān)督學(xué)習(xí)方法，它利用少量已標(biāo)記類(lèi)別的樣本，通過(guò)傳播標(biāo)記的方式來(lái)識(shí)別未知類(lèi)別的樣本．標(biāo)記傳播算法能在任意形狀的樣本空間中進(jìn)行聚類(lèi)，克服了傳統(tǒng)聚類(lèi)方法易陷入局部最優(yōu)的缺點(diǎn)，但原始標(biāo)記傳播算法迭代次數(shù)過(guò)大，每次迭代前都要重新標(biāo)記已知類(lèi)別的樣本，且最終的劃分準(zhǔn)則也并不明確．針對(duì)上述問(wèn)題，提出了一種改進(jìn)的LP算法，并應(yīng)用于實(shí)際的癌癥數(shù)據(jù)的分析中．癌癥數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果證明了該方法的有效性．

1 基因表達(dá)數(shù)據(jù)的概率轉(zhuǎn)移矩陣表示

(1)

其中，aij表示基因gj在樣本xi中的表達(dá)值．

(2)

其中，dij表示節(jié)點(diǎn)xi和xj之間的歐氏距離，σ是權(quán)重參數(shù)，通常，σ可以根據(jù)節(jié)點(diǎn)xi和xj的K個(gè)近鄰的平均距離來(lái)自適應(yīng)調(diào)整大小[10]，K是一個(gè)經(jīng)驗(yàn)值．顯然，對(duì)于任意的xi,xj和σ，有0≤Wij≤1，反映了節(jié)點(diǎn)xi和xj之間的親近程度，Wij越大，則節(jié)點(diǎn)xi和xj越有可能屬于同一類(lèi)．假設(shè)xi是一個(gè)已標(biāo)記的節(jié)點(diǎn)，那么從節(jié)點(diǎn)xi轉(zhuǎn)移到節(jié)點(diǎn)xj的概率為

(3)

其中，di=∑kWik為節(jié)點(diǎn)xi的度，表示與其連接的所有節(jié)點(diǎn)的邊權(quán)之和．因此，概率轉(zhuǎn)移矩陣可表示為

P=D-1W

(4)

2 標(biāo)記傳播算法

標(biāo)記傳播的步驟如下：

Step1: 傳播標(biāo)記，f=Pf；

Step2: 強(qiáng)化標(biāo)記數(shù)據(jù)，fL=YL；

Step3: 返回Step1，直到f收斂．

通過(guò)第一步，將已標(biāo)記樣本節(jié)點(diǎn)的標(biāo)記傳播至相鄰的節(jié)點(diǎn)；此外，在標(biāo)記的傳播過(guò)程中，為保證傳播過(guò)程的正確性，已知樣本的標(biāo)記值不變，用以保持標(biāo)記數(shù)據(jù)的強(qiáng)度；算法迭代終止后，標(biāo)記序列f包含了樣本的類(lèi)別信息．文獻(xiàn)[8]給出了標(biāo)記傳播算法的收斂解

(5)

其中，PUU和PUL是概率轉(zhuǎn)移矩陣P的子矩陣塊，即

(6)

因此，標(biāo)記傳播算法的解將收斂于一個(gè)固定解，需要指出的是，根據(jù)式(5)可以直接求出未知樣本的標(biāo)記．

3 改進(jìn)的標(biāo)記傳播算法

通過(guò)上述方法任意數(shù)據(jù)點(diǎn)xi都可以映射為相應(yīng)的實(shí)數(shù)值fi，但本文算法在每次迭代前都要重新標(biāo)記已知樣本，且由于標(biāo)記傳播過(guò)程和標(biāo)記強(qiáng)化過(guò)程的分離，造成算法迭代次數(shù)過(guò)大；同時(shí)，本文算法采用0-1標(biāo)記，需要選取適合的閾值對(duì)樣本進(jìn)行分類(lèi)，Zhu等人[8]使用的0.5閾值缺乏穩(wěn)定性，應(yīng)用于復(fù)雜數(shù)據(jù)時(shí)并不能取得很好的效果．

3.1 改進(jìn)的標(biāo)記傳播算法

令α表示標(biāo)記傳播和標(biāo)記強(qiáng)化的平衡參數(shù)，且滿(mǎn)足0<α<1，反映了數(shù)據(jù)點(diǎn)從其近鄰點(diǎn)獲取的標(biāo)記信息的比例，將參數(shù)α加入迭代公式，在t+1次迭代后，數(shù)據(jù)點(diǎn)xi的標(biāo)記為

(7)

其中，f0=(YL,0,…,0)，在每次迭代過(guò)程中，數(shù)據(jù)點(diǎn)從已標(biāo)記節(jié)點(diǎn)中獲取一部分標(biāo)記信息；同時(shí)，由于相似節(jié)點(diǎn)間的權(quán)重較大，數(shù)據(jù)點(diǎn)可以從其近鄰中獲取一部分標(biāo)記信息，當(dāng)傳播終止后，相似節(jié)點(diǎn)的分布情況也趨于一致．因此，迭代公式可以改寫(xiě)為

(8)

利用式(8)來(lái)更新每個(gè)數(shù)據(jù)的標(biāo)記，直至收斂．這里，并不采用原始LP算法中的0和1標(biāo)記，而采用正負(fù)標(biāo)記的方式，如對(duì)于兩類(lèi)問(wèn)題，將其中一類(lèi)的若干個(gè)樣本標(biāo)記為1，而另一類(lèi)的若干個(gè)樣本標(biāo)記為-1，對(duì)于最終的收斂結(jié)果，就能以零為分割點(diǎn)對(duì)未知類(lèi)別的樣本進(jìn)行劃分．

3.2 收斂性證明

本節(jié)將證明利用上述算法得到的f是收斂的，由式(8)可以得到是收斂的，由式(8)可以得到

(9)

由于Pij>0且∑jPij=1，根據(jù)Perron-Frobenius定理[11]，矩陣P的譜半徑小于1；同時(shí)，由于0<α<1，因此

(10)

(11)

其中，I為n×n的單位矩陣，因此，ft將收斂于

(12)

因此，本文算法的解也是收斂的．同樣，可以根據(jù)式(12)直接求出未知樣本的標(biāo)記．

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

選用兩組公開(kāi)的癌癥數(shù)據(jù)集：白血病數(shù)據(jù)(leukemia)，共52個(gè)樣本，其中24個(gè)樣本被確定為急性淋巴白血病(ALL)，28個(gè)被確定為急性粒細(xì)胞白血病(AML)，每個(gè)樣本含有12564個(gè)基因表達(dá)數(shù)據(jù)；結(jié)腸癌數(shù)據(jù)(coloncancer)，共62個(gè)樣本，其中22個(gè)樣本被確定為正常樣本，40個(gè)被確定為腫瘤樣本，每個(gè)樣本含有2000個(gè)基因表達(dá)數(shù)據(jù)．實(shí)驗(yàn)是在酷睿雙核主頻2.60GHz，內(nèi)存2G的計(jì)算機(jī)上運(yùn)行的．

癌癥基因表達(dá)譜數(shù)據(jù)的獲取過(guò)程十分復(fù)雜，所得到的數(shù)據(jù)含有大量的噪聲，同時(shí)每個(gè)樣本都記錄了組織細(xì)胞中所有可測(cè)基因的表達(dá)水平，但只有較少數(shù)基因包含與類(lèi)別相關(guān)的信息，因此，對(duì)數(shù)據(jù)進(jìn)行預(yù)處理是必要的，定義下式對(duì)基因表達(dá)譜數(shù)據(jù)進(jìn)行篩選

(13)

其中，max(i)，min(i)和mean(i)分別表示第i個(gè)基因于所有樣本當(dāng)中表達(dá)水平的最大值，最小值和平均值．T為給定的閾值．如果某個(gè)基因的表達(dá)情況符合式(13)便將該基因剔除．

4.2 白血病數(shù)據(jù)實(shí)驗(yàn)

將白血病數(shù)據(jù)的第1號(hào)樣本(ALL)標(biāo)記為1，第52號(hào)樣本(AML)標(biāo)記為-1，分別進(jìn)行5、10、50、200次迭代，更新每個(gè)樣本點(diǎn)的標(biāo)記，觀察標(biāo)記序列各分量的變化，結(jié)果如圖1所示：

圖1 白血病數(shù)據(jù)的標(biāo)記傳播過(guò)程 圖2 白血病數(shù)據(jù)樣本均值

圖1中，標(biāo)記序列的前24個(gè)分量對(duì)應(yīng)的是白血病數(shù)據(jù)集的ALL樣本，后28個(gè)分量對(duì)應(yīng)AML樣本．從圖1中可以看到，當(dāng)進(jìn)行5次迭代后，ALL樣本的標(biāo)記都大于零，而AML樣本的標(biāo)記都小于零，所有樣本被正確的劃分為兩類(lèi)，說(shuō)明該方法可以快速且有效的實(shí)現(xiàn)樣本類(lèi)別的劃分；同時(shí)，圖1(c)和(d)變化不明顯，即表示較少次數(shù)的迭代便可得到最終結(jié)果．另外，ALL樣本中，第3號(hào)樣本的分布明顯不同于其他樣本，AML樣本中，第48、49、50、51和52號(hào)樣本也不同于其他樣本，這是由數(shù)據(jù)的分布特點(diǎn)決定的，圖2是白血病數(shù)據(jù)集中各樣本均值．

4.3 結(jié)腸癌數(shù)據(jù)實(shí)驗(yàn)

將結(jié)腸癌數(shù)據(jù)的第1號(hào)樣本(正常組織樣本)標(biāo)記為1，第62號(hào)樣本(腫瘤組織樣本)標(biāo)記為-1，同樣分別進(jìn)行5、10、50、200次迭代，結(jié)果如圖3所示.

圖3 結(jié)腸癌數(shù)據(jù)的標(biāo)記傳播過(guò)程 圖4 異常樣本被標(biāo)記為已知的迭代結(jié)果

圖3中，標(biāo)記序列的前22個(gè)分量對(duì)應(yīng)的是結(jié)腸癌數(shù)據(jù)集的正常組織樣本，后40個(gè)分量對(duì)應(yīng)腫瘤組織樣本．從圖3中可以看到，當(dāng)經(jīng)過(guò)5次迭代后，兩類(lèi)樣本標(biāo)記的區(qū)別并不明顯，但經(jīng)過(guò)10次迭代后，就可以看出兩類(lèi)樣本的標(biāo)記的差異性，在正常組織樣本中，第18和20號(hào)樣本被錯(cuò)誤標(biāo)記，而在腫瘤組織樣本中，第52、55和58號(hào)樣本被錯(cuò)誤標(biāo)記，分類(lèi)準(zhǔn)確率達(dá)到91.94%，實(shí)際情況中，這些樣本中含有較多的偏離值和異常點(diǎn)；同時(shí)，進(jìn)行50次和200迭代后，樣本標(biāo)記的變化已經(jīng)不明顯，同樣說(shuō)明了該方法可以快速實(shí)現(xiàn)標(biāo)記序列的收斂．

為了觀察初始標(biāo)記點(diǎn)對(duì)最終迭代結(jié)果的影響，分別將結(jié)腸癌數(shù)據(jù)中被錯(cuò)誤標(biāo)記的第18、55和58號(hào)樣本標(biāo)記為已知，結(jié)果如圖4所示．

圖4(a)中僅標(biāo)記了第1和62號(hào)樣本；圖4(b)除標(biāo)記第1和62號(hào)樣本外，同時(shí)將第18號(hào)樣本標(biāo)記為1；圖4(c)、(d)除標(biāo)記第1和62號(hào)樣本外，分別將第55號(hào)和58號(hào)樣本標(biāo)記為-1．由圖4(b-c)可知，當(dāng)將第18或55號(hào)樣本標(biāo)記為已知，那么與第18或55樣本相似的樣本，其標(biāo)記值也趨向于與第18或55樣本相似(實(shí)際表現(xiàn)為樣本標(biāo)記值的絕對(duì)值減小)．由圖4(d)可知，當(dāng)將第58號(hào)樣本標(biāo)記為已知，第13至22號(hào)樣本全部被錯(cuò)誤標(biāo)記，同時(shí)第1至12號(hào)樣本的標(biāo)記值的絕對(duì)值減小，這同樣是由于在標(biāo)記傳播過(guò)程中，某個(gè)樣本的標(biāo)記是根據(jù)其近鄰樣本點(diǎn)的標(biāo)記進(jìn)行更新的．因此得出結(jié)論，在試驗(yàn)中，若把異樣表達(dá)的樣本標(biāo)記為已知，與該樣本表達(dá)相似的樣本趨向于已標(biāo)記的異樣表達(dá)樣本，便會(huì)出現(xiàn)樣本被錯(cuò)誤標(biāo)記的現(xiàn)象．

4.4 對(duì)比驗(yàn)證

為進(jìn)一步驗(yàn)證該方法的正確性，設(shè)計(jì)了兩組對(duì)比實(shí)驗(yàn)：

第一組實(shí)驗(yàn)：將該方法與局部線(xiàn)性嵌入(LLE)算法[12-13]和NJW譜聚類(lèi)算法[14]進(jìn)行對(duì)比．LLE是一種非線(xiàn)性特征提取算法，先以L(fǎng)LE進(jìn)行特征提取，再用KNN對(duì)樣本進(jìn)行分類(lèi)；NJW算法采用規(guī)范化相似矩陣的前K個(gè)最大特征值對(duì)應(yīng)的特征向量作為數(shù)據(jù)的特征表示，再用K均值等對(duì)特征空間的樣本點(diǎn)進(jìn)行聚類(lèi)．結(jié)果如表1所示：

表1 本文方法與基于圖的方法的實(shí)驗(yàn)結(jié)果比較

由表1可知，從準(zhǔn)確率方面，本文方法明顯優(yōu)于另外兩種基于圖的方法，LLE算法是一種有效的可視化方法，但要求數(shù)據(jù)服從流形分布，其提取的特征并不具有很強(qiáng)的分類(lèi)能力；NJW算法屬于無(wú)監(jiān)督學(xué)習(xí)，提取的特征向量未必能反映數(shù)據(jù)結(jié)構(gòu)；而本文方法利用已知樣本的類(lèi)別標(biāo)記對(duì)未知樣本的標(biāo)記進(jìn)行傳播，在傳播過(guò)程中，某個(gè)樣本的標(biāo)記是根據(jù)其近鄰樣本點(diǎn)的標(biāo)記進(jìn)行更新的，最后得到的收斂結(jié)果也更符合原始數(shù)據(jù)分布的特點(diǎn)．同時(shí)，在時(shí)間效率上，本文方法并不具有明顯的優(yōu)勢(shì)，這是因?yàn)檫@幾種方法都是利用構(gòu)圖的方法將高維樣本映射到低維空間，構(gòu)造的矩陣規(guī)模是相同的．

第二組實(shí)驗(yàn)：將本文方法與傳統(tǒng)的S2N_KNN法[1]和CLUSTER_S2N[4]進(jìn)行對(duì)比，S2N_KNN以“信噪比”為指標(biāo)選取特征基因，再用K-近鄰(KNN)分類(lèi)器對(duì)樣本進(jìn)行分類(lèi)；CLUSTER_S2N先用K均值將數(shù)據(jù)聚類(lèi)，再以“信噪比”選取特征基因，最后用支持向量機(jī)(SVM)實(shí)現(xiàn)樣本的分類(lèi)．結(jié)果如表2所示：

表2 本文方法與傳統(tǒng)方法的實(shí)驗(yàn)結(jié)果比較

由表2可知，無(wú)論從準(zhǔn)確率還是運(yùn)算效率等方面，本文方法都優(yōu)于另外兩種傳統(tǒng)方法，由于基因之間普遍存在相關(guān)性，傳統(tǒng)方法以降維來(lái)提取特征基因勢(shì)必會(huì)丟失部分含有分類(lèi)信息的基因，而本文方法將樣本數(shù)據(jù)作為高維空間中的點(diǎn)，所構(gòu)造的概率轉(zhuǎn)移矩陣反映了樣本之間的關(guān)系，使得原來(lái)的樣本分類(lèi)信息完全映射到低維的概率轉(zhuǎn)移矩陣中．同時(shí)，在時(shí)間效率上，提出的方法同樣優(yōu)于后兩種方法，這是因?yàn)閭鹘y(tǒng)方法在前期處理中對(duì)高維數(shù)據(jù)進(jìn)行復(fù)雜運(yùn)算，進(jìn)行一次甚至多次降維處理，而提出的方法首先以樣本為節(jié)點(diǎn)構(gòu)圖，其低樣本特性決定了構(gòu)造的矩陣規(guī)模較小，從而具有較低的運(yùn)算復(fù)雜度，有利于基因表達(dá)數(shù)據(jù)的快速分類(lèi)．

5 結(jié) 語(yǔ)

基于圖的半監(jiān)督學(xué)習(xí)是當(dāng)前模式識(shí)別領(lǐng)域的研究熱點(diǎn)．提出一種改進(jìn)的標(biāo)記傳播算法，本文算法通過(guò)引入標(biāo)記傳播過(guò)程和標(biāo)記強(qiáng)化過(guò)程的平衡參數(shù)，克服了傳統(tǒng)標(biāo)記傳播算法迭代次數(shù)過(guò)大和重復(fù)標(biāo)記數(shù)據(jù)點(diǎn)的缺點(diǎn)；同時(shí)在數(shù)據(jù)類(lèi)別劃分時(shí)使用正負(fù)標(biāo)記的方式，避免了采用0-1標(biāo)記時(shí)閾值選取的不確定性．通過(guò)癌癥數(shù)據(jù)的實(shí)驗(yàn)，證明了該方法可快速且有效地實(shí)現(xiàn)基因表達(dá)譜數(shù)據(jù)的聚類(lèi)．

[1]GULOBTR,SLONIMDK,TAMAYOP,etal.Molecularclassificationofcancer:classdiscoveryandclasspredictionbygeneexpressionmonitoring[J].Science, 1999, 286(5439):531-537.

[2]KANCHERLAK,MUKKAMALAS.FeatureselectionforlungcancerdetectionusingSVMbasedrecursivefeatureeliminationmethod[J].MachineLearningandDataMininginBioinformatics, 2012, 7246:168-176.

[3] 禤浚波, 吳小霞, 王珍珍,等. 基于粒子對(duì)和極值優(yōu)化的基因聚類(lèi)混合算法研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2011, 28(10):3675-3677，3680.

[4]TARIL,BARALC,KIMS.Fuzzyc-meansclusteringwithpriorbiologicalknowledge[J].JournalofBiomedicalInformatics, 2009, 42(1):74-81.

[5]PATTERSONAD,LIH,EICHLERGS,etal.UPLC-ESI-TOFMS-basedmetabolomicsandgeneexpressiondynamicsinspectorself-organizingmetabolomicmapsastoolsforunderstandingthecellularresponsetoionizingradiation[J].AmericanChemicalSociety, 2008, 80(3):665-674.

[6] 禤世麗,楊秋葉，張超英,等. 基于粒子對(duì)和差分進(jìn)化的基因表達(dá)數(shù)據(jù)聚類(lèi)[J]. 計(jì)算機(jī)應(yīng)用研究, 2012, 29(7):2484-2487.

[7]MELIAM,SHIJin-bo.Learningsegmentationbyrandomwalks[J].InAdvancesinNeuralInformationProcessing，2000, 10(2):873-879.

[8]ZHUXiao-jin.Semi-Supervisedlearningwithgraphs[D].Doctoraldissertation,CarnegieMellonUniv,CMU-LTI-05-192,2005.

[9]BAIXiang,YANGXing-wei,LATECKILJ,etal.Learningcontext-sensitiveshapesimilaritybygraphtransduction[J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 2010, 32(5):861-874.

[10]ZELNIK-MANORL,PERONAP.Self-tuningspectralclustering[J].AdvancesinNeuralInformationProcessingSystems, 2004, 17(2):1601-1608.

[11]GOLUBGH,VANLOANCF.Matrixcomputatio[M].Baltimore:TheJohnsHopkinsUniversityPress, 1996.

[12]PILLATIM,VIROLIC.Supervisedlocallylinearembeddingforclassication[A].anapplicationtogeneexpressiondataanalysis[C].Proceedingsof29thAnnualConferenceoftheGermanClassicationSociety(GfKl2005), 2005.15-18.

[13]ZHAOLing-xiao,ZHANGZheng-yue.Supervisedlocallylinearembeddingwithprobability-baseddistanceforclassification[J].ComputersandMathematicswithApplications, 2009, 57: 919-926.

[14]NGAY,JORDANMI,WEISSY.Onspectralclustering：analysisandanalgorithm[C].DIETTERICHTG,BECKERS,GHAHRAMANIZ.AdvancesinNeuralInformationProcessingSystems,Cambridge,MA:MITpress, 2002,849-85.

[責(zé)任編輯：王軍]

The analysis of gene expression profiles based on improved label propagation algorithm

GE Fang，GUO Youqiang, WANG Lei, MA Cheng

(Department of Computer Science and technology, Bengbu College, Bengbu 233030, China)

In this paper, an improved label propagation algorithm was proposed and introduced into the analysis of gene expression profiles. First, the probability transition matrix was constructed with gene expression profiles. Meanwhile, the label sequence which indicates the class information was defined and several samples were marked as labeled data. Then, the label sequence was updated by an iterative formula and the convergence solution of the label sequence was obtained, which was proved to be the unique solution. Finally, the clustering problem was solved by using plus-minus label which was on the basis of the signs of the label sequence. Experiments on the cancer data demonstrate our method is feasible and effective.

semi-supervised learning; probability transition matrix; label propagation; gene expression profile data

2015-03-02

安徽省自然科學(xué)基金資助項(xiàng)目(No.11040606M151)；蚌埠學(xué)院自然科學(xué)基金資助項(xiàng)目(No.2014ZR26，No.2013ZR06)

葛芳(1986-), 女, 安徽亳州人, 蚌埠學(xué)院助教, 碩士研究生, 主要從事模式識(shí)別、計(jì)算生物學(xué)的研究; 郭有強(qiáng)(1966-), 男, 蚌埠學(xué)院教授,博士, 碩士生導(dǎo)師, 主要從事為數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)的研究.

TP 18

A

1672-3600(2015)06-0063-06