計(jì)算生物學(xué)中的高性能計(jì)算(Ⅱ)—序列分析*

王 濤

(上海超級計(jì)算中心，上海 201203)

計(jì)算生物學(xué)中的高性能計(jì)算(Ⅱ)—序列分析*

王 濤

(上海超級計(jì)算中心，上海 201203)

序列分析是高性能計(jì)算應(yīng)用的一個重要方向。隨著高通量測序技術(shù)的發(fā)展，基因數(shù)據(jù)呈現(xiàn)爆炸性增長，對高性能計(jì)算的需求也更加迫切。介紹了高性能計(jì)算在序列分析中的應(yīng)用和序列分析算法的并行實(shí)現(xiàn)，包括序列比對、檢索、重測序、拼接等。

高性能計(jì)算應(yīng)用；計(jì)算生物學(xué)；序列分析

1 引言

生物學(xué)中的計(jì)算應(yīng)用包括序列分析(生物信息學(xué))、全原子模擬(分子動力學(xué)和量子力學(xué)計(jì)算)、生物網(wǎng)絡(luò)(系統(tǒng)生物學(xué))等。在過去的幾十年里，計(jì)算生物學(xué)已經(jīng)發(fā)展成為一門成熟的學(xué)科。生物信息的爆炸性增長、生物過程中相互作用的復(fù)雜性、分子級別生物組織的多樣性和關(guān)聯(lián)性等都需要人們使用高性能并行計(jì)算機(jī)、網(wǎng)格計(jì)算以及其它最新的體系架構(gòu)來開展計(jì)算研究。盡管全球已有很多大型超級計(jì)算機(jī)被用于計(jì)算生物學(xué)研究，但生物信息學(xué)軟件的擴(kuò)展性、移植性、集成度、可用性等仍然有許多問題需要解決，包括將已有的序列分析軟件移植到現(xiàn)代的機(jī)群，使用網(wǎng)格計(jì)算、云計(jì)算等分布式技術(shù)解決大規(guī)模并行計(jì)算，利用加速卡(FPGA、GPU、MIC等)和大規(guī)模并行架構(gòu)處理大規(guī)模數(shù)據(jù)等。近年來，隨著高通量測序技術(shù)的進(jìn)步，在短時間內(nèi)(幾個小時)以很小的代價(幾千美元)對百萬量級的基因片段進(jìn)行測序已成為可能，測序分析已成為生物實(shí)驗(yàn)室的常規(guī)手段。因此，如何采用先進(jìn)的計(jì)算算法和計(jì)算硬件以減少計(jì)算分析時間，處理超大規(guī)模的數(shù)據(jù)，已成為生物信息學(xué)領(lǐng)域的重要挑戰(zhàn)。本文將主要介紹高性能計(jì)算在序列分析中的應(yīng)用和序列分析算法的并行實(shí)現(xiàn)，包括序列比對、檢索、重測序、組裝等。

2 序列分析

序列同源性檢測或序列比對，是所有生物信息學(xué)序列分析SA(Sequence Analysis)中最主要的計(jì)算任務(wù)。隨著序列數(shù)據(jù)庫的指數(shù)性增長，這種計(jì)算操作也變得越來越困難。一般來說，這種比對操作可以分為三類：一對一、一對多、多對多。一對一比對操作稱之為雙序列比對PSA(Pairwise Sequence Alignment)，用于計(jì)算兩個序列之間的最優(yōu)編輯距離(edit distance)，同時必須考慮基因突變因素如取代、插入、缺失等。一對多比對是在一個序列數(shù)據(jù)庫中進(jìn)行序列查詢檢索。多對多比對是將多個序列統(tǒng)一分析，以判明序列的子群特征如同源等。多序列比對MSA(Multiple Sequence Alignment)就屬于這一類。在所有這些比對操作中，序列可以是DNA或蛋白質(zhì)，計(jì)算操作主要涉及整數(shù)運(yùn)算。

2.1 雙序列比對

將兩個序列進(jìn)行比對是基因組學(xué)中的基本操作。出于生物學(xué)和算法的原因，在序列分析應(yīng)用中，雙序列比對還產(chǎn)生了很多其它形式。生物學(xué)上的應(yīng)用包括反映從一個序列進(jìn)化到另外一個序列的全局比對，表征保守子序列(例如結(jié)構(gòu)基元)的局部比對，通過兩個基因發(fā)現(xiàn)保留外顯子的剪接比對等[1]。使用比對算法的需求來源于基因組大小與實(shí)驗(yàn)可讀取的DNA 片段長度之間的多個數(shù)量級差異。例如，一個序列后綴與另外一個序列前綴的比對可以用于DNA片段拼接，DNA片段與某類物種基因模板的比對可以用于重測序。

盡管實(shí)際應(yīng)用各有不同，PSA問題可以采用動態(tài)規(guī)劃算法來解決，算法的時間復(fù)雜度為O(mn)，空間復(fù)雜度為O(m+n)[1]，m和n是比對的序列長度。在所有的應(yīng)用當(dāng)中，求解包括填充一個或多個大小為(m+1)×(n+1)的表，表中的單元[i,j]與單元[i-1,j]、[i,j-1]和[i-1,j-1]相關(guān)。PSA計(jì)算的并行實(shí)現(xiàn)一般有兩種，最常使用的方式是基于如下原理：反對角線上的單元是相互獨(dú)立的，只依賴于前兩個反對角斜線上的單元(三個單元)，因而可以并行計(jì)算[2]。如圖1所示，E與A、B、D相關(guān)而與C、F無關(guān)，因此C、E、F可以并行計(jì)算，整體計(jì)算可以按照反對角線一條一條向下推進(jìn)。此項(xiàng)技術(shù)稱為波前技術(shù)。

Figure 1 Wavefront technique

第二種技術(shù)則是利用并行前綴算法(圖1中，A、B、C三者之間的關(guān)系就是一個典型的前綴計(jì)算)，每次計(jì)算表的一行[3]。這種方法優(yōu)化后，可以獲得O(mn/p)的時間復(fù)雜度，但很難獲得O((m+n)/p)的空間復(fù)雜度，p為并行的線程數(shù)。盡管文獻(xiàn)[4]中給出了空間復(fù)雜度的解決方式，但在實(shí)際應(yīng)用中很少采用。

PSA已經(jīng)在各種主要的加速卡平臺上實(shí)現(xiàn)了并行，包括FPGA平臺[5,6]、GPU平臺[7,8]、Cell BE處理器平臺[9,10]、眾核系統(tǒng)[11]、片上系統(tǒng)[12]等，這些實(shí)現(xiàn)或者采用反對角線方法，或者采用并行前綴算法。例如，在FPGA平臺上[5]，動態(tài)規(guī)劃表沿著數(shù)據(jù)庫序列方向分成小塊，在線性脈動陣列上采用反對角線并行方式，陣列上的每一個處理單元計(jì)算矩陣的一行。在GPU平臺上[8]，GPU被用于加速Smith-Waterman算法[13](一種采用動態(tài)規(guī)劃算法的局部比對方法)，計(jì)算采用反對角線并行方法，通過菱形數(shù)據(jù)布局以更充分地利用GPU的并行處理能力，最高可獲得120倍以上的性能提升。

2.2 多序列比對

多序列比對(MSA)是PSA問題的自然擴(kuò)展，它可以在多個序列中發(fā)現(xiàn)保守子序列，因而常常用于查找多個蛋白質(zhì)序列(例如基因家族)中的共同結(jié)構(gòu)域和結(jié)構(gòu)基元。由于在保留功能的同時，蛋白質(zhì)的一級結(jié)構(gòu)可以有明顯的變化，因而可以使用MSA查找多個序列中存在的弱相似性。而這種相似性在雙序列比對時并不明顯。

2.3 數(shù)據(jù)庫檢索

在已知序列數(shù)據(jù)庫中檢索給定序列以找出同源序列，可能是生物信息學(xué)中使用最頻繁和最有價值的操作。此類檢索一般涉及局部序列比對，本質(zhì)上是重復(fù)多次成千上萬次的PSA。人們已經(jīng)開發(fā)了大量的局部序列比對算法，包括Smith-Waterman算法[13]、FASTA(FAST-ALL)算法[20]、BLAST(Basic Local Alignment Search Tool)算法[21]等等[22～24]。Smith-Waterman算法采用動態(tài)規(guī)劃法，是局部比對算法中的基礎(chǔ)算法。由于其計(jì)算結(jié)果是最優(yōu)解，因此往往作為其他算法計(jì)算結(jié)果的參考，但這種算法計(jì)算時間過長。為了減少給定序列與每一個數(shù)據(jù)庫序列直接比對的開銷，在合理的時間內(nèi)完成比對檢索操作，在實(shí)際應(yīng)用中，人們一般采用啟發(fā)性算法，在降低敏感度的情況下，提高比對速度。FASTA算法是一種啟發(fā)式算法，它進(jìn)行整體聯(lián)配，重點(diǎn)查找那些可能達(dá)到匹配顯著的聯(lián)配。雖然FASTA算法不會錯過那些匹配極好的序列，但有時會漏過一些匹配程度不高但達(dá)到顯著水平的序列。BLAST算法是目前最流行的局部序列比對算法。它也是一種啟發(fā)式算法，基于匹配短序列片段，用一種統(tǒng)計(jì)模型來確定未知序列與數(shù)據(jù)庫序列的最佳局部聯(lián)配。其主要工作原理是同源序列的最優(yōu)比對通常包含精確匹配的區(qū)域。BLAST算法一般分為四步：單詞匹配(尋找種子)、非空位延伸、空位延伸以及比對回溯。

BLAST算法有大量的并行實(shí)現(xiàn)[25～29]，常用的并行實(shí)現(xiàn)是將數(shù)據(jù)庫進(jìn)行分割，每個計(jì)算單元處理數(shù)據(jù)庫的一部分。由于將數(shù)據(jù)庫分割成小塊，因而每個計(jì)算單元在進(jìn)行處理的時候，分割的數(shù)據(jù)庫可以全部讀入內(nèi)存或緩存，減少了磁盤的I/O，從而大幅提高計(jì)算速度。此外，由于BLAST的并行實(shí)現(xiàn)對通信的要求很低，因而可以較好地使用分布式計(jì)算模式[30]。

在FPGA、GPU等協(xié)處理器平臺上，BLAST算法的并行也有大量的實(shí)現(xiàn)[31～38]。在FPGA平臺上，文獻(xiàn)[31]根據(jù)數(shù)據(jù)庫大小和查詢序列長度的不同，對BLAST類算法提出了三種不同的建議，并進(jìn)行了部分實(shí)現(xiàn)。文獻(xiàn)[32]在FPGA上加速了BLAST算法的第一步，并行實(shí)現(xiàn)了布隆過濾器(Bloom Filter)模塊、假陽性消除模塊以及冗余消除模塊，在減少片外哈希表訪問數(shù)和低匹配率的條件下獲得了更好的計(jì)算效率。在GPU平臺上，減少操作和數(shù)據(jù)之間的偏離，設(shè)計(jì)和布局好數(shù)據(jù)結(jié)構(gòu)是獲得良好性能的關(guān)鍵。數(shù)據(jù)庫可以先根據(jù)目標(biāo)序列的長度進(jìn)行預(yù)排序，然后并發(fā)掃描長度相似的部分，使并發(fā)線程的執(zhí)行時間盡可能一致。文獻(xiàn)[35]通過合理分割數(shù)據(jù)庫，在主CPU上對查詢序列進(jìn)行預(yù)處理生成查詢索引表，CPU和GPU同時進(jìn)行序列比對，對BLAST算法的前兩步實(shí)現(xiàn)了GPU加速。文獻(xiàn)[36] 在單詞匹配階段，引入了一個由CPU生成的壓縮確定有限狀態(tài)自動機(jī)DFA(Deterministic Finite Automaton)來存儲查詢序列的單詞匹配信息；在延伸階段，采用修改的Smith-Waterman算法計(jì)算一個矩形區(qū)域，充分利用反對角線上數(shù)據(jù)的獨(dú)立性來并行加速；在GPU上實(shí)現(xiàn)了BLAST算法的前三步。文獻(xiàn)[37]也對BLAST算法構(gòu)造單詞表和單詞匹配擴(kuò)展進(jìn)行了并行實(shí)現(xiàn)，分別取得了3～7倍的加速性能。

除了BLAST算法外，其它常用的局部序列比對算法也實(shí)現(xiàn)了GPU加速或Intel Xeon Phi加速[39,40]。例如，文獻(xiàn)[39]報(bào)道了Smith-Waterman算法的GPU實(shí)現(xiàn)。該實(shí)現(xiàn)耦合CPU與GPU的SIMD指令集，共同進(jìn)行蛋白質(zhì)數(shù)據(jù)庫的快速檢索。此外，所有的目標(biāo)序列按序列長度升序進(jìn)行預(yù)排序，工作負(fù)載動態(tài)、均衡地分布在CPU和GPU上。CPU上的計(jì)算使用多線程和向量擴(kuò)展單元上的SIMD，GPU上的計(jì)算使用新一代GPU架構(gòu)上的SIMD視頻指令集以獲得更好的并行性。文獻(xiàn)[40]報(bào)道了Smith-Waterman算法在Intel Xeon Phi平臺上的實(shí)現(xiàn)，它有效利用了眾核處理器上實(shí)現(xiàn)的粗粒度并行機(jī)制和每個核上512位寬的SIMD上實(shí)現(xiàn)的細(xì)粒度并行機(jī)制，在蛋白質(zhì)數(shù)據(jù)庫快速檢索方面取得了較好的性能和并行效率。

2.4 重測序

重測序是對已知基因組序列的物種進(jìn)行不同個體的基因組測序，并在此基礎(chǔ)上對個體或群體進(jìn)行差異性分析。當(dāng)個體的基因出現(xiàn)變異時，由于這種變異通常情況下非常小，因而可以通過使用比對程序?qū)€體基因片段定位到基因模板，來進(jìn)行個體測序。這個方法正被越來越多地用于人類個體基因測序，以研究基因變異及其影響，從而實(shí)現(xiàn)個人保健和醫(yī)療方案的定制化。片段定位(Reads Mapping)屬于計(jì)算密集型操作，并且需要反復(fù)執(zhí)行以滿足大量的個體測序需求，因而對執(zhí)行速度有相當(dāng)?shù)囊?。由于重測序涉及上億DNA片段的定位，不宜使用PSA方法將個體片段定位到模板，因而常常使用啟發(fā)式算法來快速表征可能的定位位置。即便如此，人類基因組重測序所花費(fèi)的計(jì)算時間仍然需要以日來計(jì)算。

人們已經(jīng)發(fā)展很多計(jì)算方法和軟件實(shí)現(xiàn)用于重測序或序列比對，包括SOAP(Short Oligonudeotide Alignment Program)、BWA/MAQ、Bowtie、Subread等等[41～45]。SOAP[41]是較早出現(xiàn)的短序比對工具，能夠在較小內(nèi)存的機(jī)器上將短序比對用于人類基因組這樣的大數(shù)據(jù)上去。BWA/MAQ[42,43]具有較高的準(zhǔn)確率，Bowtie[44]的計(jì)算速度較快，可采用多線程的方式進(jìn)行多核的并行計(jì)算。為了加速片段定位的過程，F(xiàn)PGA和GPU平臺也被廣泛地用于重測序[46～52]。在FPGA平臺上，F(xiàn)PGA被用于處理計(jì)算密集型的種子生成和延伸過程[46]。延伸階段使用條帶(Banded)比對算法，采用并行的block-wise 比對結(jié)構(gòu)來近似傳統(tǒng)的動態(tài)規(guī)劃算法，以提高計(jì)算效率。另外一種基于BWT(Burrows-Wheeler Transform)方法[53]的非確切序列定位算法也在FPGA上進(jìn)行了實(shí)現(xiàn)[47]。在該實(shí)現(xiàn)中，遞歸計(jì)算用層次結(jié)構(gòu)表來處理，并使用雙堿基延伸DBE(Dual-Base Extension)方法進(jìn)行并行化，將BWT類方法中最耗時的后綴數(shù)組間隔搜索用FPGA來加速。在GPU平臺上，定位問題被研究得更為廣泛?；贐WT和FM索引(Ferragina Manzini-index)[54]，CUSHAW軟件[48]使用質(zhì)量感知邊界搜索方法，只將替換作為非精確匹配的一部分，在減少搜索空間的同時取得較高的比對質(zhì)量。它使用多線程設(shè)計(jì)，通過每個線程比對不同的片段來實(shí)現(xiàn)粗粒度并行。而頻繁的全局內(nèi)存訪問限制了該軟件的性能。另外一種片段定位程序[49]在保持?jǐn)?shù)據(jù)訪問對稱性和本地內(nèi)存使用最大化的同時，通過在相同參考搜索樹上并發(fā)搜索不同片段來實(shí)現(xiàn)并行。文獻(xiàn)[50]提出了一種過濾驗(yàn)證算法。它采用雙向BWT搜索和直接匹配方式，過濾的部分在GPU上執(zhí)行，后綴數(shù)組轉(zhuǎn)換部分在CPU上處理。SOAP3軟件[51]也是基于BWT索引數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。它通過啟發(fā)式算法識別導(dǎo)致大量不同分支出現(xiàn)的模式，并用CPU處理。同時，CPU還會在非結(jié)構(gòu)化比對時分擔(dān)GPU負(fù)載。SOAP3并不處理插入和缺失，而僅僅使用全局內(nèi)存會導(dǎo)致一定的性能限制。該軟件的另外一個后續(xù)版本[52]SOAP3-DP，通過短子串(種子)確切比對或不匹配比對來識別候選區(qū)域，然后采用動態(tài)規(guī)劃法進(jìn)行片段的詳細(xì)比對。對較長片段，該版本性能會下降。

2.5 基因組組裝

基因組組裝是指將大量的短DNA序列重新組合成一個能代表原基因組目標(biāo)序列的過程?；蚪M組裝問題產(chǎn)生的來源在于被測序的基因組缺少基因組模板，例如從頭測序一個迄今未編序的物種，或者變異數(shù)量過于龐大以至于映射到一個模板是不可行的。在這些情況下，基因組必須利用overlaps或基因片段中出現(xiàn)的其它信息直接重構(gòu)。然而由于測序技術(shù)每次只能讀取幾百個DNA堿基，要從數(shù)百萬個重疊、重復(fù)、甚至不準(zhǔn)確的基因片段中直接拼接出DNA結(jié)構(gòu)進(jìn)行全基因組組裝是非常困難的。目前最常用的一種測序方法是全基因組鳥槍法WGS(Whole Genome Shotgun)[55]測序。該方法將DNA分子打碎成可被讀取的小碎片(稱之為“reads”或片段)，通常會產(chǎn)生上百萬的碎片，每個碎片由103量級或更少的堿基組成。為了彌補(bǔ)可能的讀取錯誤，多份DNA被同時測序產(chǎn)生多個overlaps，覆蓋或冗余因子常常在5～12。盡管這種覆蓋或冗余的方式可以獲得更好的overlaps，進(jìn)而獲得更準(zhǔn)確的結(jié)果，但數(shù)據(jù)膨脹了很多倍，導(dǎo)致處理過程成為了計(jì)算密集型操作，因而需要采用并行計(jì)算或分布式計(jì)算來加速序列拼接。

目前，使用最為廣泛的兩種基于圖的拼接算法分別是OLC(Overlap-Layout-Consensus)算法[56,57]和de Bruijn圖算法[58]。這兩種方法將問題簡化為圖，通過一次性遍歷所有的節(jié)點(diǎn)(產(chǎn)生哈密頓量)或邊(產(chǎn)生歐拉路徑)得到共有序列。OLC算法由三步組成：找到reads中的重復(fù)區(qū)域和overlaps；建立layout；找到共有序列。de Bruijn圖算法包括產(chǎn)生k-mers(輸入序列被分割成長度為k的子序列，稱之為k-mers)；分發(fā)k-mers(適用于并行算法)；準(zhǔn)備數(shù)據(jù)；建立de Bruijn圖；遍歷歐拉路徑。OLC算法適合于小基因組內(nèi)較長的reads，而de Bruijn圖算法更適合于大規(guī)模的短reads。目前已有很多拼接軟件基于這兩種算法實(shí)現(xiàn)了并行[59～65]。大多數(shù)軟件采用OpneMP或多線程并行的方式在共享內(nèi)存系統(tǒng)上實(shí)現(xiàn)加速，如Velvet[59]、SOAPdenovo[60]、PCAP[61]、PASQUAL[62]等。此類軟件一般可以得到較好的拼接結(jié)果，對較小的基因組有很好的表現(xiàn)。對于較大規(guī)模的基因組，隨著數(shù)據(jù)量的增長，此類軟件對硬件的要求較高，需要較大的內(nèi)存容量，缺乏擴(kuò)展性，拼接時間過長。另外一種并行方式是采用MPI工具實(shí)現(xiàn)分布式并行，如ABySS[63]、Ray[64]等，通過對數(shù)據(jù)進(jìn)行劃分，分發(fā)到各個工作節(jié)點(diǎn)進(jìn)行拼接，實(shí)現(xiàn)了對海量數(shù)據(jù)的處理。此類方法擴(kuò)展性較好，整體運(yùn)行速度快，對計(jì)算機(jī)硬件的要求較低，但數(shù)據(jù)劃分可能會帶來誤差，導(dǎo)致拼接結(jié)果碎片化且不夠準(zhǔn)確。更多基因拼接并行算法分析和性能分析可參考文獻(xiàn)[66,67]。在協(xié)處理器平臺上，基因拼接軟件也有一些實(shí)現(xiàn)，例如GPU被用于加速序列拼接過程中的錯誤校正和比對步驟，獲得了較好的加速性能[40,68,69]。

3 結(jié)束語

隨著下一代測序技術(shù)的廣泛應(yīng)用，測序數(shù)據(jù)和基因數(shù)據(jù)呈現(xiàn)爆炸性增長。進(jìn)一步縮短序列分析時間，在可接受的時間和可接受的精度范圍內(nèi)得到分析結(jié)果已成為人們的迫切需求。生物信息學(xué)中的計(jì)算主要涉及整數(shù)操作，序列分析中的算法問題往往是一個離散數(shù)學(xué)或組合數(shù)學(xué)問題，具有天然的并行性。充分利用高性能計(jì)算軟硬件技術(shù)的特點(diǎn)可以極大縮短序列分析的處理時間。序列分析計(jì)算中的通信量少，屬于計(jì)算密集型和訪存密集型，因而較容易實(shí)現(xiàn)OpenMP或多線程并行。分布式并行主要能夠解決序列分析計(jì)算內(nèi)存需求過大、共享內(nèi)存計(jì)算機(jī)擴(kuò)展性不足的問題，但數(shù)據(jù)庫分割會帶來精度不夠、誤差較大等問題。隨著協(xié)處理器技術(shù)的進(jìn)步，GPU、Intel Xeon Phi等協(xié)處理器進(jìn)一步提高計(jì)算能力，完善編程環(huán)境，未來的協(xié)處理器平臺可能成為序列分析領(lǐng)域的主要計(jì)算平臺。綜合利用主機(jī)CPU和協(xié)處理器計(jì)算單元，改進(jìn)數(shù)據(jù)訪問模型，合理分配數(shù)據(jù)，控制內(nèi)存使用可能是一個改進(jìn)的方向。

[1] Aluru S.Handbook of computational molecular biology [M]. Boca Raton:CRC Press, 2005.

[2] Edmiston E W, Core N G, Saltz J H, et al. Parallel processing of biological sequence comparison algorithms [J]. International Journal of Parallel Programming, 1988, 17(3):259-275.

[3] Aluru S, Futamura N, Mehrotra K. Parallel biological sequence comparison using prefix computations [J]. Journal of Parallel and Distributed Computing, 2003, 63(3):264-272.

[4] Rajko S, Aluru S. Space and time optimal parallel sequence alignments [J]. IEEE Transactions on Parallel and Distributed Systems, 2004, 15(12):1070-1081.

[5] Allred J, Coyne J, Lynch W, et al. Smith-waterman implementation on a FSB-FPGA module using the Intel accelerator abstraction layer [C]∥Proc of IEEE International Parallel & Distributed Processing Symposium, 2009:1-4.

[6] Benkrid K, Liu Y, Benkrid A. A highly parameterized and efficient FPGA-based skeleton for pairwise biological sequence alignment [J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2009, 17(4):561-570.

[7] Weiguo L, Schmidt B, Voss G, et al. Streaming algorithms for biological sequence alignment on GPUs [J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2007, 18(9):1270-1281.

[8] Lin Jiang, Tang Min, Tong Ruo-feng. GPU accelerated biological sequence alignment [J]. Journal of Computer-Aided Design & Computer Graphics, 2010, 22(3):420-427.(in Chinese)

[9] Sarje A, Aluru S. Parallel biological sequence alignments on the cell broadband engine[C]∥Proc of IEEE International Parallel & Distributed Processing Symposium, 2008:1-11.

[10] Sachdeva V, Kistler M, Speight E, et al. Exploring the viability of the cell broadband engine for bioinformatics applications [J]. Parallel Computing, 2008, 34(11):616-626.

[11] Díaz D, Esteban F J, Hernández P, et al. Parallelizing and optimizing a bioinformatics pairwise sequence alignment algorithm for many-core architecture [J]. Parallel Computing, 2011, 37(4):244-259.

[12] Sarkar S, Kulkarni D R, Pande P P, et al. Network-on-chip hardware accelerators for biological sequence alignment [J]. IEEE Transactions on Computers, 2010, 59(1);29-41.

[13] Smith T F, Waterman M S. Identification of common molecular subsequences [J]. Journal of Molecular Biology, 1981, 147(1):195-197.

[14] Oliver T, Schmidt B, Nathan D, et al. Using reconfigurable hardware to accelerate multiple sequence alignment with clustalW [J]. Bioinformatics, 2005, 21(16):3431-3432.

[15] Lloyd S, Snell Q O. Accelerated large-scale multiple sequence alignment [J]. BMC Bioinformatics, 2011, 12(1):466.

[16] Wei Shu-feng, Liu Yu, Jiang Cai-yun. GPU-based parallelization research of genetic annealing algorithm for multiple sequence alignment [J]. Computer Engineering and Design, 2014, 35(4):1247-1252.(in Chinese)

[17] Blazewicz J, Frohmberg W, Kierzynka M, et al. G-MSA - A GPU-based, fast and accurate algorithm for multiple sequence alignment [J]. Journal of Parallel and Distributed Computing, 2013, 73(1):32-41.

[18] Vandierendonck H, Rul S, De Bosschere K. Accelerating multiple sequence alignment with the cell BE processor [J]. The Computer Journal, 2010, 53(6):814-826.

[19] Larkin1M A, Blackshields G, Brown N P, et al. Clustal W and Clustal X version 2.0 [J]. Bioinformatics, 2007, 23(21):2947-2948.

[20] Lipman D J, Pearson W R. Rapid and sensitive protein similarity searches [J]. Science, 1985, 227(4693):1435-1441.

[21] Altschul S F, Gish W, Miller W, et al. Basic local alignment search tool [J]. Journal of Molecular Biology, 1990, 215(3):403-410.

[22] Delcher A L, Kasif S, Fleischmann R D, et al. Alignment of whole genomes [J]. Nucleic Acids Research, 1999, 27(11):2369-2376.

[23] Ma B,Tromp J,Li M.PatternHunter:faster and more sensitive homology search [J]. Bioinformatics, 2002, 18(3):440-445.

[24] Kent W J. BLAT-The BLAST-like alignment tool [J]. Genome Research, 2002, 12(4):656-664.

[25] Darling A E, Carey L, Feng W C. The design, implementation, and evaluation of mpiBLAST [C]∥Proc of the 4th International Conference on Linux Clusters, 2003, 1-14.

[26] Nguyen V H, Lavenier D. PLAST:parallel local alignment search tool for database comparison [J]. BMC Bioinformatics, 2009, 10(10):329.

[27] Rognes T.ParAlign:A parallel sequence alignment algorithm for rapid and sensitive database searches [J]. Nucleic Acids Research, 2001, 29(7):1647-1652.

[28] Mathog D. Parallel BLAST on split databases [J]. Bioinformatics, 2003, 19(14):1865-1866.

[29] Tan Guang-ming, Xu Lin, Zhou You-ying, et al. Exploiting parallelization of BLAST on dawning 4000A [J]. Computer Engineering, 2006, 32(10):45-46.(in Chinese)

[30] Yang C T, Han T F, Kan H C. G-BLAST:A grid-based solution for mpiBLAST on computational grids [J]. Concurrency and Computation:Practice & Experience, 2009, 21(2):225-255.

[31] Sotiriades E, Dollas A. A general reconfigurable architecture for the BLAST algorithm [J]. Journal of Vlsi Signal Processing Systems for Signal Image and Video Technology, 2007, 48(3):189-208.

[32] Chen Y, Schmidt B, Maskell D L. Reconfigurable accelerator for the word-matching stage of BLASTN [J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2013, 21(4):659-669.

[33] Jacob A, Lancaster J, Buhler J, et al. Mercury BLASTP:Accelerating protein sequence alignment [J]. ACM Transactions on Reconfigurable Technology and Systems, 2008, 1(2):9.

[34] Herbordt M C, Model J, Sukhwani B, et al. Single pass streaming BLAST on FPGAs [J]. Parallel Computing, 2007, 33(10-11):741-756.

[35] Vouzis P D, Sahinidis N V. GPU-BLAST:Using graphics processors to accelerate protein sequence alignment [J]. Bioinformatics, 2011, 27( 2):182-188.

[36] Liu W, Schmidt B, Muller-Wittig W. CUDA-BLASTP:Accelerating BLASTP on CUDA-enabled graphics hardware [J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2011, 8(6):1678-1684.

[37] Pei Song-wen, Wang Xin-yi, Wei Gang, et al. Research on parallel BLAST algorithm based on multi-core stream processors [J]. Journal of System Simulation, 2011, 23(10):2065-2069.(in Chinese)

[38] Wan Ning, Xie Hai-bo, Zhang Qing, et al. A preliminary exploration on parallelized BLAST algorithm using GPU [J]. Computer Engineering & Science, 2009, 31(11):98-101.(in Chinese)

[39] Liu Y, Wirawan A, Schmidt B. CUDASW++ 3.0:Accelerating smith-waterman protein database search by coupling CPU and GPU SIMD instructions[J]. BMC Bioinformatics, 2013, 14(1):117.

[40] Liu Y, Schmidt B. SWAPHI:Smith-waterman protein database search on Xeon Phi coprocessors[C]∥Proc of 2014 IEEE 25th International Conference on Application-specific Systems, Architectures and Processors (ASAP), 2014:184-185.

[41] Li R, Li Y, Kristiansen K, et al. SOAP:Short oligonucleotide alignment program [J]. Bioinformatics, 2008, 24(5):713-714.

[42] Li H, Durbin R. Fast and accurate short read alignment with Burrows-Wheeler transform [J]. Bioinformatics, 2009, 25(14):1754-1760.

[43] Li H, Ruan J, Durbin R. Mapping short DNA sequencing reads and calling variants using mapping quality scores [J]. Genome Research, 2008, 18(11):1851-1858.

[44] Langmead B,Trapnell C,Pop M,et al.Ultrafast and memory-efficient alignment of short DNA sequences to the human genome[J]. Genome Biology, 2009, 10(3):R25.

[45] Liao Y, Smyth G K, Shi W. The subread aligner:Fast, accurate and scalable read mapping by seed-and-vote [J]. Nucleic Acids Research, 2013, 41(10):e108.

[46] Chen Y, Schmidt B, Maskell D L. A hybrid short read mapping accelerator [J]. BMC Bioinformatics, 2013, 14(2):67.

[47] Xin Y, Liu B, Min B, et al. Parallel architecture for DNA sequence inexact matching with burrows-wheeler transform [J]. Microelectronics Journal, 2013, 44(8):670-682.

[48] Liu Y,Schmidt B,Maskell D L.CUSHAW:A CUDA compatible short read aligner to large genomes based on the burrows-wheeler transform [J]. Bioinformatics, 2012, 28(14):1830-1837.

[49] Torres J S, Espert I B, Dominguez A T, et al. Using GPUs for the exact alignment of short-read genetic sequences by means of the burrows-wheeler transform [J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2012, 9(4):1245-1256.

[50] Lu M, Tan Y, Bai G, et al. High-performance short sequence alignment with GPU acceleration [J]. Distributed and Parallel Databases, 2012, 30(5-6):385-399.

[51] Liu C M, Wong T, Wu E, et al. SOAP3:Ultra-fast GPU-based parallel alignment tool for short reads [J]. Bioinformatics, 2012, 28(6):878-879.

[52] Luo R, Wong T, Zhu J, et al. SOAP3-dp:Fast, accurate and sensitive GPU-based short read aligner [J]. PLoS ONE, 2013, 8(5):e65632.

[53] Burrows M, Wheeler D J. A block sorting lossless data compression algorithm [R]. Technical Report 124, Palo Alto:Digital Equipment Corporation, 1994.

[54] Ferragina P, Manzini G. Indexing compressed text [J]. Journal of the ACM, 2005, 52(4):552-581.

[55] Edwards A, Voss H, Rice P, et al. Automated DNA sequencing of the human HPRT locus [J]. Genomics, 1990, 6(4):593-608.

[56] Huang X,Madan A.CAP3:A DNA sequence assembly program [J]. Genome Research, 1999, 9(9):868-877.

[57] Batzoglou S, Jaffe D, Stanley K, et al. Arachne:A whole-genome shotgun assembler [J]. Genome Research, 2002, 12(1):177-189.

[58] Pevzner P,Tang H,Waterman S.An eulerian path approach to DNA fragment assembly [J]. Proceedings of National Academy of Sciences of the United States of America, 2001, 98(17):9748-9753.

[59] Zerbino D, Birney E. Velvet:Algorithms for de Novo short read assembly using de bruijn graphs[J]. Genome Research, 2008, 18(5):821-829.

[60] Li R, Zhu H, Ruan J, et al. De Novo assembly of human genomes with massively parallel short read sequencing [J]. Genome Research, 2010, 20(2):265-272.

[61] Huang X, Wang J, Aluru S, et al. PCAP:A whole-genome assembly program [J]. Genome Research, 2003, 13(9):2164-2170.

[62] Liu X, Pande P R, Meyerhenke H, et al. PASQUAL:Parallel techniques for next generation genome sequence assembly [J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(5):977-986.

[63] Simpson J T, Wong K, Jackman S D, et al. ABySS:A parallel assembler for short read sequence data[J]. Genome Research, 2009, 19(6):1117-1123.

[64] Boisvert S, Laviolette F, Corbeil J. Ray:Simultaneous assembly of reads from a mix of high-throughput sequencing technologies [J]. Journal of Computational Biology, 2010, 17(11):1519-1533.

[65] Lin Jiao,Chen Wen-guang,Li Qiang,et al.A new data clustering algorithm for parallel whole-genome shotgun sequence assembly [J]. Journal of Computer Research and Development, 2006, 43(8):1323-1329.(in Chinese)

[66] Zhang W, Chen J, Yang Y, et al. A practical comparison of de Novo genome assembly software tools for next-generation sequencing technologies[J]. PLoS ONE, 2011, 6(3):e17915.

[67] Ahmed M, Ahmad I, Khan S U. A comparative analysis of parallel computing approaches for genome assembly [J]. Interdisciplinary Sciences:Computational Life Sciences, 2011, 3(1):57-63.

[68] Shi H, Schmidt B, Liu W, et al. A parallel algorithm for error correction in high-throughput short-read data on CUDA-enabled graphics hardware [J]. Journal of Computational Biology, 2010, 17(4):603-615.

[69] Trapnell C, Schatz M C. Optimizing data Intensive GPGPU computations for DNA sequence alignment [J]. Parallel Computing, 2009, 35(8-9):429-440.

附中文參考文獻(xiàn)：

[8] 林江，唐敏，童若鋒. GPU加速的生物序列比對 [J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2010, 22(3):420-427.

[16] 韋樹烽，劉羽，蔣財(cái)運(yùn). 基于GPU的遺傳退火多序列比對并行研究 [J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2014, 35(4):1247-1252.

[29] 譚光明，徐琳，周幼英，等. 基于曙光4000A的BLAST并行算法 [J]. 計(jì)算機(jī)工程, 2006, 32(10):45-46.

[37] 裴頌文，王心怡，韋剛，等. 基于多核流處理器的BLAST并行化算法研究 [J]. 系統(tǒng)仿真學(xué)報(bào), 2011, 23(10):2065-2069.

[38] 萬寧，謝海波，張清，等. 使用GPU加速BLAST算法初探 [J]. 計(jì)算機(jī)工程與科學(xué), 2009, 31(11):98-101.

[65] 林皎，陳文光，栗強(qiáng)，等. 基于圖劃分的全基因組并行拼接算法 [J]. 計(jì)算機(jī)研究與發(fā)展, 2006, 43(8):1323-1329.

WANG Tao,born in 1977,post doctor,senior engineer,his research interests include high performance computing, and computational chemistry.

High performance computing in computational biology (Ⅱ)—sequence analysis

WANG Tao

(Shanghai Supercomputer Center,Shanghai 201203,China)

Sequence analysis is an important domain of high performance computing applications.With the development of high-throughput sequencing technique,there is an explosive growth in genome data,and the demand for high performance computing becomes more urgent.The paper introduces the applications of high performance computing in sequence analysis and parallel implementation of sequence analysis algorithms, including sequence alignment,database search,resequencing, and genome assembly.

high performance computing application;computation biology sequence analysis

1007-130X(2015)01-0007-07

2014-10-15;

2014-12-20

Q811.4；TP301

A

10.3969/j.issn.1007-130X.2015.01.002

王濤(1977-),男,江西九江人，博士后,高級工程師,研究方向?yàn)楦咝阅苡?jì)算和計(jì)算化學(xué)。E-mail:taowang328@hotmail.com

通信地址：201203 上海市浦東新區(qū)上海超級計(jì)算中心郭守敬路585號

Address:Shanghai Supercomputer Center,585 Guoshoujing Rd,Pudong District,Shanghai 201203,P.R.China