類似的圖形聚類算法可用于理解執(zhí)行大部分生命功能的蛋白質(zhì)

您是否知道用于分析社交網(wǎng)絡(luò)用戶之間關(guān)系或排名網(wǎng)頁(yè)的工具對(duì)于理解大型科學(xué)數(shù)據(jù)也非常有價(jià)值?在像Facebook這樣的社交網(wǎng)絡(luò)上，每個(gè)用戶(個(gè)人或組織)都被表示為一個(gè)節(jié)點(diǎn)，它們之間的連接(關(guān)系和交互)被稱為邊緣。通過(guò)分析這些聯(lián)系，研究人員可以了解很多關(guān)于每個(gè)用戶的興趣，愛(ài)好，購(gòu)物習(xí)慣，朋友等。

在生物學(xué)中，類似的圖形聚類算法可用于理解執(zhí)行大部分生命功能的蛋白質(zhì)。據(jù)估計(jì)，僅人體就含有約100,000種不同的蛋白質(zhì)類型，當(dāng)這些微生物相互作用時(shí)，幾乎所有的生物學(xué)任務(wù) - 從消化到免疫 - 都會(huì)發(fā)生。更好地了解這些網(wǎng)絡(luò)可以幫助研究人員確定藥物的有效性或確定各種疾病的潛在治療方法。

如今，先進(jìn)的高通量技術(shù)使研究人員能夠在一系列環(huán)境條件下同時(shí)捕獲數(shù)億種蛋白質(zhì)，基因和其他細(xì)胞成分。然后將聚類算法應(yīng)用于這些數(shù)據(jù)集，以識(shí)別可能指向結(jié)構(gòu)和功能相似性的模式和關(guān)系。盡管這些技術(shù)已被廣泛使用了十多年，但它們無(wú)法跟上下一代測(cè)序儀和微陣列產(chǎn)生的大量生物數(shù)據(jù)。事實(shí)上，現(xiàn)有的算法很少能夠聚類包含數(shù)百萬(wàn)個(gè)節(jié)點(diǎn)(蛋白質(zhì))和邊緣(連接)的生物網(wǎng)絡(luò)。

這就是能源部(DOE)勞倫斯伯克利國(guó)家實(shí)驗(yàn)室(伯克利實(shí)驗(yàn)室)和聯(lián)合基因組研究所(JGI)的一組研究人員采用現(xiàn)代生物學(xué)中最流行的聚類方法之一 - 馬爾可夫聚類(MCL)算法 - 以及將其修改為在分布式內(nèi)存超級(jí)計(jì)算機(jī)上快速，高效和大規(guī)模運(yùn)行。在一個(gè)測(cè)試案例中，他們的高性能算法 - 稱為HipMCL--實(shí)現(xiàn)了以前不可能的壯舉：在國(guó)家能源研究中使用大約140,000個(gè)處理器核心，在幾個(gè)小時(shí)內(nèi)聚集一個(gè)包含大約7000萬(wàn)個(gè)節(jié)點(diǎn)和680億個(gè)邊緣的大型生物網(wǎng)絡(luò)科學(xué)計(jì)算中心(NERSC)Cori超級(jí)計(jì)算機(jī)。最近發(fā)表在“ 核酸研究 ”雜志上的一篇描述這項(xiàng)工作的論文。

“HipMCL的真正好處在于它能夠聚集大規(guī)模的生物網(wǎng)絡(luò)，這些生物網(wǎng)絡(luò)無(wú)法與現(xiàn)有的MCL軟件聚類，從而使我們能夠識(shí)別和表征微生物群落中存在的新功能空間，”負(fù)責(zé)JGI的Nikos Kyrpides說(shuō)道。微生物數(shù)據(jù)科學(xué)工作和原核生物超級(jí)計(jì)劃是本文的共同作者。“而且我們可以做到這一點(diǎn)，而不會(huì)犧牲原始方法的任何敏感性或準(zhǔn)確性，這始終是這類擴(kuò)展工作中的最大挑戰(zhàn)。”

“隨著我們的數(shù)據(jù)增長(zhǎng)，我們將工具轉(zhuǎn)移到高性能計(jì)算環(huán)境變得更加迫切，”他補(bǔ)充道。“如果你問(wèn)我蛋白質(zhì)空間有多大?事實(shí)上，我們并不知道，因?yàn)橹钡浆F(xiàn)在我們還沒(méi)有計(jì)算工具來(lái)有效地聚集我們所有的基因組數(shù)據(jù)并探測(cè)功能性暗物質(zhì)。 “

除了數(shù)據(jù)收集技術(shù)的進(jìn)步之外，研究人員越來(lái)越多地選擇在社區(qū)數(shù)據(jù)庫(kù)中共享他們的數(shù)據(jù)，例如綜合微生物基因組和微生物組(IMG / M)系統(tǒng)，該系統(tǒng)是通過(guò)JGI和伯克利實(shí)驗(yàn)室的科學(xué)家之間數(shù)十年的合作開(kāi)發(fā)的。計(jì)算研究部(CRD)。但是，通過(guò)允許用戶進(jìn)行比較分析并根據(jù)其宏基因組序列探索微生物群落的功能，IMG / M等社區(qū)工具也會(huì)導(dǎo)致技術(shù)數(shù)據(jù)爆炸。

隨機(jī)游走如何導(dǎo)致計(jì)算瓶頸

為了掌握這些數(shù)據(jù)，研究人員依靠聚類分析或聚類。這基本上是對(duì)對(duì)象進(jìn)行分組的任務(wù)，以便同一組(群集)中的項(xiàng)目與其他群集中的項(xiàng)目更相似。十多年來(lái)，計(jì)算生物學(xué)家一直青睞MCL通過(guò)相似性和相互作用聚類蛋白質(zhì)。

“MCL在計(jì)算生物學(xué)家中很受歡迎的原因之一是它相對(duì)無(wú)參數(shù);用戶無(wú)需設(shè)置大量參數(shù)即可獲得準(zhǔn)確的結(jié)果，并且對(duì)于數(shù)據(jù)的小變化非常穩(wěn)定。這是這很重要，因?yàn)槟赡苄枰匦露x數(shù)據(jù)點(diǎn)之間的相似性，或者您可能需要糾正數(shù)據(jù)中的輕微測(cè)量錯(cuò)誤。在這些情況下，您不希望您的修改將分析從10個(gè)集群更改為1,000個(gè)集群，“ CRD科學(xué)家AydinBuluç是該論文的共同作者之一。

但是，他補(bǔ)充說(shuō)，計(jì)算生物學(xué)社區(qū)正面臨計(jì)算瓶頸，因?yàn)樵摴ぞ咧饕\(yùn)行在單個(gè)計(jì)算機(jī)節(jié)點(diǎn)上，執(zhí)行計(jì)算成本高并且占用大量?jī)?nèi)存 - 所有這些都限制了此算法可以聚集的數(shù)據(jù)量。

此分析中計(jì)算量和內(nèi)存最密集的步驟之一是稱為隨機(jī)游走的過(guò)程。此技術(shù)可量化節(jié)點(diǎn)之間連接的強(qiáng)度，這對(duì)于分類和預(yù)測(cè)網(wǎng)絡(luò)中的鏈接非常有用。在互聯(lián)網(wǎng)搜索的情況下，這可能會(huì)幫助您在舊金山尋找便宜的酒店房間，享受春假，甚至可以告訴您預(yù)訂的最佳時(shí)間。在生物學(xué)中，這樣的工具可以幫助您識(shí)別幫助您的身體對(duì)抗流感病毒的蛋白質(zhì)。

給定任意圖形或網(wǎng)絡(luò)，很難知道訪問(wèn)所有節(jié)點(diǎn)和鏈接的最有效方法。隨機(jī)游走通過(guò)隨機(jī)探索整個(gè)圖形來(lái)獲得足跡感; 它從節(jié)點(diǎn)開(kāi)始，沿邊緣任意移動(dòng)到相鄰節(jié)點(diǎn)。此過(guò)程一直持續(xù)到圖形網(wǎng)絡(luò)上的所有節(jié)點(diǎn)都已到達(dá)。因?yàn)樵诰W(wǎng)絡(luò)中的節(jié)點(diǎn)之間有許多不同的傳播方式，所以該步驟重復(fù)多次。像MCL這樣的算法將繼續(xù)運(yùn)行此隨機(jī)游走過(guò)程，直到迭代之間不再存在顯著差異。

在任何給定的網(wǎng)絡(luò)中，您可能有一個(gè)連接到數(shù)百個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)和另一個(gè)只有一個(gè)連接的節(jié)點(diǎn)。隨機(jī)游走將捕獲高度連接的節(jié)點(diǎn)，因?yàn)槊看芜\(yùn)行該過(guò)程時(shí)都會(huì)檢測(cè)到不同的路徑。利用該信息，該算法可以以確定的程度預(yù)測(cè)網(wǎng)絡(luò)上的節(jié)點(diǎn)如何連接到另一個(gè)節(jié)點(diǎn)。在每個(gè)隨機(jī)游走運(yùn)行之間，算法在馬爾可夫矩陣的列中標(biāo)記其對(duì)圖上的每個(gè)節(jié)點(diǎn)的預(yù)測(cè) - 類似于分類帳 - 并且最后顯示最終聚類。這聽(tīng)起來(lái)很簡(jiǎn)單，但對(duì)于具有數(shù)百萬(wàn)個(gè)節(jié)點(diǎn)和數(shù)十億個(gè)邊緣的蛋白質(zhì)網(wǎng)絡(luò)，這可能成為極其計(jì)算和內(nèi)存密集的問(wèn)題。借助HipMCL，伯克利實(shí)驗(yàn)室的計(jì)算機(jī)科學(xué)家們使用尖端的數(shù)學(xué)工具來(lái)克服這些局限。

“我們特別保持了MCL骨干的完整性，使得HipMCL成為原始MCL算法的大規(guī)模并行實(shí)現(xiàn)，”CRD的計(jì)算機(jī)科學(xué)家，該論文的第一作者Ariful Azad說(shuō)。

Azad指出，雖然之前曾嘗試將MCL算法并行化以在單個(gè)GPU上運(yùn)行，但由于GPU上的內(nèi)存限制，該工具仍然只能聚集相對(duì)較小的網(wǎng)絡(luò)。

“通過(guò)HipMCL，我們基本上可以重新編寫(xiě)MCL算法，在數(shù)千個(gè)處理器上并行運(yùn)行，并將其設(shè)置為利用所有計(jì)算節(jié)點(diǎn)中可用的聚合內(nèi)存，”他補(bǔ)充道。“HipMCL前所未有的可擴(kuò)展性來(lái)自于使用最先進(jìn)的稀疏矩陣操作算法。”

根據(jù)Buluç，從圖的許多節(jié)點(diǎn)同時(shí)執(zhí)行隨機(jī)游走最好使用稀疏矩陣矩陣乘法計(jì)算，這是最近發(fā)布的GraphBLAS標(biāo)準(zhǔn)中最基本的操作之一。Buluç和Azad為GraphBLAS的稀疏矩陣矩陣乘法開(kāi)發(fā)了一些最具可擴(kuò)展性的并行算法，并修改了其最先進(jìn)的HipMCL算法之一。

“這里的關(guān)鍵是在并行性和內(nèi)存消耗之間取得適當(dāng)?shù)钠胶?HipMCL在分配給它的可用內(nèi)存的情況下動(dòng)態(tài)提取盡可能多的并行性，”Buluç說(shuō)。

HipMCL：大規(guī)模聚類

除了數(shù)學(xué)創(chuàng)新之外，HipMCL的另一個(gè)優(yōu)勢(shì)是它能夠在任何系統(tǒng)上無(wú)縫運(yùn)行，包括筆記本電腦，工作站和大型超級(jí)計(jì)算機(jī)。研究人員通過(guò)使用C ++開(kāi)發(fā)工具并使用標(biāo)準(zhǔn)MPI和OpenMP庫(kù)來(lái)實(shí)現(xiàn)這一目標(biāo)。

“我們?cè)贜ERSC的Intel Haswell，Ivy Bridge和Knights Landing處理器上廣泛測(cè)試了HipMCL，在所有處理器上使用了多達(dá)2,000個(gè)節(jié)點(diǎn)和50萬(wàn)個(gè)線程，在所有這些運(yùn)行中，HipMCL成功地聚集了包含數(shù)千到數(shù)十億邊緣的網(wǎng)絡(luò)， “Buluç說(shuō)。“我們發(fā)現(xiàn)它可以用來(lái)運(yùn)行的處理器數(shù)量沒(méi)有障礙，并且發(fā)現(xiàn)它可以比原始MCL 算法快1000倍。”

“正如IMG和IMG / M系統(tǒng)已用于微生物組基因組學(xué)一樣，HipMCL將成為大數(shù)據(jù)計(jì)算生物學(xué)的真正轉(zhuǎn)型，”Kyrpides說(shuō)。“這一成就證明了伯克利實(shí)驗(yàn)室跨學(xué)科合作的好處。作為生物學(xué)家，我們了解科學(xué)，但能夠與計(jì)算機(jī)科學(xué)家合作能夠幫助我們解決局限并推動(dòng)我們前進(jìn)，這是非常寶貴的。”

他們的下一步是繼續(xù)為未來(lái)的exascale系統(tǒng)重新設(shè)計(jì)HipMCL和其他計(jì)算生物學(xué)工具，這些工具將能夠計(jì)算每秒鐘數(shù)的計(jì)算。這將是至關(guān)重要的，因?yàn)榛蚪M學(xué)數(shù)據(jù)繼續(xù)以令人難以置信的速度增長(zhǎng) - 每五到六個(gè)月翻一番。這將作為DOE Exascale Computing Project的Exagraph聯(lián)合設(shè)計(jì)中心的一部分完成。