本文關(guān)鍵詞：基于基因表達數(shù)據(jù)的雙聚類算法研究

  更多相關(guān)文章： 基因表達數(shù)據(jù) 雙聚類算法 趨勢一致雙聚類 最長公共子序列

【摘要】：基因芯片技術(shù)是近年來分子生物學(xué)領(lǐng)域的一大技術(shù)突破,它可以平行檢測數(shù)以萬計基因的表達水平,從而獲得不同條件下基因組水平的基因表達數(shù)據(jù)。然而面對迅速增長的數(shù)據(jù),如何借助有效的計算方法對海量數(shù)據(jù)進行分析成為了新的挑戰(zhàn)。本文主要研究的就是如何針對基因表達數(shù)據(jù)設(shè)計雙聚類算法,從而在表達數(shù)據(jù)中尋找趨勢一致雙聚類,即那些在特定條件下具有趨勢一致表達的基因集。通過對基因表達數(shù)據(jù)的研究,有助于分析基因的表達調(diào)控信息,了解基因之間的相關(guān)性,對疾病診斷治療、藥物療效判斷等方面具有十分重要的意義。最早的研究基因表達數(shù)據(jù)的方法是利用單聚類算法分別對基因或條件進行分析。其結(jié)果反映的往往是一組基因在全部條件下,或全部基因在某些條件下表達的相關(guān)性。然而在生物體內(nèi),參與同一調(diào)控功能的僅僅是一部分基因,且它們只在部分條件下具有表達相關(guān)性。同時,許多基因通常具有多種調(diào)控功能,可能會在不同的條件下表現(xiàn)出不同的功能。因此在基因表達數(shù)據(jù)的分析中,我們需要的是能夠反映部分基因在部分條件下表達相關(guān)性的雙聚類,同時允許不同的雙聚類之間會存在一定程度的覆蓋,而這些數(shù)據(jù)特征都是采用傳統(tǒng)的單聚類算法難以獲得的。雙聚類算法的提出為基因表達數(shù)據(jù)的分析提供了有效的方法,使得我們可以找到在特定條件下具有一致表達類型的基因集。雙聚類算法最初由Morgan等人提出,他們將矩陣分解為值近似相等的子矩陣。隨著雙聚類算法被應(yīng)用到基因表達數(shù)據(jù)的分析中,大量針對不同類型雙聚類的算法涌現(xiàn)出來,并對基因表達數(shù)據(jù)的分析起了重要的作用。趨勢一致雙聚類是隱藏在基因表達數(shù)據(jù)中最具有生物意義的一種雙聚類類型,目前也有很多算法是針對此類型雙聚類設(shè)計的。但是由于問題本身的復(fù)雜性,如何快速有效地識別數(shù)據(jù)中的趨勢一致雙聚類仍然是一大難題。本文中,我們提出了一種新的雙聚類算法UniBic,它可以準確地識別矩陣數(shù)據(jù)中的趨勢一致雙聚類。算法的設(shè)計基于如下發(fā)現(xiàn)：在順序一致的雙聚類中,存在一個列的重排列,使得各行元素值在該重排列下是非降序排列的,且識別雙聚類的關(guān)鍵就在于準確定位雙聚類所在的列。UniBic的設(shè)計主要分為以下幾步：首先,根據(jù)原始矩陣創(chuàng)建數(shù)據(jù)的索引矩陣,并根據(jù)所要尋找的雙聚類的顯著性信息將索引矩陣分組：隨后,將最長公共子序列方法運用到索引矩陣每一分組的行對之間,以定位可以用來進一步擴增雙聚類的種子序列；最后,將種子擴增為嚴格順序一致的雙聚類,并在允許誤差存在時將嚴格順序一致的雙聚類擴增為趨勢一致雙聚類。索引矩陣的建立將在背景矩陣中尋找趨勢一致雙聚類的問題轉(zhuǎn)化為在索引矩陣的行對之間尋找最長公共子序列的問題,使得原問題不那么棘手。此外,在處理如基因表達數(shù)據(jù)等的大規(guī)模矩陣數(shù)據(jù)時,我們通過對數(shù)據(jù)進行預(yù)處理,選擇出起調(diào)控作用的部分數(shù)據(jù)進行分析,從而有效地減少了冗余數(shù)據(jù)及噪音數(shù)據(jù)對結(jié)果造成的影響。我們分別在模擬數(shù)據(jù)及真實數(shù)據(jù)上對比了UniBic與其余六種算法的性能。在不同類型的模擬數(shù)據(jù)上的測試結(jié)果表明,當嵌入的雙聚類具有一定列數(shù)支持時,UniBic的表現(xiàn)明顯優(yōu)于其余所有算法,特別地,UniBic能夠有效識別模擬矩陣數(shù)據(jù)中嵌入的趨勢一致雙聚類。同時,當模擬數(shù)據(jù)中嵌入的雙聚類之間存在一定覆蓋度時,UniBic的表現(xiàn)也優(yōu)于其它算法。在真實數(shù)據(jù)的測試中,UniBic得到的結(jié)果也是平均GO富集度最高的。但我們的算法仍有不足之處,由于種子是從索引矩陣行對之間的最長公共子序列中尋找的,UniBic在一定程度上會忽略列數(shù)較少的窄形雙聚類。目前已有算法是專門針對數(shù)據(jù)中的窄形雙聚類設(shè)計的,但是此類型的算法不但時間復(fù)雜度普遍較高,而且當雙聚類列數(shù)較多時表現(xiàn)十分不理想�？紤]到雙聚類算法的復(fù)雜性,我們很難設(shè)計一種算法來高效地尋找所有類型的雙聚類,不過我們提出了一種可行的方法來彌補現(xiàn)有算法的不足,并作為后續(xù)的研究課題。文章的最后我們介紹了一個簡單的聚類算法Peg,并在梭狀芽孢桿菌基因組數(shù)據(jù)中將其與層次聚類算法進行對比。結(jié)果表明我們的算法可以較好地反映基因組的分組狀態(tài)。UniBic已用C語言實現(xiàn)為開源軟件,下載地址為：http://sourceforge.net/projects/unibic/files/?source=navbar.本文所用測試數(shù)據(jù)及測試結(jié)果也可從該地址下載。
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：TP311.13

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 周世兵;徐振源;唐旭清;;新的K-均值算法最佳聚類數(shù)確定方法[J];計算機工程與應(yīng)用;2010年16期

2 周世兵;徐振源;唐旭清;;基于近鄰傳播算法的最佳聚類數(shù)確定方法比較研究[J];計算機科學(xué);2011年02期

3 周世兵;徐振源;唐旭清;;一種基于近鄰傳播算法的最佳聚類數(shù)確定方法[J];控制與決策;2011年08期

4 李旭;林偉;溫金環(huán);史彩云;;基于圖譜理論的圖像聚類數(shù)的確定及應(yīng)用[J];工程數(shù)學(xué)學(xué)報;2012年05期

5 秦振濤;楊武年;;一種新的最佳聚類數(shù)確定方法[J];電子技術(shù)應(yīng)用;2013年01期

6 宋銘利;高新科;;基于距離的最大聚類數(shù)探索算法的探討[J];礦山機械;2006年09期

7 普運偉;朱明;金煒東;胡來招;;核聚類算法最佳聚類數(shù)的自適應(yīng)確定方法[J];計算機工程;2007年04期

8 楊欣斌,孫京誥,黃道;一種進化聚類學(xué)習(xí)新方法[J];計算機工程與應(yīng)用;2003年15期

9 田彥山;;基于山峰聚類的聚類上限確定方法[J];江西師范大學(xué)學(xué)報(自然科學(xué)版);2007年02期

10 褚娜;馬利莊;王彥;;聚類趨勢問題的研究綜述[J];計算機應(yīng)用研究;2009年03期

中國重要會議論文全文數(shù)據(jù)庫 前9條

1 高翠芳;吳小俊;;基于二階差分的聚類數(shù)自動確定方法[A];江蘇省系統(tǒng)工程學(xué)會第十一屆學(xué)術(shù)年會論文集[C];2009年

2 劉洋;江志綱;丁增喜;王大玲;鮑玉斌;于戈;;一種基于圖的聚類算法GB-Cluster[A];第十九屆全國數(shù)據(jù)庫學(xué)術(shù)會議論文集（技術(shù)報告篇）[C];2002年

3 李浪波;傅彥;劉紅;;基于范例推理的網(wǎng)格和密度聚類算法[A];第二十二屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（技術(shù)報告篇）[C];2005年

4 婁冬梅;陳明;朱有娜;;一種基于密度的無參數(shù)聚類算法[A];第二十三屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報告篇）[C];2006年

5 魏昕路;洪志令;姜青山;;一種基于樣本縮減策略的新窗口式聚類算法[A];第二十四屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報告篇）[C];2007年

6 程尊平;周鼎;王晨;周皓峰;汪衛(wèi);施伯樂;;SDPHC——基于密度的分割和分層的自校聚類算法[A];第二十一屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報告篇）[C];2004年

7 張曉峰;王麗珍;陸葉;;一種基于屬性加權(quán)的不確定K-means聚類算法[A];第26屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（B輯）[C];2009年

8 蔡軍;袁華鵬;陳金海;施伯樂;;一種基于相似性分析的聚類新算法:PDS算法[A];第十八屆全國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報告篇）[C];2001年

9 胡仲義;郭超;王永炎;劉勝航;王宏安;;基于時間衰減和特征變量的數(shù)據(jù)流聚類算法[A];第29屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（B輯）（NDBC2012）[C];2012年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 王振佳;基于基因表達數(shù)據(jù)的雙聚類算法研究[D];山東大學(xué);2016年

2 胡雅婷;可能性聚類方法研究及應(yīng)用[D];吉林大學(xué);2012年

3 王縱虎;聚類分析優(yōu)化關(guān)鍵技術(shù)研究[D];西安電子科技大學(xué);2012年

4 周世兵;聚類分析中的最佳聚類數(shù)確定方法研究及應(yīng)用[D];江南大學(xué);2011年

5 楊燕;基于計算智能的聚類組合算法研究[D];西南交通大學(xué);2006年

6 馮永;基于計算智能的聚類技術(shù)及其應(yīng)用研究[D];重慶大學(xué);2006年

7 劉晨;高伸縮性聚類分析方法研究[D];哈爾濱工程大學(xué);2013年

8 王強;局部疊加基因表達模式聚類分析方法研究[D];哈爾濱工業(yè)大學(xué);2012年

9 姜磊;混合演化聚類算法研究及其應(yīng)用[D];武漢大學(xué);2012年

10 尹學(xué)松;半監(jiān)督聚類分析策略設(shè)計及其拓展性研究[D];南京航空航天大學(xué);2009年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 魏建東;K-means初始化算法研究[D];南京理工大學(xué);2015年

2 張依;基于MapReduce的k-means聚類算法并行化研究[D];中央民族大學(xué);2015年

3 劉嬋;蟻群與K均值聚類算法融合研究及其在用戶分群中的應(yīng)用[D];西南科技大學(xué);2015年

4 朱琪;基于減法聚類的混合算法研究[D];湖南科技大學(xué);2015年

5 韓偉森;聚類集成研究與應(yīng)用[D];貴州大學(xué);2015年

6 譚浩;K-Means算法改進及其在森林健康評價中的應(yīng)用[D];中南林業(yè)科技大學(xué);2015年

7 嚴巍;以KPCA為核心的FCM算法改進[D];成都理工大學(xué);2015年

8 汪娟;基于權(quán)重設(shè)計的聚類集成算法研究[D];重慶大學(xué);2015年

9 牛品菽;基于圖模型的高效聚類算法研究[D];北京交通大學(xué);2016年

10 蔡洪山;大數(shù)據(jù)分析中的聚類算法研究[D];安徽理工大學(xué);2016年

，

本文編號：1285505