• Parallel Smith-Waterman Algorithm for Pairwise Sequence Alignment on CPU-GPU heterogeneous platform for Proceedings of the International Conference on Bioinformatics and Biomedical Engineering (ICBBE 2014)   [iCBBE 2014]
  • Author(s)
  • YingHui DONG, Fei XIA, Guoqing JIN
  • Nowadays, GPU has emerged as one promising computing platform to accelerate bio-sequence analysis applications by exploiting all kinds of parallel optimization strategies. This paper explored the parallel schemes on CPU-GPU platforms to accelerate the S-W algorithm for pair-wise sequence alignment. We tried various optimization schemes, including SIMD optimization for CPU, coalesced global memory accesses, shared memory tiles, and loop unfolding for GPU. To balance the runtimes of CPU and GPU computations, we have dynamically distributed all sequence alignment workloads over CPU and GPU, as per their compute power. Our algorithm gains an average performance of 78.3 billion cell updates per second, demonstrating significant speedups on average over other softwares.
  • Smith-Waterman Algorithm, Optimization, SIMD, GPU
  • References
  • [1]
    1. Smith, Temple F. and Waterman, Michael S. 1981. "Identification of Common Molecular Subsequences," J. Mol. Biol., 147:195-197.
    NCBI. GenBank Growth Statistics. 2012., accessed Sept. 2012.
    Y. Liu, D. Maskell, B. Schmidt. 2008. "CUDASW++: optimizing Smith-Waterman sequence database searches for CUDA-enabled graphics processing units," BMC Research Notes, 2(1), pp. 73.
    S A. Manavski and G. Valle. "CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment," Bioinformatics, 9(2): 10-19.
    L. Ligowski, W. Rudnicki. 2010. "An efficient implementation of smith waterman algorithm on GPU using cuda for massively parallel scanning of sequence databases," in Proc. of ACM SIGPLAN symposium on Principles and practice of parallel programming, pp. 137-146.
    NVIDIA Corporation. 2012. "NVIDIA CUDA BestPracticesGuide 3.1," online web site, accessed Sept. 2011.
    J. Thompson, D. Higgins, T. Gibson. 1994. "Clustalw: improving the sensitivity of progressive multiple sequence alignment through sequence weighting position specific gap penalties and weight matrix choice," Nucleic Acids Res., 22, pp. 4673-4680.
    Bowen Alpern, Larry Carter, and Kang Su Gatlin. 1995. "Microparallelism and high performance protein matching," in Proc. of ACM/IEEE Supercomputing Conference, pp. 1-24.
    A. Wozniak. 1997. "Using video-oriented instructions to speed up sequence comparison," Comput Appl Biosci., 13(2): 145-150.
    T. Rognes, E. Seeberg. 2000. "Six-fold speed-up of Smith-Waterman sequence database searches using parallel processing on common microprocessors," Bioinformatics, 16(8): 699-706.
    Arpith Jacob, Marcin Paprzycki, et al. 2007. "Applying SIMD approach to whole genome comparison on commodity hardware," in Proc. of International conference on Parallel processing and applied mathematics, pp. 1220-1229.

Engineering Information Institute is the member of/source content provider to