Computational Analysis of Biological Data on Parallel Architectures.pdf

1、并行體系結構的優(yōu)越性應該用來處理超指數(shù)增長的生物學數(shù)據(jù)，這一事實揭示了本論文的兩個方面。本文我們提出了一種計算密集型生物學數(shù)據(jù)分析的解決方案。文中所研究的生物學數(shù)據(jù)對象是生物序列、結構和網(wǎng)絡。此外，我們利用的是不同的并行體系結構，英特爾多核、多核CPU以及集群。
　　本文第一個貢獻是一種新的并行 k路原地歸并算法—Lazy-Merge。該歸并算法是本論文中整個工作的最后一步。由于本文中提出的生物學計算方法的加速算法是在將生物學數(shù)據(jù)

2、集分成可并行的較小部分基礎上進行處理的，所以該 Lazy-Merge是本文必不可少的一步。最后，一個結果中的每一部分與其他結果進行融合來形成最終結果。
　　本 Lazy-Merge算法包含三部分。第一部分描述了輸入段的劃分的過程和目的；這一部分將原來的k路歸并任務重定義為大小確定的t個較小的k路歸并任務，這里的t為劃分數(shù)。第二部分描述不連續(xù)段的歸并過程。最后一部分是以正確順序使用不完全歸并的段的算法。Lazy-Merge時間復雜度

3、分析O(k×log(n/k)).
　　我們計劃使用三種不同的數(shù)據(jù)。第一種規(guī)模上萬；他的輸入規(guī)模在到之間，我們稱之為數(shù)據(jù)集1。第二種有幾千萬的規(guī)模；大約從到，我們稱之為數(shù)據(jù)集2。增加數(shù)據(jù)集1和數(shù)據(jù)集2的方法是取其原有規(guī)模的兩倍；換句話說，將”2”的指數(shù)加1。
　　實驗結果顯示，Lazy-Merge算法在移動次數(shù)和總用時上均勝過已有算法。使用128個線程來處理數(shù)據(jù)集1和數(shù)據(jù)集2，Lazy-Merge在與重復2路原地歸并任務的比較

4、樹的比較中，平均減少了8.5倍的移動次數(shù)。移動的次數(shù)減少的程度隨劃分數(shù)的增多而上升。另外，對數(shù)據(jù)集1，Lazy-Merge相比于bitonic算法和Guan’s算法分別具有4.4倍和5.4倍的移動次數(shù)下降。對于數(shù)據(jù)集2，在規(guī)模最大的的情況下Lazy-Merge相比于bitonic算法具有3.2倍的移動次數(shù)下降。在數(shù)據(jù)集1的運行時間方面，Lazy-Merge比bitonic和Guan的算法分別快了2.5倍和292倍。在數(shù)據(jù)集2的運行時間方

5、面，Lazy-Merge相比bitonic算法表現(xiàn)出5.7倍的加速比。
　　在第二個貢獻中，我們通過解決兩大不同的問題來處理生物序列。這兩大問題是多序列聯(lián)配(MSA)問題和系統(tǒng)發(fā)育樹重建問題。
　　據(jù)我們所知，大多數(shù)現(xiàn)有的并行MSA問題的解決方法都是在工作站或者網(wǎng)絡集群上實現(xiàn)的。這種體系結構的計算機價格比較高，而且對于非專業(yè)的用戶來說使用比較困難。眾所周知，使用配有共享存儲器與多核處理器的計算機如今已經普遍存在。
　　

6、我們提出了一個在多核以及眾核體系結構中處理MSA的并行策略—CDAM。CDAM的動機是將大規(guī)模序列組分解成若干任何一個 MSA程序都可以處理的小規(guī)模子序列組。用集群的方法來分解序列組的原因是序列之間的距離越短，聯(lián)配出現(xiàn)的錯誤就會越少。
　　我們在 CDAM中采用了五種聚類算法：CD-hit，UCLUST，SiLiX，CLUSS和BLASTClust；四種主流的基準：BAliBASE，PREFAB，IRMBASE和OXBench，以

7、及28個大規(guī)模人工合成的數(shù)據(jù)集。實驗結果清晰地表明，不同的聚類方法對CDAM的速度和精度的影響各不相同，CDAM(UCLUST)和CDAM(CD-hit)的綜合性能最佳。盡管 CDAM(UCLUST)和CDAM(CD-hit)分別平均失去了2.19％和2.87%的聯(lián)配精確度，但是它們可以將算法的執(zhí)行時間分別提高151倍和111倍。
　　此處我們解決的另外一個序列分析問題是系統(tǒng)發(fā)育樹的構建。一個系統(tǒng)發(fā)育（進化）樹的構建是計算生物學中

8、的一個重大挑戰(zhàn)。系統(tǒng)發(fā)育樹描述了從 DNA多序列聯(lián)配或 AA序列（taxa）代表的生物體開始的生物體之間的進化關系。比較分析最近的調查可得出，使用ML方法的最精確、最快速的軟件工具是PHYML和RAxML。
　　我們提出了一個 PhyML的改進方法—Fast-PhyML，F(xiàn)ast-PhyML可以縮小PhyML由于序列數(shù)量的增加造成的執(zhí)行時間增加而帶來的差距。對于此處提出的軟件工具，我們進行了并行性能測試，結果顯示了加速 PhyML

9、的引導計算的潛力。該測試的測試平臺是多核和眾核體系結構、測試對象是 DNA序列和蛋白序列，獲得了相當大的加速比；由于MICCPU協(xié)處理器，MIC的加速比比多核更高。
　　作為第三個貢獻，我們處理了生物學結構。我們把蛋白質結構比對作為中心論題。
　　然而，由于新結構數(shù)目持續(xù)穩(wěn)定增長，在個人計算機或服務器上的蛋白質結構比較成為一項棘手的任務。因此，為解決這個問題，急需提供一個大規(guī)模的并行工具。
　　這一工具無論在平均數(shù)據(jù)庫

10、構建還是搜索時間上都表現(xiàn)出線性的近乎完美的加速比。在一個單獨的14核的工作站上使用這一工具，數(shù)據(jù)集3平均可以在1.9和5.6秒內完成搜索，而用3D-BLAST and PSISA則分別需要25和75秒。且這一工具對精確度沒有任何影響。
　　我們的第四個貢獻是處理了生物網(wǎng)絡。降維和可視化是有效地分析和解釋生物網(wǎng)絡的高維數(shù)據(jù)的關鍵環(huán)節(jié)。矩陣的分解和可視化，允許用戶顯示感興趣的生物網(wǎng)絡的基本結構及其隨時間演變過程。生物網(wǎng)絡可視化面臨的是

11、一個巨大的數(shù)據(jù)集。
　　我們提供了生物網(wǎng)絡快速的NMF。多核和非負矩陣分解的計算密集型任務的多核心版本（NMF）。該工具的目標是使生物網(wǎng)絡圖更簡單和更快速的降維分析。此外，它可以作為眾所周知的工具，如Cytoscape的一個插件。
　　我們利用字符串數(shù)據(jù)庫作為源數(shù)據(jù)庫。然后，針對三種不同的硬件配置，我們從眾多的數(shù)據(jù)集中提取了3個。它們的大小分別是9533，21215和25713的數(shù)據(jù)集-1，數(shù)據(jù)集-2和數(shù)據(jù)集-3。這些數(shù)據(jù)集

12、上分別用在不同的并行體系結構的多核，眾核以及多核集群。實驗結果表明，快速的NMF加速比是線性的。
　　作為最后一個也就是第五個貢獻，我們把以上所有組合成一個通用的框架—Bio-Loads-to-Nodes。該框架根據(jù)輸入的大小確定并行資源 m中的最佳數(shù)量，其中N是可用并行資源的數(shù)量，也就是內核和（或）計算節(jié)點的數(shù)目,且 m≤N。然后，框架平衡地管理通過這 m個資源分配生物數(shù)據(jù)集的過程。之后，框架管理運行數(shù)據(jù)分析程序的m個實例的執(zhí)行

13、過程,該過程處理分布式生物學數(shù)據(jù)集的分區(qū)部分。最后，框架將結果中m個不同的部分合并起來。
　　選定的方案分別是：3D-BLAST、BLAST和用于蛋白質結構比較的CpG島搜索器，序列比對和CpG島取景器。
　　對于獨立的多核節(jié)點，該框架幾乎實現(xiàn)了對3D-BLAST和BLAST分別可達7.5倍與7倍的線性加速比，而CpG Island finder的加速比只提高了5倍。這是因為加速比隨著串行程序的運行時間增加而增加，CpG I