Streaming Algorithms for Biological Sequence Alignment on GPUs

Weiguo Liu, Bertil Schmidt, Gerrit Voss, Wolfgang M. Wittig
Nanyang Technol. Univ., Singapore
IEEE Trans. Parallel Distrib. Syst. In Parallel and Distributed Systems, IEEE Transactions on, Vol. 18, No. 9. (2007), pp. 1270-1281.


   title={Streaming algorithms for biological sequence alignment on GPUs},

   author={Weiguo, L. and Schmidt, B. and Voss, G. and Muller-Wittig, W.},

   journal={Parallel and Distributed Systems, IEEE Transactions on},








Source Source   



Sequence alignment is a common and often repeated task in molecular biology. Typical alignment operations consist of finding similarities between a pair of sequences (pairwise sequence alignment) or a family of sequences (multiple sequence alignment). The need for speeding up this treatment comes from the rapid growth rate of biological sequence databases: every year their size increases by a factor 1.5 to 2. In this paper we present a new approach to high performance biological sequence alignment based on commodity PC graphics hardware. Using modern graphics processing units (GPUs) for high performance computing is facilitated by their enhanced programmability and motivated by their attractive price/performance ratio and incredible growth in speed. To derive an efficient mapping onto this type of architecture, we have reformulated dynamic programming based alignment algorithms as streaming algorithms in terms of computer graphics primitives. Our experimental results show that the GPU-based approach allows speedups of over one order of magnitude with respect to optimized CPU implementations.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2020 hgpu.org

All rights belong to the respective authors

Contact us: