Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Streaming algorithms for biological sequence alignment on GPUs

: Liu, Weiguo; Schmidt, Bertil; Voss, Gerrit; Müller-Wittig, Wolfgang K.


IEEE transactions on parallel and distributed systems 18 (2007), Nr.9, S.1270-1281
ISSN: 1045-9219
Fraunhofer IGD ()
dynamic programming; graphics hardware; streaming architecture; sequence alignment; general purpose computation on graphics processing unit (GPGPU)

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 of 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 more than one order of magnitude with respect to optimized CPU implementations.