计算生物学中的高性能计算（Ⅱ）—序列分析

摘要/Abstract

摘要：

序列分析是高性能计算应用的一个重要方向。随着高通量测序技术的发展，基因数据呈现爆炸性增长，对高性能计算的需求也更加迫切。介绍了高性能计算在序列分析中的应用和序列分析算法的并行实现，包括序列比对、检索、重测序、拼接等。

Abstract:

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.

Key words: high performance computing application;computation biology sequence analysis

王涛. 计算生物学中的高性能计算（Ⅱ）—序列分析[J]. J4, 2015, 37(01): 7-13.

WANG Tao. High performance computing in computational
biology (Ⅱ)—sequence analysis [J]. J4, 2015, 37(01): 7-13.

参考文献

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

[1]	赵婧1，魏彬2，陈明淑1，张晓娟1. 基于神经网络预测的SNP信息的剪接点识别算法研究[J]. J4, 2016, 38(05): 885-890.
[2]	王涛. 计算生物学中的高性能计算（Ⅰ）—分子动力学[J]. J4, 2014, 36(12): 2242-2250.
[3]	杨国强，窦文华. 一种新的因特网拓扑的序列分析方法：dM序列分析方法[J]. J4, 2011, 33(3): 1-6.
[4]	李兴绪[1] 崔建福[2]. MATLAB在金融时间序列分析及建模中的应用[J]. J4, 2004, 26(7): 100-104.