[發(fā)明專利]基于Spark和SIMD的彈性分布式序列比對(duì)系統(tǒng)及方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710637194.X
• 申請(qǐng)日: 2017-07-31
• 公開(kāi)（公告）號(hào): CN107358061A
• 公開(kāi)（公告）日: 2017-11-17
• 發(fā)明（設(shè)計(jì)）人: 徐波;王超;周學(xué)海;李曦;陳香蘭;李昌龍;莊航;王茄力;王慶鳳
• 申請(qǐng)（專利權(quán)）人: 中國(guó)科學(xué)技術(shù)大學(xué)
• 主分類號(hào): G06F19/10
• 分類號(hào): G06F19/10;G06F17/30
• 代理公司: 蘇州創(chuàng)元專利商標(biāo)事務(wù)所有限公司32103
• 代理人: 范晴,丁浩秋

技術(shù)領(lǐng)域

本發(fā)明涉及一種序列比對(duì)系統(tǒng)及方法，具體地涉及一種基于Spark和SIMD的彈性分布式序列比對(duì)系統(tǒng)及方法。

背景技術(shù)

序列比對(duì)是用來(lái)識(shí)別雙序列之間高度相似的區(qū)域，一般用比對(duì)得分來(lái)評(píng)價(jià)雙序列之間的相似度，為了方便后續(xù)分析，會(huì)計(jì)算最佳比對(duì)路徑。序列比對(duì)算法是生物信息學(xué)領(lǐng)域基本而又至關(guān)重要的算法，被廣泛應(yīng)用于基因串匹配、本地重新比對(duì)等校準(zhǔn)操作、變異分析、蛋白質(zhì)數(shù)據(jù)庫(kù)搜索等領(lǐng)域。序列比對(duì)包括本地序列比對(duì)、全局序列比對(duì)和半全局序列比對(duì)等。目前最常用的本地序列比對(duì)算法是Smith-Waterman（SW）算法，該算法也是目前最常用的序列比對(duì)算法之一。SW算法是基于動(dòng)態(tài)規(guī)劃的算法，可以找出兩序列之間的最優(yōu)本地比對(duì)。但是SW算法具有很高的時(shí)間復(fù)雜度，所以也是最慢的比對(duì)算法之一。盡管像BLAST（Basic Local Alignment Search Tool）等采用啟發(fā)式方法的算法速度更快，但是無(wú)法保證找到最優(yōu)解。由于SW算法至關(guān)重要，所以從提出到現(xiàn)在，已經(jīng)有大量的科學(xué)家提出了加速SW運(yùn)行的算法。包括基于SIMD（Single Instruction Multiple Data，單指令多數(shù)據(jù)流）指令集的加速算法、基于GPU的算法、基于FPGA的算法。相對(duì)于基于GPU、FPGA的加速方法，基于SIMD的加速方法更加通用，使用的也更頻繁。Farrar提出了將SIMD寄存器并行查詢序列但以條紋模式（Striped Pattern）訪問(wèn)的算法，相對(duì)于其他已經(jīng)被優(yōu)化的但沒(méi)有用SIMD的實(shí)現(xiàn)來(lái)說(shuō)有超過(guò)6倍的加速比。Farrar的算法已經(jīng)被嵌入到幾個(gè)流行的基因序列匹配工具中，比如BWA-MEM和Bowtie2。Zhao實(shí)現(xiàn)了一個(gè)基于SIMD的SW算法C/C++庫(kù)來(lái)方便將SW算法整合到其他基因組的應(yīng)用中，其庫(kù)名被稱作SSW（Striped Smith-Waterman），同時(shí)擴(kuò)展了Farrar的算法，除了最優(yōu)的比對(duì)得分之外還返回比對(duì)信息。SSW使用的是英特爾處理器支持的SSE2（Streaming SIMD Extensions 2）指令集。2016年Daily提出了SW算法C語(yǔ)言庫(kù)Parasail，該庫(kù)包含了不同的序列比對(duì)算法，包括SW算法、NW（Needleman-Wunsch）算法和SG（Semi-Global）算法。Parasail主要意圖是方便將序列比對(duì)算法整合到其他應(yīng)用，而不是替換目前高性能的蛋白質(zhì)搜索工具。Parasail提供了超過(guò)一千個(gè)函數(shù)，并且支持SSE2、SSE4.1、AVX2（Advanced Vector Extensions 2）和KNC（Knight's Corner）等SIMD指令集。以上這些算法主要運(yùn)行在單機(jī)環(huán)境，可擴(kuò)展性受限，難以滿足數(shù)據(jù)快速增長(zhǎng)帶來(lái)的計(jì)算需求。

由于SW算法隨著序列長(zhǎng)度的增加，其時(shí)間復(fù)雜度和空間復(fù)雜度都呈平方增加，所以SW算法也是最慢的序列比對(duì)算法之一。而傳統(tǒng)基于SIMD、GPU或FPGA等技術(shù)實(shí)現(xiàn)的SW算法可擴(kuò)展性受限，難以滿足基因數(shù)據(jù)指數(shù)增長(zhǎng)帶來(lái)的計(jì)算需求。盡管SparkSW實(shí)現(xiàn)了基于Spark的分布式SW算法，但使用純Scala代碼編寫(xiě)，沒(méi)有使用其他加速技術(shù)，所以性能較差。作者實(shí)驗(yàn)結(jié)果顯示，SparkSW最高性能只有0.346GCUPS（Giga Cell Updates Per Second）。我們通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)查詢序列長(zhǎng)度為4096字符，參考序列數(shù)據(jù)集為大小4G的1000萬(wàn)條左右序列時(shí)，SparkSW在8個(gè)物理節(jié)點(diǎn)的集群運(yùn)行需要38.53個(gè)小時(shí)。雖然SparkSW具有很好的可擴(kuò)展性，但是性能并不理想。

發(fā)明內(nèi)容

針對(duì)傳統(tǒng)序列比對(duì)算法可擴(kuò)展性的問(wèn)題和單純只使用Spark進(jìn)行計(jì)算的低性能問(wèn)題，本發(fā)明目的是：提供了一種基于Spark和SIMD的彈性分布式序列比對(duì)系統(tǒng)及方法，將Spark的分布式計(jì)算和SIMD技術(shù)的高性能進(jìn)行結(jié)合來(lái)實(shí)現(xiàn)序列比對(duì)，采用Alluxio和HDFS來(lái)分布式存儲(chǔ)數(shù)據(jù)，采用計(jì)算框架Spark進(jìn)行分布式計(jì)算，在每個(gè)節(jié)點(diǎn)采用SIMD技術(shù)進(jìn)行序列比對(duì)，提高了性能。

本發(fā)明的技術(shù)方案是：

一種基于Spark和SIMD的彈性分布式序列比對(duì)系統(tǒng)，包括一個(gè)主節(jié)點(diǎn)和與主節(jié)點(diǎn)連接的多個(gè)工作節(jié)點(diǎn)，所述主節(jié)點(diǎn)用于管理元數(shù)據(jù)和集群，包括基于分布式計(jì)算框架Spark的主節(jié)點(diǎn)、基于分布式內(nèi)存文件系統(tǒng)Alluxio的主節(jié)點(diǎn)和Hadoop分布式文件系統(tǒng)的主節(jié)點(diǎn)；