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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

HipMCL：大規(guī)模聚類

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

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

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

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