libgapmis: an ultrafast library for short-read single-gap alignment

TY - CHAP

T1 - libgapmis

T2 - IEEE International Conference on Bioinformatics and Biomedicine Workshops (BIBMW)

AU - Alachiotis, Nikolaos

AU - Berger, Simon

AU - Flouri, Tomas

AU - Pissis, Solon

AU - Stamatakis, Alexandros

PY - 2012

Y1 - 2012

N2 - A broad variety of short-read alignment programmes has been released recently to address the task of mapping tens of millions of short reads to a reference genome, placing emphasis on various aspects of the problem. Although all programmes allow for a small number of alignment mismatches, some of them either perform poorly when allowing gap insertions or they do not allow for gap insertions at all. The seed-and-extend strategy is applied in most of these programmes: after a fast alignment between a fragment of the reference sequence and a high-quality fragment of a short read-the seed-an important problem is to extend the alignment between a relatively short succeeding fragment of the reference sequence and the remaining low-quality fragment of the read allowing a number of mismatches and the insertion of gaps in the alignment. However, the length of the short reads in combination with the gap occurrence frequency observed in various applications suggest that the single-gap alignment of (parts of) those reads is desirable. In this article, we present libgapmis, an ultrafast library for pairwise short-read single-gap alignment including accelerated SSE-based and GPU-based versions. It implements an algorithm, which computes a modified version of the traditional dynamic programming matrix for sequence alignment to solve the above alignment problem. We show that the library functions of the CPU-based version are up to 20x faster compared to competing programmes, while the respective SSE-based and GPU-based versions are up to 6x and 11x faster than our CPU-based implementation, respectively. The functions made available via our library can be seamlessly integrated into any short-read alignment pipeline.

AB - A broad variety of short-read alignment programmes has been released recently to address the task of mapping tens of millions of short reads to a reference genome, placing emphasis on various aspects of the problem. Although all programmes allow for a small number of alignment mismatches, some of them either perform poorly when allowing gap insertions or they do not allow for gap insertions at all. The seed-and-extend strategy is applied in most of these programmes: after a fast alignment between a fragment of the reference sequence and a high-quality fragment of a short read-the seed-an important problem is to extend the alignment between a relatively short succeeding fragment of the reference sequence and the remaining low-quality fragment of the read allowing a number of mismatches and the insertion of gaps in the alignment. However, the length of the short reads in combination with the gap occurrence frequency observed in various applications suggest that the single-gap alignment of (parts of) those reads is desirable. In this article, we present libgapmis, an ultrafast library for pairwise short-read single-gap alignment including accelerated SSE-based and GPU-based versions. It implements an algorithm, which computes a modified version of the traditional dynamic programming matrix for sequence alignment to solve the above alignment problem. We show that the library functions of the CPU-based version are up to 20x faster compared to competing programmes, while the respective SSE-based and GPU-based versions are up to 6x and 11x faster than our CPU-based implementation, respectively. The functions made available via our library can be seamlessly integrated into any short-read alignment pipeline.

KW - short reads

KW - alignment

KW - gap

KW - vector intrinsics

KW - SSE

KW - GPGPU

KW - SEQUENCE

U2 - 10.1109/BIBMW.2012.6470221

DO - 10.1109/BIBMW.2012.6470221

M3 - Conference paper

SN - 9781467327466

VL - N/A

T3 - IEEE International Conference on Bioinformatics and Biomedicine-BIBM

SP - 688

EP - 695

BT - 2012 IEEE International Conference on Bioinformatics and Bio medicine Workshops (BIBMW)

A2 - Gao, J

A2 - Dubitzky, W

A2 - Wu, C

A2 - Liebman, M

A2 - Alhaij, R

A2 - Ungar, L

A2 - Christianson, A

A2 - Hu, null

PB - IEEE

CY - Piscataway, N.J.

Y2 - 4 October 2012 through 7 October 2012

ER -