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

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

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

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

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

“隨著我們的數據增長，我們將工具轉移到高性能計算環境變得更加迫切，”他補充道。“如果你問我蛋白質空間有多大?事實上，我們并不知道，因為直到現在我們還沒有計算工具來有效地聚集我們所有的基因組數據并探測功能性暗物質。 “

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

隨機游走如何導致計算瓶頸

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

“MCL在計算生物學家中很受歡迎的原因之一是它相對無參數;用戶無需設置大量參數即可獲得準確的結果，并且對于數據的小變化非常穩定。這是這很重要，因為您可能需要重新定義數據點之間的相似性，或者您可能需要糾正數據中的輕微測量錯誤。在這些情況下，您不希望您的修改將分析從10個集群更改為1,000個集群，“ CRD科學家AydinBuluç是該論文的共同作者之一。

但是，他補充說，計算生物學社區正面臨計算瓶頸，因為該工具主要運行在單個計算機節點上，執行計算成本高并且占用大量內存 - 所有這些都限制了此算法可以聚集的數據量。

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

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

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

“我們特別保持了MCL骨干的完整性，使得HipMCL成為原始MCL算法的大規模并行實現，”CRD的計算機科學家，該論文的第一作者Ariful Azad說。

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

“通過HipMCL，我們基本上可以重新編寫MCL算法，在數千個處理器上并行運行，并將其設置為利用所有計算節點中可用的聚合內存，”他補充道。“HipMCL前所未有的可擴展性來自于使用最先進的稀疏矩陣操作算法。”

根據Buluç，從圖的許多節點同時執行隨機游走最好使用稀疏矩陣矩陣乘法計算，這是最近發布的GraphBLAS標準中最基本的操作之一。Buluç和Azad為GraphBLAS的稀疏矩陣矩陣乘法開發了一些最具可擴展性的并行算法，并修改了其最先進的HipMCL算法之一。

“這里的關鍵是在并行性和內存消耗之間取得適當的平衡.HipMCL在分配給它的可用內存的情況下動態提取盡可能多的并行性，”Buluç說。

HipMCL：大規模聚類

除了數學創新之外，HipMCL的另一個優勢是它能夠在任何系統上無縫運行，包括筆記本電腦，工作站和大型超級計算機。研究人員通過使用C ++開發工具并使用標準MPI和OpenMP庫來實現這一目標。

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

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

他們的下一步是繼續為未來的exascale系統重新設計HipMCL和其他計算生物學工具，這些工具將能夠計算每秒鐘數的計算。這將是至關重要的，因為基因組學數據繼續以令人難以置信的速度增長 - 每五到六個月翻一番。這將作為DOE Exascale Computing Project的Exagraph聯合設計中心的一部分完成。