非負(fù)矩陣分解算法及其在生物信息學(xué)中的應(yīng)用研究

1、CN43 1258/TP ISSN1007 130X計算機工程與科學(xué)COMPUTERENGINEERING&SCIENCE2010年第32卷第8期 Vol 32,No 8,2010文章編號:1007 130X(2010)08 0117 07*非負(fù)矩陣分解算法及其在生物信息學(xué)中的應(yīng)用研究ResearchontheAdvancesofNonnegativeMatrixFactorizationandItsApplicationinBioinformatics石金龍,駱志剛SHIJin long,LUOZhi gang(國防科學(xué)技術(shù)大學(xué)計算機學(xué)院,湖南長沙410073)(SchoolofCo

2、mputerScinece,NationalUniversityofDefenseTechnology,Changsha410073,China)摘 要:非負(fù)矩陣分解是近年來快速發(fā)展的一類機器學(xué)習(xí)算法,能夠?qū)崿F(xiàn)對高維數(shù)據(jù)的維度規(guī)約及局部特征提取,在諸多生物信息問題的分析與處理中得到了廣泛應(yīng)用,并衍生出一系列實用算法。本文系統(tǒng)分析了非負(fù)矩陣分解的數(shù)學(xué)理論基礎(chǔ)及其特有的局部表達屬性,綜述了標(biāo)準(zhǔn)非負(fù)矩陣分解與各種衍生算法的發(fā)展歷程及算法初始化與參數(shù)選取方法的研究進展,并從序列特征分析、表達模式與功能模塊識別、生物醫(yī)學(xué)文獻挖掘等幾個方面總結(jié)了非負(fù)矩陣分解算法在生物信息學(xué)領(lǐng)域的應(yīng)用成果。最后,指出了非負(fù)

3、矩陣分解算法研究及其應(yīng)用于生物信息處理所面臨的問題,分析和預(yù)測了可能的發(fā)展方向。Abstract:NonnegativeMatrixFactorization(NMF)isarapidlydevelopingparts basedmachinelearningalgorithm,whichcanbeusedasatoolofdimensionalityreductionandcanidentifythelocalfeaturesforhigh dimensionaldata.NMFhasabroadapplicationintheanalysisandinterpretationofbiolo

4、gicaldata,andanumberofpracticalalgorithmshavebeenderivedfromit.ThispapersystematicallyanalyzesthemathematicalfoundationofNMFanditsadvantagesfortherepresen tationoflocalfeatures,andsurveystheadvancesofdifferentvarieties,initializationandparameterselectionfortheNMFal gorithm.Also,itsapplicationinbioin

5、formaticsisreviewedandclassifiedintoseveralcategories.Finally,thefuturedirec tionsoftheNMFresearchandapplicationareanalyzedandpredicted.關(guān)鍵詞:非負(fù)矩陣分解;生物信息學(xué);局部特征Keywords:nonnegativematrixfactorization;bioinformatics;localfeaturedoi:10.3969/j.issn.1007 130X.2010.08.032中圖分類號:TP301.6文獻標(biāo)識碼:A海量的基因表達數(shù)據(jù)。截止到200

6、9年3月,美國國家生物技術(shù)信息中心(NCBI)的GEO數(shù)據(jù)庫已經(jīng)包含多個物種的310404組樣本數(shù)據(jù),記錄條數(shù)每天都在增加中。這些數(shù)據(jù)中蘊藏著生命活動的基本規(guī)律,深入分析這些數(shù)據(jù),有助于進一步認(rèn)識和理解紛繁多樣的表現(xiàn)型下隱藏的調(diào)控機理、作用機制,有助于人們研究各種疾病的病變機理、確定藥物的作用靶、輔助新藥的研制等,最終幫助人們理解生命的奧秘。針對這些海量的基因表達數(shù)據(jù)設(shè)計新的算法,識別蘊藏的各種特征,并給出合理解釋,是當(dāng)前生物信息學(xué)研究的主題,來自不同學(xué)科的研究者提出了各種各樣的計算方法。1 引言以芯片技術(shù)為代表的高通量技術(shù)的誕生,標(biāo)志著基因組研究進入了新的水平。芯片實驗?zāi)軌蛲瑫r測量成千上萬個

7、基因的表達水平,利用這一技術(shù),研究者可以獲得細胞在生理、發(fā)育過程中各個基因表達水平的動態(tài)變化信息,也可以監(jiān)控外部環(huán)境變化時細胞內(nèi)部各個基因表達水平的變化狀況,這就提供了一種量化細胞活動過程的有效途徑。因此,芯片技術(shù)在生命科學(xué)的研究中得到了廣泛應(yīng)用,產(chǎn)生了*收稿日期:2009 06 19;修訂日期:2009 09 21基金項目:國家自然科學(xué)基金資助項目(60673018);國家863計劃資助項目(2007AA01Z106)作者簡介:石金龍(1980 ),男,河南唐河人,博士生,研究方向為生物信息學(xué);駱志剛,教授,博士生導(dǎo)師,研究方向為并行計算、生物信息學(xué)等。通訊地址:410073湖南省長沙市國防

8、科學(xué)技術(shù)大學(xué)計算機學(xué)院博士生隊;Tel:(0731)84575835E mail:jlshi.nudtAddress:DoctoralBrigade,SchoolofComputerScinece,NationalUniversityofDefenseTechnology,Changsha,Hunan410073,P.R.China例如,通過聚類技術(shù)識別共表達或共調(diào)控的基因,確定基因作用的功能模塊;利用Boolean、微分方程、Bayes統(tǒng)計推斷等理論建立基因作用的數(shù)學(xué)模型并在此基礎(chǔ)上建立基因作用網(wǎng)絡(luò)等等。數(shù)學(xué)上,芯片實驗產(chǎn)生的數(shù)據(jù)一般表現(xiàn)為N M的矩陣,其中N表示基

9、因數(shù)目,M表示樣本數(shù)目(如基于時間順序的采樣點、不同的實驗條件、組織類型等),M<<N,即樣本的數(shù)目遠遠小于基因數(shù)目。針對這一特點,奇異值分解(SVD)1及各種成分分析技術(shù)24先后被用于芯片實驗數(shù)據(jù)的分析和處理,這些方法能夠有效地降低表達數(shù)據(jù)的維數(shù),識別數(shù)據(jù)中蘊含的全局特征,但卻難以識別細胞活動過程中特定條件下存在的局部特征。Lee和Seung5提出非負(fù)矩陣分解算法(NMF),并將其應(yīng)用于人臉識別和文本挖掘中。NMF的最大優(yōu)點是能夠在一定程度上識別數(shù)據(jù)的局部特征,定量地刻畫局部與整體之間潛在的、可加的非線性組合關(guān)系。近年來,NMF已經(jīng)被廣泛地應(yīng)用于圖像處理、人臉識別、文本信息處理、

10、音頻處理等多個領(lǐng)域,產(chǎn)生了大量快速實用的有效算法,這就使得NMF特別適合于分析大規(guī)模的基因芯片數(shù)據(jù)。許多研究者利用NMF能夠分析和處理生物信息學(xué)領(lǐng)域的多種問題,包括基因表達數(shù)據(jù)聚類、調(diào)控模式及功能模塊識別、生物醫(yī)學(xué)文本挖掘、序列模式與基因功能分析等,取得了諸多有意義的研究成果。結(jié)合NMF算法的最新發(fā)展,對這些應(yīng)用及成果進行系統(tǒng)的綜述是很必要的,這將有助于深入理解NMF算法分析結(jié)果的生物學(xué)意義,進一步拓展NMF在生物信息學(xué)領(lǐng)域的應(yīng)用范圍。本文對NMF算法及其在生物信息處理中的應(yīng)用進行綜述,回顧其發(fā)展歷程并對算法的各種屬性進行分析,重點關(guān)注NMF算法在分析和解釋大規(guī)模生物數(shù)據(jù)中的應(yīng)用。本文首先回顧

11、NMF算法的發(fā)展歷程,分析NMF的各種變形和快速算法,闡述NMF算法的特有性質(zhì);然后,綜述NMF算法在生物信息學(xué)中的應(yīng)用并進行分類,針對每一類應(yīng)用,說明NMF分析和解釋基因表達數(shù)據(jù)的有效性;最后,總結(jié)全文,分析NMF算法應(yīng)用于生物信息處理的局限性,討論需要進一步研究和解決的問題,并給出可行的解決思路與方法。有直觀的物理涵義,即整體可以劃分為多個部分的可加的非線性組合。因此,近年來NMF算法獲得了極大的關(guān)注,從概念體系到實現(xiàn)方法都得到了進一步完善和發(fā)展,產(chǎn)生了一系列快速、高效的實用算法。圖1表示應(yīng)用NMF、VQ和PCA于同一幅人臉圖像進行數(shù)據(jù)降維后所得到的結(jié)果,其中圖1a圖1d分別表示原始圖像、

12、NMF、VQ和PCA降維處理后的圖像?？梢钥闯?NMF能夠獲得局部化的特征,而VQ和PCA只能獲得全局特征5。圖1 NMF與VQ、PCA比較2.1 非負(fù)矩陣分解算法的產(chǎn)生與發(fā)展NMF算法最早可追溯到1994年發(fā)表在 Environmet rics!上的一篇文章6,該文基于因子分析導(dǎo)出正矩陣分解(PositiveMatrixFactorization,簡稱PMF)的概念,提出了一種加權(quán)最小二乘分解算法,并將其應(yīng)用于環(huán)境數(shù)據(jù)分析。處理結(jié)果表明,PMF算法能夠得到優(yōu)于PCA、FA兩種算法的分析結(jié)果。但是,由于應(yīng)用領(lǐng)域較偏,同時實現(xiàn)算法過于復(fù)雜,因此該文并未受到廣泛的關(guān)注。Lee和Seung5于199

13、9年在 Nature!上正式提出NMF算法的基本概念框架,從理論上簡潔地描述和定義了算法的目標(biāo)函數(shù),并結(jié)合非負(fù)交替最小二乘法7和凸編碼算法8給出了簡便實用的計算方法,最后將其應(yīng)用于人臉識別和文本特征提取中。通過將NMF算法與PCA、VQ算法進行比較(如圖1所示),分析了NMF算法具有的基于部分、局部表達等良好特性。2001年,他們提出了NMF的兩種簡化算法9:一類以最小化歐式距離為目標(biāo)函數(shù),另一類以最小化Kullback Liebler散度為目標(biāo)函數(shù),兩類算法都采用多重迭代梯度下降策略,同時進一步從理論上證明了這兩種計算方法的收斂性。Lee和Seung的工作奠定了標(biāo)準(zhǔn)NMF算法的基本框架,使得

14、NMF成為一個實用、高效的計算方法。10為得到更局部化的分解,Li提出了局部非負(fù)矩陣分解算法(LocalNonnegativeMatrixFactorization,簡稱LNMF),通過對Kullback Liebler散度目標(biāo)函數(shù)施加額外的約束以最小化基向量的個數(shù),并減少基向量之間的冗余。基于人臉重構(gòu)和識別的數(shù)值實驗表明,LNMF優(yōu)于標(biāo)準(zhǔn)NMF和PCA。Wang等人11針對LNMF應(yīng)用于分類問題時無法編碼判別信息的缺點,將Fisher線性判別條件引入NMF,提出FNMF并證明了算法的收斂性。Hoyer12結(jié)合NMF和稀疏編碼提出了非負(fù)稀疏編碼(Non negative2 非負(fù)矩陣分解矩陣分解

15、是許多計算方法的基礎(chǔ),比如常用的統(tǒng)計分析方法:主成分分析(PrincipleComponentAnalysis,簡稱PCA)、獨立成分分析(IndependentComponentAnalysis,簡稱ICA)、因子分析(FactorAnalysis,簡稱FA)、矢量量化(VectorQuantization,簡稱VQ),包括奇異值分解(SingularValueDecomposition,簡稱SVD)及本文所述的NMF等,這些算法的共同點都是通過將一個高維的矩陣分解為兩個或多個低維矩陣的乘積,實現(xiàn)維度規(guī)約,方便于在一個低維空間研究高維數(shù)據(jù)的性質(zhì)。NMF與其它方法的不同之處在于,它將原始給定的

16、非負(fù)矩陣近似分解為兩個非負(fù)矩陣的乘積,即NMF保證分解所得矩陣的每一元素都是正值,從而基于局部特征獲得對原數(shù)據(jù)的可加表達。NMF分解具有局部性、部分表達等優(yōu)于其它同類算法的獨特性質(zhì),具SparseCoding,簡稱NNSC),并給出了簡單有效的乘法規(guī)則。在此基礎(chǔ)上,進一步定義稀疏度的量化指標(biāo),增加約束條件以控制標(biāo)準(zhǔn)NMF算法分解的稀疏性,通過顯式控制因子矩陣的稀疏度獲取更局部化的分解13。Theis等人14進一步證明了稀疏NMF算法分解結(jié)果的唯一性。Guillamet等15提出了加權(quán)非負(fù)矩陣分解,將其與標(biāo)準(zhǔn)NMF、PCA算法進行了分析、比較,在此基礎(chǔ)上結(jié)合三種算法構(gòu)造了一個專用于圖像分類的分類

17、器。Ding等人16研究了對稱NMF,將一個對稱非負(fù)矩陣近似分解為一個對稱非負(fù)矩陣與其轉(zhuǎn)置的乘積,證明了對稱NMF與核k means聚類、基于拉普拉斯的譜聚類相互之間的等價性。他們還進一步提出三因子非負(fù)矩陣分解算法17,針對正交約束提出新的迭代更新規(guī)則,并證明了其收斂性。Pascual Mon tano等18通過定義一個光滑#矩陣以顯式控制分解的稀疏性,提出了非光滑矩陣分解算法。針對人臉識別的應(yīng)用表明,該算法能夠更好地提取局部特征。Cichocki和Zdunek19等提出了多重非負(fù)矩陣分解算法,將給定矩陣分解為一系列非負(fù)矩陣的乘積。Wang等20將對基因表達數(shù)據(jù)的不確定估計引入NMF算法的更新

18、規(guī)則,提出最小二乘NMF以識別基因之間的功能關(guān)系。Pascual Montano等人21開發(fā)了一個基于NMF的分析工具,能夠用于基因表達數(shù)據(jù)的聚類、蛋白序列分析及醫(yī)學(xué)文本挖掘等。NMF能夠獲得二維矩陣的部分表達,能夠有效地學(xué)習(xí)矩陣數(shù)據(jù)中潛在的局部特征,因此也有研究者試圖將這一思路拓展到高維張量數(shù)據(jù)的處理。Shashua等22提出了非負(fù)張量分解的概念,給出了一種梯度下降算法并應(yīng)用于人臉識別。期刊 ComputationalIntelligenceandNeuro science!在2008年還推出專刊介紹NMF和NTF算法的研究進展。作為一種較新的計算方法,NMF尚處于不斷發(fā)展與完善之中,隨著研

19、究的深入和應(yīng)用領(lǐng)域的拓展,更多基于NMF的新的擴展算法將會進一步涌現(xiàn)。定因子矩陣W和H。由于目標(biāo)函數(shù)僅分別對W或H為凸函數(shù),因此只能確定問題的局部最優(yōu)解。針對所提出的兩類目標(biāo)函數(shù),Lee和Seung9分別提出了相應(yīng)的乘法更新算法。對第一類目標(biāo)函數(shù),迭代規(guī)則為:(WTV)au(VHT)iaHau(Hau,W(Wiaia(WTWH)au(WHHT)ia對于第二類目標(biāo)函數(shù),迭代規(guī)則為:Hau(HauWiaViu/(WH)iukWkaWia(WiauHauViu/(WH)iuvHavLee和Seung證明了每次迭代后相應(yīng)的目標(biāo)函數(shù)是非增的。盡管并沒有證明NMF收斂于穩(wěn)定點,但由于上述迭代規(guī)則定義清晰,

20、易于實現(xiàn),且在實際應(yīng)用中表現(xiàn)良好,因此得到了廣泛應(yīng)用,一度成為求解NMF的標(biāo)準(zhǔn)算法。隨著研究的深入,標(biāo)準(zhǔn)NMF算法暴露出一些缺點,如無法收斂至穩(wěn)定點23,收斂速度也不盡如人意;難以選定合適k值;計算結(jié)果依賴于初始條件,只能獲得局部最優(yōu)解;對原始矩陣的分解結(jié)果稀疏性不佳,得到的基向量之間存在冗余等。針對這些問題,許多學(xué)者提出了一系列的算法以改進和擴展標(biāo)準(zhǔn)NMF算法。Hans24導(dǎo)出了有關(guān)NMF分解唯一性的幾個定理,還進一步討論了噪音對NMF的影響。Lin25基于投影梯度方法提出兩種NMF迭代算法,保證迭代速度和標(biāo)準(zhǔn)NMF算法相當(dāng)?shù)臈l件下獲得更好的收斂性。Zdunek等26基于Amarialpha

21、 散度構(gòu)造新的目標(biāo)函數(shù),并提出二階擬牛頓算法以減少迭代次數(shù)。他們進一步利用約束二階優(yōu)化方法實現(xiàn)NMF分解,獲得了更快的收斂速度27。Liu等28基于alpha 散度構(gòu)造NMF的目標(biāo)函數(shù),提出兩種更新規(guī)則并將其應(yīng)用于癌癥表達數(shù)據(jù)的分類。還有一些研究者從分析NMF的幾何意義入手,試圖提出效率更高的迭代策略。Donoho29分析了NMF的幾何意義,即求正象限中的單純錐,并討論了NMF算法的分解唯一性問題。Chu和Lin30提出基于數(shù)據(jù)點的近似凸錐包實現(xiàn)NMF。Bradley31基于幾何框架提出了一種新的迭代方法,還分析了NMF的不適定性(Ill Posedness),同時指出NMF并不適合于某些問題

22、的求解。考慮到NMF在處理大規(guī)模數(shù)據(jù)集時的計算密集性,也有一些研究者試圖優(yōu)化NMF的實現(xiàn),如Okun和Priisalu32發(fā)現(xiàn),通過對原始數(shù)據(jù)進行特征縮放,如對數(shù)據(jù)進行歸一化,NMF能夠得到更快的收斂速度。Kompass33在Lee和Seung的基礎(chǔ)上考慮更一般的參數(shù)化散度作為目標(biāo)函數(shù),提出二次收斂速度更快的更新規(guī)則,并基于最大期望值理論框架利用輔助函數(shù)給出了收斂性證明。2.2 非負(fù)矩陣分解的理論與計算方法2.2.1 問題描述給定非負(fù)矩陣Vn m,NMF的目標(biāo)是尋找兩個適當(dāng)?shù)姆秦?fù)矩陣因子Wn k、Hk m,使得:VW H通常k<m,k<n。于是,NMF實現(xiàn)了對原始矩陣的維度規(guī)約和信

23、息壓縮。2.2.2 計算過程基于之前的問題描述,NMF本質(zhì)上是一個帶約束的非線性規(guī)劃問題。根據(jù)刻畫原始矩陣和因子矩陣乘積近似程度的不同尺度,Lee和Seung基于歐氏距離定義為:%V-WH%2=9提出了兩類目標(biāo)函數(shù)。一個-WijHij)2&(Vijij2.2.3 k值選取與初始化在NMF分解中,k值的選取非常關(guān)鍵,它直接影響到分解結(jié)果及所給出的物理解釋的合理性。但是,k值的確定并沒有成熟或通用的方法。研究者或基于經(jīng)驗,或嘗試通過數(shù)值預(yù)處理選用合理的k值。Kim和Tidor34通過初步的試算,并結(jié)合奇異值分解考慮最小根均方差確定k值,該文選用k=50分析酵母的300組芯片表達數(shù)據(jù)。Mon

24、另一個目標(biāo)函數(shù)基于廣義Kullback Liebler散度定義為:D(V%WH)=&(Vijijlg(V-Vij+(WH)ij)(WH)ij可以證明,兩個目標(biāo)函數(shù)對矩陣W或矩陣H都是凸函數(shù),并且在V=WH時取得最小值。因此,NMF的實現(xiàn)轉(zhuǎn)換為:在約束W0,H0的條件下,最小化目標(biāo)函數(shù)并確ti35基于重采樣技術(shù)提出了一致聚類方法,用于刻畫聚類算法多次運行結(jié)果的一致性,并結(jié)合NMF對初始條件的敏感性評估所得聚類結(jié)果的穩(wěn)定性。在此基礎(chǔ)上,Brunet等36為一致性聚類增加一個量化指標(biāo),通過對分解魯棒性的評估確定合理的k值?；谶@種思路,結(jié)合必要的背景知識,他們將NMF算法應(yīng)用于白血病、神經(jīng)瘤

25、等基因表達數(shù)據(jù)集的分析,準(zhǔn)確識別出相關(guān)的腫瘤亞類。NMF屬于一種局部最優(yōu)的迭代算法,初始值的選取對其收斂速度和計算結(jié)果有著重要影響。選擇接近極值點的初值可以加快算法的收斂速度,而對于多極值問題,不合適的初值將使得算法終止于局部極值點,得不到全局最優(yōu)的結(jié)果。NMF算法的運行是通過對因子矩陣W和H的反復(fù)更新獲取的,Lee和Seung利用0和1之間的均勻分布獲得W和H的初始值。這種方法沒有任何傾向性,易于實現(xiàn),能夠在多次運行中得到目標(biāo)函數(shù)最小的局部最優(yōu)解。Wild37提出基于球心K Means方法計算矩陣W的初始值,并進一步考慮分解的誤差提出了確定k值的規(guī)則。這一方法所得的分解誤差遠小于隨機初始化方

26、法,同時還能夠有效地確定k值,但缺點是計算量過大,難以應(yīng)用于大規(guī)模的數(shù)據(jù)集處理。Russell等人38比較了隨機初始化與K means初始化的優(yōu)缺點,提出了四種新的初始化方法:第一種稱之為SVD 質(zhì)心初始化,通過對原始矩陣的低維SVD分解所得因子進行質(zhì)心分解得到W的初始值;第二種是隨機Acol初始化,通過隨機選取矩陣V中的任意p列,取平均值作為W的初始值;后兩種分別是隨機C初始化和共生矩陣初始化,主要通過對V的變換實現(xiàn)。數(shù)據(jù)實驗表明,隨機Acol初始化計算代價最低,而SVD 質(zhì)心初始化的分解誤差最小。Kim等人39對圖像屬性進行分層聚類(HC),通過定義刻畫子矩陣行向量的相似性指標(biāo)(Close

27、nesstoRank One,簡稱CRO)實現(xiàn)對NMF算法的初始化并確定k值,獲得了局部性更好的分解。文獻40系統(tǒng)地探討了基于聚類實現(xiàn)結(jié)構(gòu)化NMF初始化的各種策略,進一步結(jié)合標(biāo)準(zhǔn)化AIC提出了選取k值的有效方法。針對人臉識別的應(yīng)用表明,這一算法能夠以相對較低的計算代價獲得較好的識別精度。Boutsidis等41進一步提出基于雙重SVD分解實現(xiàn)NMF算法的初始化,獲得了遠高于隨機初始化方法的收斂速度和分解精度。如何為NMF算法選取適當(dāng)?shù)膋值與初始值,當(dāng)前并沒有標(biāo)準(zhǔn)的做法,仍然需要進一步深入研究和探索。錄、翻譯兩個階段,表達為相應(yīng)的RNA或氨基酸序列,而后經(jīng)過復(fù)雜的折疊過程,形成特殊的二級、三級結(jié)

28、構(gòu),得到具備功能的RNA或蛋白質(zhì)。分析和認(rèn)識生物大分子的序列特征是理解基因功能與各種調(diào)控機制的關(guān)鍵所在。目前,包括人類在內(nèi)的上百個物種的基因組已經(jīng)被完整測序,自動化測序技術(shù)每天都能夠產(chǎn)生大量的序列數(shù)據(jù),如何設(shè)計有效算法從這些海量數(shù)據(jù)中提取有意義的生物學(xué)知識成為生物信息學(xué)研究的巨大挑戰(zhàn)。早期的研究主要集中在簡單的序列比對,研究者提出了多種高效算法,并將其實現(xiàn)為各種應(yīng)用軟件包,如經(jīng)典的序列比對軟件BLAST、張春霆院士提出的圖形化序列分析工具Z Curve42等。隨著研究的深入,尤其是系統(tǒng)生物學(xué)的發(fā)展,基于序列特征認(rèn)識基因、蛋白分子的功能及相互關(guān)系得到了更多的關(guān)注。序列分析強調(diào)基于基因組的序列組成

29、與分布特征認(rèn)識生物大分子的活動規(guī)律,從而預(yù)測基因、蛋白功能,理解轉(zhuǎn)錄、調(diào)控的內(nèi)在機制。作為一種有效的維度規(guī)約和機器學(xué)習(xí)策略,NMF廣泛應(yīng)用于基因組的序列特征識別,獲得了諸多有意義的分析結(jié)果。Heger43應(yīng)用NMF分析了序列相似性較低(11%,BLAST)的尿素酶蛋白家族,識別出的蛋白功能類及不同類別之間的作用關(guān)系能夠較好地吻合于傳統(tǒng)的實驗結(jié)果。Heli等44應(yīng)用NMF分析轉(zhuǎn)錄因子結(jié)合位點之間的依賴關(guān)系,與ICA、PLSA和頻繁集方法的分析結(jié)果比較表明:NMF能夠更好地提取基因上游區(qū)的序列motif。Graber等45應(yīng)用NMF分析C.Elegans序列,識別出控制轉(zhuǎn)錄剪接和前體mRNA處理的

30、C.Elegans。Hutchins等46結(jié)合序列組成和位置兩方面的信息分析了順式調(diào)控Motif的位置依賴關(guān)系,對果蠅基因組序列的分析表明了NMF方法的有效性。Jung等47應(yīng)用NMF于蛋白質(zhì)的profile profile比對以提取蛋白質(zhì)的必要特征,并利用這些特征有效提高折疊識別(FoldRecognition)和遠距離同源蛋白檢測(RemoteHomologDetection)的準(zhǔn)確性。3.2 表達模式與功能模塊識別通過有選擇地激活或抑制某些基因表達,細胞能夠響應(yīng)外部環(huán)境的各種刺激,同時保持細胞內(nèi)部處于相對穩(wěn)定的狀態(tài),從而正常行使功能。因此,基因的表達水平反映了細胞活動的內(nèi)部機制。利用各種

31、微陣列技術(shù)(如cDNA芯片、寡核苷酸芯片等),能夠同步測量成千上萬個基因的表達。這些表達數(shù)據(jù)中蘊含著有關(guān)基因功能和細胞活動機制的豐富信息,如何利用計算技術(shù)從中挖掘和提取有意義的生物知識,是當(dāng)前生物信息學(xué)領(lǐng)域的熱點問題?，F(xiàn)有算法一般通過分析基因表達譜之間的相似性或相關(guān)性將基因劃分為不同的共表達、共調(diào)控模塊。研究者利用各種聚類、分類方法進行了嘗試,如分層聚類(HC)、K means聚類、SVM構(gòu)造分類器等。這些嘗試取得了一定的成果,能夠識別基因表達數(shù)據(jù)中蘊含的功能模塊。但是,這些方法只能從全局上識別表達模式和功能模塊,無法獲取表達數(shù)據(jù)中蘊含的局部特征。而NMF通過維度規(guī)約,能夠得到源數(shù)據(jù)的一個局部

32、表達,能夠更好地識別存在于特定條件下的局部特征。同時,NMF可以識別相互重疊的功能模塊,即一個或一些基因能夠同時屬于不同的功能模塊。顯然,這更符合真實情況,能夠更好地刻畫復(fù)雜的細胞活動過程。3 非負(fù)矩陣分解在生物信息學(xué)中的應(yīng)用相比其它維度規(guī)約或特征提取算法,NMF具有更好的性質(zhì),其分析結(jié)果能夠得到合理的生物學(xué)解釋。因此,NMF在生物信息學(xué)中得到了廣泛應(yīng)用。本節(jié)對這些應(yīng)用進行綜述、歸類,從序列特征分析、表達模式與功能模塊識別、生物醫(yī)學(xué)文本挖掘等幾個方面進行總結(jié)和討論。3.1 序列特征分析序列是遺傳信息的載體,也是基因、蛋白執(zhí)行功能的物質(zhì)基礎(chǔ)。DNA一般不直接參與生命活動,一般要經(jīng)過轉(zhuǎn)Kim和Ti

33、dor34應(yīng)用NMF分析酵母的300組基因表達數(shù)據(jù)集,將6316個基因劃分為不同的功能類別,并預(yù)測不同類別之間的關(guān)系。比較表明,NMF預(yù)測結(jié)果與MIPS功能數(shù)據(jù)庫的分類結(jié)果是一致的。Brunet36提出了一個確定k值的有效策略,并將其應(yīng)用于白血病、成神經(jīng)細胞瘤、中樞神經(jīng)系統(tǒng)細胞腫瘤等3個數(shù)據(jù)集的分析,定義metagene以描述數(shù)據(jù)中隱含的亞表達模式。文章將NMF與HC、SOM的分析結(jié)果進行了比較,結(jié)果表明NMF能夠更準(zhǔn)確地識別腫瘤子類。GAO等人483.4 其它應(yīng)用作為一種近年來快速發(fā)展的機器學(xué)習(xí)方法,NMF能夠?qū)崿F(xiàn)對高維數(shù)據(jù)的快速降維,獲得基于部分的局部表達。NMF具有諸多良好屬性,如非負(fù)性

34、使其能夠有效地刻畫數(shù)據(jù)中潛存的局部屬性,對其稀疏性的顯式控制能夠?qū)崿F(xiàn)細粒度的特征提取等。此外,算法的收斂性與諸多高效的快速算法使其具有極好的實用性,因此除了應(yīng)用序列、表達數(shù)據(jù)及生物醫(yī)學(xué)文獻數(shù)據(jù)的分析,NMF算法也廣泛地應(yīng)用于其它生物信息學(xué)問題的研究。Zhang等58應(yīng)用NMF算法于復(fù)雜網(wǎng)絡(luò)分析,有效識別出網(wǎng)絡(luò)中存在的模糊社團結(jié)構(gòu)。Schachtner59等利用NMF分析基因表達數(shù)據(jù),提取細胞分裂與分化過程各階段的標(biāo)志基因,并進一步將NMF用于分析人類體表細胞在分化過程中的表達水平,識別出可用于疾病診斷的相關(guān)基因60。Derek等人61將NMF用于分析蛋白質(zhì)相互作用數(shù)據(jù),將二值蛋白值相互作用裝配

35、為多個存在重疊關(guān)系的功能模塊。為目標(biāo)函數(shù)增加了拉格朗日算子,通過算子系數(shù)顯式控制NMF分解的稀疏性,進一步提高了NMF對局部特征的識別能力。Pedro等49應(yīng)用非光滑NMF分析了包含79個組織的人類轉(zhuǎn)錄組數(shù)據(jù)集,結(jié)合GO數(shù)據(jù)庫(GeneOntology)中的注釋信息,成功識別出包含神經(jīng)與腦、血液與淋巴等8類組織及對應(yīng)的表達樣本。CarrascoDR等50應(yīng)用NMF分析骨髓瘤病人的比較基因組雜交微陣列,識別出能應(yīng)用于臨床治療的兩個致病基因型子類。Tamayo等研究者51利用NMF降低表達數(shù)據(jù)中包含的噪音,實現(xiàn)對跨平臺、多物種基因表達數(shù)據(jù)的分析,并應(yīng)用這一方法分析白血病和肺癌數(shù)據(jù)集,得到了更準(zhǔn)確的

36、聚類結(jié)果。Pascual Montano等52基于NMF開發(fā)一個Web程序應(yīng)用于基因表達數(shù)據(jù)的分析。Li等534 結(jié)束語高通量實驗技術(shù)能夠得到大規(guī)模的實驗數(shù)據(jù),很多情況下這些數(shù)據(jù)在數(shù)學(xué)上體現(xiàn)為高維的數(shù)值矩陣,需要高效的、解釋能力強的矩陣分解與計算方法。NMF為這些數(shù)據(jù)的處理提供了一條新的思路。通過對因子矩陣施加非負(fù)約束,NMF能夠得到基于部分的局部表達,分解結(jié)果容易得到直觀的物理解釋。相比其它同類矩陣分解算法,NMF在實現(xiàn)上比較簡單,具有收斂速度快、穩(wěn)定性好的優(yōu)勢。因此,NMF算法在包括生物信息學(xué)在內(nèi)的多個領(lǐng)域得到了廣泛的應(yīng)用。本文系統(tǒng)地分析了NMF算法的發(fā)展歷程、構(gòu)造原則及應(yīng)用特點,綜述了近

37、年來的最新發(fā)展,尤其重點關(guān)注了NMF在生物信息學(xué)領(lǐng)域的應(yīng)用。但是,作為一種較新的算法,NMF的理論和計算方法仍處于不斷發(fā)展中,其分析和解釋生物信息的能力也有待進一步挖掘。NMF算法具有一定的隨機性,其算法初始化、k值選取、穩(wěn)定性及收斂速度等問題,以及如何拓展矩陣分解至高維的張量數(shù)據(jù)分解,發(fā)展和完善非負(fù)張量分解算法(NTF),均需進一步深入研究。應(yīng)用NMF處理生物數(shù)據(jù)時也有很多有意義的問題,這些問題包括:(1)如何提高對NMF計算結(jié)果解釋的合理性;(2)如何選取合理的預(yù)處理方法,降低噪音對NMF分解結(jié)果的影響;(3)如何結(jié)合生物學(xué)先驗知識,合理選取k值與算法初始點;(4)如何構(gòu)造標(biāo)準(zhǔn)數(shù)據(jù)集,評估

38、NMF算法的計算結(jié)果;(5)提出滿足生物信息處理特殊要求的NMF擴展等。為廣泛應(yīng)用的基因表達數(shù)據(jù)分析程序BRB ArrayTools增加NMF算法的插件。Andre等54應(yīng)用NMF分析高分辨率的寡核苷酸比較基因組雜交微陣列數(shù)據(jù)識別出與乳腺癌相關(guān)的3個基因亞類。3.3 生物醫(yī)學(xué)文獻挖掘文獻數(shù)據(jù)庫積累了浩如煙海的生物醫(yī)學(xué)文獻,包含大量與基因序列、功能相關(guān)的無序、非結(jié)構(gòu)化信息,如何從這些零碎的信息中提取有意義的生物知識是當(dāng)前生物信息學(xué)研究的熱點問題。本質(zhì)上講,文獻挖掘主要基于自然語言中存在的相似性,從大量文獻中提取有關(guān)某一主題的全部信息,并做進一步的處理,以抽象出有意義的知識#。Pubmed是最大的

39、醫(yī)學(xué)文獻數(shù)據(jù)庫,包含了自1948年以來7300多種不同類型的研究文獻。截至至2009年,其包含的文獻已經(jīng)超過1800萬條。將主題詞和文檔分別作為矩陣的行和列,矩陣元素表示單詞在文檔中出現(xiàn)的頻率,文獻挖掘可通過對數(shù)據(jù)矩陣的分析實現(xiàn)。NMF的最早應(yīng)用之一就是文獻挖掘,Lee和Seung5首先應(yīng)用NMF提取文檔中的語義特征,并通過與PCA、ICA及VQ等方法的比較驗證了NMF算法的有效性。Chagoyen等人55應(yīng)用NMF從相關(guān)文獻中提取共同的語義特征,并在此基礎(chǔ)上構(gòu)建大規(guī)模基因或蛋白分子集合的文獻譜,進一步可建立基因、蛋白之間的功能關(guān)聯(lián)網(wǎng)絡(luò)。Kim等56利用已知的基因關(guān)系作為先驗知識,應(yīng)用NMF于

40、生物醫(yī)學(xué)文獻挖掘建立基因相互作用網(wǎng)絡(luò),并與基于奇異值分解的潛在語義檢索方法進行比較,討論了選取不同k值時算法的性能。Kevin等57參考文獻:1 YeungMK,TegnerJ,CollinsJJ.ReverseEngineeringGeneNetworksUsingSingularValueDecompositionandRobustRegressionJ.ProceedingsoftheNationalAcademyofSciences,2002,99(9):6163 6168.2 YeungKY,RuzzoWL.PrincipalComponentAnalysisforClusterin

41、gGeneExpressionDataJ.Bioinformatics,2001,17(9):763 774.3 LiebermeisterW.LinearModesofGeneExpressionDeter嘗試基于醫(yī)學(xué)文獻挖掘建立基因的分層聚類樹,通過對每一節(jié)點進行注釋標(biāo)記建立刻畫基因間的功能關(guān)聯(lián)。該文基于NMF提出了一種有效的聚類、標(biāo)記算法,同時還進一步討論了選取不同參數(shù)對算法收斂性與標(biāo)記精度的影響。minedbyIndependentComponentAnalysisJ.Bioinformat ics,2002,18(1):51 60.4 LiaoJC,BoscoloR,YangYL,e

42、tal.NetworkComponentAnalysis:ReconstructionofRegulatorySignalsinBiologicalSystemsJ.ProceedingsoftheNationalAcademyofSci ences,2003,100(26):15522 15527.5 LeeDD,SeungHS.LearningthePartsofObjectsbyNonnegativeMatrixFactorizationJ.Nature,1999,401(6755):788 791.6 PaateroP,TapperU.PositiveMatrixFactorizati

43、on:ANonnegativeFactorModelwithOptimalUtilizationofErrorEs timatesofDataValuesJ.Environmetrics,1994,5(2):111 126.7 PaateroP.LeastSquaresFormulationofRobustNon negativeFactorAnalysisJ.ChemometricsandIntelligentLabo ratorySystems,1997,37(1):22 35.8 LeeDD,SeungHS.UnsupervisedLearningbyConvexandConicCodi

44、ngJ.AdvancesinNeuralInformationProcessingSystems,1997,1997(9):515 521.9 LeeDD,SebastianSH.AlgorithmsforNon negativeMatrixFactorizationJ.AdvancesinNeuralInformationProcessingSystems,2001,2001(13):556 562.10 LiSZ,HouXinwen,ZhangHongjiang,etal.LearningSpatiallyLocalized,Parts BasedRepresentationC)Proco

45、fIEEEConfonComputerVisionandPatternRecognition,2001:207 212.11 WangYuan,JiaYunde.FisherNon negativeMatrixFactorizationforLearningLocalFeaturesC)ProcofAsianConfonComputerVision,2004:27 30.12 PatrikHO.Non negativeSparseCodingC)ProcofIEEEWorkshoponNeuralNetworksforSignalProcessing,2002:557 565.13 Patri

46、kHO,DayanP.Non negativeMatrixFactorizationwithSparsenessConstraintsJ.TheJournalofMachineLearningResearch,2004,5(12):1457 1469.14 TheisFJ,StadlthannerK,TanakaT.FirstResultsonUniquenessofSparseNon negativeMatrixFactorizationC)Procofthe13thEuropeanSignalProcessingConf,2005:1 4.15 GuillametD,VitriaJ,Sch

47、ieleB.IntroducingaWeightedNon negativeMatrixFactorizationforImageClassificationJ.PatternRecognitionLetters,2003,24(14):2447 2454.16 DingC,HeX,SimonHD.OntheEquivalenceofNon negativeMatrixFactorizationandSpectralClusteringC)ProcofSIAMDataMiningConf,2005:606 610.17 DingChris,LiTao,PengWei,etal.Orthogon

48、alNon negativeMatrixt FactorizationsforClusteringC)Procofthe12thACMSIGKDDIntlConfonKnowledgeDiscoveryandDataMining,2006:126 135.18 Pascual MontanoA,CarazoJM,KochiK,etal.NonsmoothNon negativeMatrixFactorization(nsNMF)J.IEEETransonPatternAnalysisandMachineIntelligence,2006,28(3):403 415.19 CichockiA,Z

49、dunekR.MultilayerNon negativeMatrixFactorizationJ.ElectronicsLetters,2006,42(16):947 948.20 WangG,KossenkovAV,OchsMF.LS NMF:AModifiedNon negativeMatrixFactorizationAlgorithmUtilizingUn certaintyEstimatesJ.BMCBioinformatics,2006,7(3):175 184.21 Pascual MontanoA,Carmona SaezP,ChagoyenM,etal.bioNMF:AVe

50、rsatileToolforNon negativeMatrixFactori zationinBiologyJ.BMCBioinformatics,2006,7(7):366 374.22 ShashuaA,HazanT.Non negativeTensorFactorizationwithApplicationstoStatisticsandComputerVisionC)Procofthe22ndIntlConfonMachineLearning,2005:792 799.23 GonzalesEdwardF,ZhangYin.AcceleratingtheLee SeungAlgori

51、thmforNon negativeMatrixFactorizationR.TechnicalReport,DepartmentofComputationalandAp pliedMathematics,RiceUniversity,2005:1 13.24 LaurbergH,ChristensenMG,PlumbleyMD,etal.TheoremsonPositiveData:OntheUniquenessofNMFJ.ComputationalIntelligenceandNeuroscience,2008,2008(3):1 9.25 LinCJ.ProjectedGradient

52、MethodsforNon negativeMatrixFactorizationJ.NeuralComputation,2007,19(10):2756 2779.26 ZdunekR,CichockiA.Non negativeMatrixFactorizationwithQuasi NewtonOptimizationC)ProcoftheIntlConfonArtificialIntelligenceandSoftComputing,2006:870 879.27 ZdunekR,CichockiA.Non negativeMatrixFactorizationwithConstrai

53、nedSecond OrderOptimizationJ.SignalProcessing,2007,87(8):1904 1916.28 LiuWeixiang,YeDatian,YuanKehong.OnAlpha DivergenceBasedNon negativeMatrFactorizationforClusteringCancerGeneExpressionDataJ.ArtificialIntelligenceinMedicine,2008,44(1):1 5.29 DavidD,VictoriaS.WhenDoesNon negativeMatrixFactorization

54、GiveaCorrectDecompositionIntoParts?J.AdvancesinNeuralInformationProcessingSystems,2003,16:1 8.30 ChuMT,LinMM.Low DimensionalPolytopeApproximationandItsApplicationstoNon negativeMatrixFactor izationJ.SiamJournalonScientificComputing,2007,30(3):1131 1155.31 KlingenbergB,CurryJ,DoughertyA.Non negativeM

55、atrixFactorization:Ill PosednessandaGeometricAlgorithmJ.PatternRecognition,2009,42(5):918 928.32 OkunO,PriisaluH.FastNon negativeMatrixFactorizationandItsApplicationforProteinFoldRecognitionJ.Eur asipJournalonAppliedSignalProcessing,2006,2006(12):1 8.33 RaulK.AGeneralizedDivergenceMeasureforNon nega

56、tiveMatrixFactorizationJ.NeuralComputation,2007,19(3):780 791.34 KimPM,TidorB.SubsystemIdentificationThroughDimensionalityReductionofLarge ScaleGeneExpressionDa taJ.GenomeResearch,2003,13(7):1706 1718.35 MontiS,TamayoP,MesirovJ,etal.ConsensusClustering:AResampling BasedMethodforClassDiscoveryandVisu

57、alizationofGeneExpressionMicroarrayDataJ.Ma chineLearning,2003,52(1 2):91 118.36 BrunetJP,TamayoP,GolubTR,etal.MetagenesandMolecularPatternDiscoveryUsingMatrixFactorizationJ.ProceedingsoftheNationalAcademyofSciences,2004,101(12):4164 4169.37 WildS,CurryJ,DoughertyA.ImprovingNon negativeMatrixFactorizationsThroughStructuredInitializationJ.PatternRecognition,2004,37(11):2217 2232.38 AlbrightR,CoxJ,DulingD,etal.Algorithms,Initializations,andConvergencefortheNon negativeMatrixFac torizationR.TechnicalReport,NCSUTec