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

王 濤

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

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

王 濤

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

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

高性能計算應用；計算生物學；序列分析

1 引言

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

2 序列分析

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

2.1 雙序列比對

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

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

Figure 1 Wavefront technique

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

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

2.2 多序列比對

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

2.3 數據庫檢索

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

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

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

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

2.4 重測序

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

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

2.5 基因組組裝

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

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

3 結束語

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

[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.

附中文參考文獻：

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

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

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

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

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

[65] 林皎，陳文光，栗強，等. 基于圖劃分的全基因組并行拼接算法 [J]. 計算機研究與發展, 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-),男,江西九江人，博士后,高級工程師,研究方向為高性能計算和計算化學。E-mail:taowang328@hotmail.com

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

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