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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：1285505