基于基因表達(dá)數(shù)據(jù)的雙聚類算法研究.pdf

1、基因芯片技術(shù)是近年來分子生物學(xué)領(lǐng)域的一大技術(shù)突破，它可以平行檢測數(shù)以萬計(jì)基因的表達(dá)水平，從而獲得不同條件下基因組水平的基因表達(dá)數(shù)據(jù)。然而面對迅速增長的數(shù)據(jù)，如何借助有效的計(jì)算方法對海量數(shù)據(jù)進(jìn)行分析成為了新的挑戰(zhàn)。本文主要研究的就是如何針對基因表達(dá)數(shù)據(jù)設(shè)計(jì)雙聚類算法，從而在表達(dá)數(shù)據(jù)中尋找趨勢一致雙聚類，即那些在特定條件下具有趨勢一致表達(dá)的基因集。通過對基因表達(dá)數(shù)據(jù)的研究，有助于分析基因的表達(dá)調(diào)控信息，了解基因之間的相關(guān)性，對疾病診斷治療、

2、藥物療效判斷等方面具有十分重要的意義。
　　最早的研究基因表達(dá)數(shù)據(jù)的方法是利用單聚類算法分別對基因或條件進(jìn)行分析。其結(jié)果反映的往往是一組基因在全部條件下，或全部基因在某些條件下表達(dá)的相關(guān)性。然而在生物體內(nèi)，參與同一調(diào)控功能的僅僅是一部分基因，且它們只在部分條件下具有表達(dá)相關(guān)性。同時(shí)，許多基因通常具有多種調(diào)控功能，可能會在不同的條件下表現(xiàn)出不同的功能。因此在基因表達(dá)數(shù)據(jù)的分析中，我們需要的是能夠反映部分基因在部分條件下表達(dá)相關(guān)性的雙

3、聚類，同時(shí)允許不同的雙聚類之間會存在一定程度的覆蓋，而這些數(shù)據(jù)特征都是采用傳統(tǒng)的單聚類算法難以獲得的。
　　雙聚類算法的提出為基因表達(dá)數(shù)據(jù)的分析提供了有效的方法，使得我們可以找到在特定條件下具有一致表達(dá)類型的基因集。雙聚類算法最初由Morgan等人提出，他們將矩陣分解為值近似相等的子矩陣。隨著雙聚類算法被應(yīng)用到基因表達(dá)數(shù)據(jù)的分析中，大量針對不同類型雙聚類的算法涌現(xiàn)出來，并對基因表達(dá)數(shù)據(jù)的分析起了重要的作用。趨勢一致雙聚類是隱藏在基

4、因表達(dá)數(shù)據(jù)中最具有生物意義的一種雙聚類類型，目前也有很多算法是針對此類型雙聚類設(shè)計(jì)的。但是由于問題本身的復(fù)雜性，如何快速有效地識別數(shù)據(jù)中的趨勢一致雙聚類仍然是一大難題。
　　本文中，我們提出了一種新的雙聚類算法UniBic，它可以準(zhǔn)確地識別矩陣數(shù)據(jù)中的趨勢一致雙聚類。算法的設(shè)計(jì)基于如下發(fā)現(xiàn):在順序一致的雙聚類中，存在一個列的重排列，使得各行元素值在該重排列下是非降序排列的，且識別雙聚類的關(guān)鍵就在于準(zhǔn)確定位雙聚類所在的列。UniBi

5、c的設(shè)計(jì)主要分為以下幾步:首先，根據(jù)原始矩陣創(chuàng)建數(shù)據(jù)的索引矩陣，并根據(jù)所要尋找的雙聚類的顯著性信息將索引矩陣分組;隨后，將最長公共子序列方法運(yùn)用到索引矩陣每一分組的行對之間，以定位可以用來進(jìn)一步擴(kuò)增雙聚類的種子序列;最后，將種子擴(kuò)增為嚴(yán)格順序一致的雙聚類，并在允許誤差存在時(shí)將嚴(yán)格順序一致的雙聚類擴(kuò)增為趨勢一致雙聚類。索引矩陣的建立將在背景矩陣中尋找趨勢一致雙聚類的問題轉(zhuǎn)化為在索引矩陣的行對之間尋找最長公共子序列的問題，使得原問題不那么棘

6、手。此外，在處理如基因表達(dá)數(shù)據(jù)等的大規(guī)模矩陣數(shù)據(jù)時(shí)，我們通過對數(shù)據(jù)進(jìn)行預(yù)處理，選擇出起調(diào)控作用的部分?jǐn)?shù)據(jù)進(jìn)行分析，從而有效地減少了冗余數(shù)據(jù)及噪音數(shù)據(jù)對結(jié)果造成的影響。
　　我們分別在模擬數(shù)據(jù)及真實(shí)數(shù)據(jù)上對比了UniBic與其余六種算法的性能。在不同類型的模擬數(shù)據(jù)上的測試結(jié)果表明，當(dāng)嵌入的雙聚類具有一定列數(shù)支持時(shí)，UniBic的表現(xiàn)明顯優(yōu)于其余所有算法，特別地，UniBic能夠有效識別模擬矩陣數(shù)據(jù)中嵌入的趨勢一致雙聚類。同時(shí)，當(dāng)模擬

7、數(shù)據(jù)中嵌入的雙聚類之間存在一定覆蓋度時(shí)，UniBic的表現(xiàn)也優(yōu)于其它算法。在真實(shí)數(shù)據(jù)的測試中，UniBic得到的結(jié)果也是平均GO富集度最高的。
　　但我們的算法仍有不足之處，由于種子是從索引矩陣行對之間的最長公共子序列中尋找的，UniBic在一定程度上會忽略列數(shù)較少的窄形雙聚類。目前已有算法是專門針對數(shù)據(jù)中的窄形雙聚類設(shè)計(jì)的，但是此類型的算法不但時(shí)間復(fù)雜度普遍較高，而且當(dāng)雙聚類列數(shù)較多時(shí)表現(xiàn)十分不理想?？紤]到雙聚類算法的復(fù)雜性，我

8、們很難設(shè)計(jì)一種算法來高效地尋找所有類型的雙聚類，不過我們提出了一種可行的方法來彌補(bǔ)現(xiàn)有算法的不足，并作為后續(xù)的研究課題。
　　文章的最后我們介紹了一個簡單的聚類算法Peg，并在梭狀芽孢桿菌基因組數(shù)據(jù)中將其與層次聚類算法進(jìn)行對比。結(jié)果表明我們的算法可以較好地反映基因組的分組狀態(tài)。
　　UniBic已用C語言實(shí)現(xiàn)為開源軟件，下載地址為:http://sourceforge.net/projects/unibic/files/?s