《面向異構並行系統的生物序列比對並行策略及算法研究》是依託湖南大學，由周炎濤擔任項目負責人的面上項目。
基本介紹
- 中文名：面向異構並行系統的生物序列比對並行策略及算法研究
- 項目類別：面上項目
- 項目負責人：周炎濤
- 依託單位：湖南大學
中文摘要,結題摘要,
中文摘要
序列比對是生物信息學中重要的基本問題,是生物信息學的基礎,可用來預測序列的功能、結構和進化過程等. 隨著大規模測序技術日益成熟,序列數據呈指數級增長,使得現有序列比對並行策略中存在的可擴展性問題日益突出.同時,現有的序列比對並行策略多使用同構系統求解,且極少採用數據並行方案. 隨著高性能計算系統快速發展,套用異構並行系統求解各類NP難解問題已變得越來越普及和流行. 本項研究將在異構並行系統中求解序列比對問題.首先提出一種異構並行系統計算能力描述模型,然後設計基於聚類的新的數據並行策略,最後通過0-1整數規劃求解並行調度最優解,並設計近似最優的啟發式算法.本項研究不僅為生物序列比對基於異構超級計算機的並行化策略和方法奠定基礎,為生物信息學中數據密集套用提供高性能計算解決方法,還將拓寬超級計算機套用領域,推動生物信息學的研究與發展.
結題摘要
面向異構並行系統的序列比對並行策略研究，不僅設計異構並行系統計算能力描述模型，還為序列比對的並行策略和算法設計提供新思路，從而為生物信息學的更廣泛套用奠定基礎；同時還將豐富傳統並行處理的研究內容，推動生物信息學和高性能計算與超級計算機系統的研究與發展。 本項目（1）針對序列比對算法的可擴展性問題，提出基於分治法的序列比對通用算法(DCPA)。通過將大規模序列集分割成能被現有算法處理的小的序列子集，在多核計算機實現大規模序列數據的處理。分別使用基準多序列比對庫和大規模序列集測試DCPA算法的性能。實驗結果表明，相對於經典的序列比對算法MUSCLE，DCPA獲得了近111倍的性能加速，且維持較好的比對精度。 （2）進一步研究序列集分割策略，提出基於數據並行的序列比對算法(CDAM)。CDAM算法套用聚類方法分割序列集，設計最長處理時間優先算法(LPT)分發序列子集，以及設計漸進式序列子集合併策略獲得大規模序列集的比對結果。分別套用Cd-hit，UCLUST，SiLiX，CLUSS和BLASTClust等5種聚類算法到CDAM的序列集分割階段。實驗結果表明：在這5種套用不同聚類方法的CDAM程式中，CDAM(UCLUST)和CDAM(Cd-hit) 整體性能良好。相對於經典的序列比對算法MUSCLE，它們分別獲得了151倍和111倍的性能加速，損失了2.19%和2.87%的比對精度。 （3）提出基於CPU+GPU異構系統的MAFFT序列比對並行算法。分別在NVIDIA Tesla C2050、Tesla M2090和Tesla K20m GPU上測試基於異構系統的MAFFT序列比對並行算法。與串列和多執行緒MAFFT算法相比，在維持相同比對精度的同時，在Tesla K20m GPU上分別獲得了56.7和7.1的性能加速。 （4）提出一種新的多序列比對算法(CROMSA)。使用基準多序列比對庫測量CROMSA的比對精度和計算複雜度。實驗結果表明，CROMSA在比對精度上優於本文提出的DCPA、CDAM(Cd-hit)、和CDAM(UCLUST)。由於需要花費較長時間來最佳化比對結果，CROMSA較這些算法比對時間長。但相對於當前其他流行算法ProbCons和MUMMALS，CROMSA具有明顯的比對時間優勢，進一步地說明了套用化學最佳化方法求解序列比對問題的有效性。
