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

2015-03-27王涛

计算机工程与科学 2015年1期

关键词：基因组测序数据库

王涛

(上海超级计算中心，上海 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

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