雙序統(tǒng)計顯著性評估的高性能算法研究.pdf

1、生物序列數(shù)據(jù)呈爆炸性趨勢增長。如何處理這些海量數(shù)據(jù)，挖掘出蘊含于數(shù)據(jù)之中的生物學(xué)意義，是生物信息學(xué)領(lǐng)域的一個巨大挑戰(zhàn)。另一個挑戰(zhàn)來自于高性能計算平臺下的適用并行軟件的匱乏，這種匱乏在很大程度上制約著高性能計算平臺上的計算能力。設(shè)計生物信息學(xué)領(lǐng)域適用的高性能計算平臺下的并行軟件，加速分析和處理大數(shù)據(jù)集的生物序列數(shù)據(jù)，顯得尤為重要。
　　相比于傳統(tǒng)的數(shù)據(jù)庫統(tǒng)計顯著性，雙序統(tǒng)計顯著性能夠更為準(zhǔn)確地相關(guān)聯(lián)(同源)序列。然而，由于其本身固有

2、的計算密集性，雙序統(tǒng)計顯著性的評估過程是非常耗時的。此外，雙序統(tǒng)計顯著性的評估準(zhǔn)確度也有待進一步的提升。基于此，本文對雙序統(tǒng)計顯著性的高性能評估算法進行了深入的研究，并取得了以下創(chuàng)新性成果：
　　1.提出基于非統(tǒng)一內(nèi)存訪問(Non-Uniform Memory Access，NUMA)構(gòu)架下的多核處理器的雙序統(tǒng)計顯著性評估的高性能算法。針對阿姆達爾加速評估模型在多核處理器環(huán)境下的不足，提出了一個新的評估模型，通過考慮引入多核環(huán)境下

3、帶來的額外開銷(如線程同步、數(shù)據(jù)拷貝等)，能更為準(zhǔn)確地找出系統(tǒng)加速中的性能瓶頸。通過性能分析得知，雙序統(tǒng)計顯著性評估有三大計算密集核：序列重排、序列比對和參數(shù)擬合。算法優(yōu)化了序列比對中的時間復(fù)雜度和空間復(fù)雜度。通過調(diào)整NUMA體系結(jié)構(gòu)下的運行參數(shù)，克服了NUMA效應(yīng)。實驗表明，在使用24核處理器的情況下，相比于串行執(zhí)行程序，評估算法獲得的最大性能加速可達22.65倍。
　　2．提出基于分布式節(jié)點與NUMA多核處理器混合構(gòu)架下的雙序

4、統(tǒng)計顯著性算法。該算法利用分布式內(nèi)存環(huán)境下的大規(guī)模計算節(jié)點提升了整個評估系統(tǒng)的性能空間，同時利用每個節(jié)點內(nèi)的多核處理器共享內(nèi)存機制，節(jié)省了內(nèi)存消耗。此外，取代基于目標(biāo)序列數(shù)量的平衡負載調(diào)度策略，設(shè)計了一個新的基于序列長度總和的負載平衡調(diào)度算法。相比于串行執(zhí)行程序，在跨域43個節(jié)點使用1024個處理器核的情況下，混合構(gòu)架環(huán)境下加速算法獲得的最大性能加速可達621.73倍。
　　3．提出基于通用圖形處理器的自適應(yīng)數(shù)據(jù)切片的雙序統(tǒng)計顯著

5、性評估算法。該算法根據(jù)GPU的硬件配置特征，自適應(yīng)地調(diào)整傳輸至GPU中的目標(biāo)序列數(shù)量，確保GPU的高占有率(occupancy)。同時，為了提高全局內(nèi)存的訪問速度，通過對目標(biāo)序列及其混排副本進行內(nèi)存布局重組，使之支持合并訪問。在使用雙 GPU Tesla C2050情況下，自適應(yīng)數(shù)據(jù)切片的雙序統(tǒng)計顯著性評估算法，相比于串行執(zhí)行程序，獲得的最大性能加速可達369.95倍，GCUPS峰值達到25.50。
　　4．提出一組適用于雙序統(tǒng)計

6、顯著性的評估策略，包括特定評分矩陣定制、比對分值審查的參數(shù)擬合等，顯著地提高了評估的準(zhǔn)確度。通過對替換評分矩陣的各向異性定制，取代標(biāo)準(zhǔn)替換評分矩陣來評估序列比對的分值，最大程度的利用查詢序列自身的特征信息。通過比對分值審查的極大似然參數(shù)估計方法，顯著地提升極值分布中統(tǒng)計參數(shù)擬合的準(zhǔn)確度。通過上述評估策略的優(yōu)化，相比于BLAST、SSEARCH等序列分析系統(tǒng)提供的數(shù)據(jù)庫統(tǒng)計顯著性評估，在相同查詢序列誤報數(shù)(Error per Query)