Exact and complete short-read alignment to microbial genomes using Graphics Processing Unit programming

Blom J, Jakobi T, Doppmeier D, Jaenicke S, Kalinowski J, Stoye J, Goesmann A (2011)
Bioinformatics 27(10): 1351-1358.

Download
No fulltext has been uploaded. References only!
Journal Article | Original Article | Published | English

No fulltext has been uploaded

Abstract / Notes
Motivation: The introduction of next-generation sequencing techniques and especially the high-throughput systems Solexa (Illumina Inc.) and SOLiD (ABI) made the mapping of short reads to reference sequences a standard application in modern bioinformatics. Short-read alignment is needed for reference based re-sequencing of complete genomes as well as for gene expression analysis based on transcriptome sequencing. Several approaches were developed during the last years allowing for a fast alignment of short sequences to a given template. Methods available to date use heuristic techniques to gain a speedup of the alignments, thereby missing possible alignment positions. Furthermore, most approaches return only one best hit for every query sequence, thus losing the potentially valuable information of alternative alignment positions with identical scores. Results: We developed SARUMAN (Semiglobal Alignment of short Reads Using CUDA and NeedleMAN-Wunsch), a mapping approach that returns all possible alignment positions of a read in a reference sequence under a given error threshold, together with one optimal alignment for each of these positions. Alignments are computed in parallel on graphics hardware, facilitating an considerable speedup of this normally time-consuming step. Combining our filter algorithm with CUDA-accelerated alignments, we were able to align reads to microbial genomes in time comparable or even faster than all published approaches, while still providing an exact, complete and optimal result. At the same time, SARUMAN runs on every standard Linux PC with a CUDA-compatible graphics accelerator.
Publishing Year
ISSN
eISSN
PUB-ID

Cite this

Blom J, Jakobi T, Doppmeier D, et al. Exact and complete short-read alignment to microbial genomes using Graphics Processing Unit programming. Bioinformatics. 2011;27(10):1351-1358.
Blom, J., Jakobi, T., Doppmeier, D., Jaenicke, S., Kalinowski, J., Stoye, J., & Goesmann, A. (2011). Exact and complete short-read alignment to microbial genomes using Graphics Processing Unit programming. Bioinformatics, 27(10), 1351-1358. doi:10.1093/bioinformatics/btr151
Blom, J., Jakobi, T., Doppmeier, D., Jaenicke, S., Kalinowski, J., Stoye, J., and Goesmann, A. (2011). Exact and complete short-read alignment to microbial genomes using Graphics Processing Unit programming. Bioinformatics 27, 1351-1358.
Blom, J., et al., 2011. Exact and complete short-read alignment to microbial genomes using Graphics Processing Unit programming. Bioinformatics, 27(10), p 1351-1358.
J. Blom, et al., “Exact and complete short-read alignment to microbial genomes using Graphics Processing Unit programming”, Bioinformatics, vol. 27, 2011, pp. 1351-1358.
Blom, J., Jakobi, T., Doppmeier, D., Jaenicke, S., Kalinowski, J., Stoye, J., Goesmann, A.: Exact and complete short-read alignment to microbial genomes using Graphics Processing Unit programming. Bioinformatics. 27, 1351-1358 (2011).
Blom, Jochen, Jakobi, Tobias, Doppmeier, Daniel, Jaenicke, Sebastian, Kalinowski, Jörn, Stoye, Jens, and Goesmann, Alexander. “Exact and complete short-read alignment to microbial genomes using Graphics Processing Unit programming”. Bioinformatics 27.10 (2011): 1351-1358.
This data publication is cited in the following publications:
This publication cites the following data publications:

41 Citations in Europe PMC

Data provided by Europe PubMed Central.

Improving the genome annotation of the acarbose producer Actinoplanes sp. SE50/110 by sequencing enriched 5'-ends of primary transcripts.
Schwientek P, Neshat A, Kalinowski J, Klein A, Rückert C, Schneiker-Bekel S, Wendler S, Stoye J, Pühler A., J Biotechnol 190(), 2014
PMID: 24642337
High-resolution detection of DNA binding sites of the global transcriptional regulator GlxR in Corynebacterium glutamicum.
Jungwirth B, Sala C, Kohl TA, Uplekar S, Baumbach J, Cole ST, Pühler A, Tauch A., Microbiology 159(pt 1), 2013
PMID: 23103979
Comparative RNA-sequencing of the acarbose producer Actinoplanes sp. SE50/110 cultivated in different growth media.
Schwientek P, Wendler S, Neshat A, Eirich C, Rückert C, Klein A, Wehmeier UF, Kalinowski J, Stoye J, Pühler A., J Biotechnol 167(2), 2013
PMID: 23142701
Whole genome sequencing versus traditional genotyping for investigation of a Mycobacterium tuberculosis outbreak: a longitudinal molecular epidemiological study.
Roetzer A, Diel R, Kohl TA, Rückert C, Nübel U, Blom J, Wirth T, Jaenicke S, Schuback S, Rüsch-Gerdes S, Supply P, Kalinowski J, Niemann S., PLoS Med 10(2), 2013
PMID: 23424287
A hybrid short read mapping accelerator.
Chen Y, Schmidt B, Maskell DL., BMC Bioinformatics 14(), 2013
PMID: 23441908
New insights into Chlamydomonas reinhardtii hydrogen production processes by combined microarray/RNA-seq transcriptomics.
Toepel J, Illmer-Kephalides M, Jaenicke S, Straube J, May P, Goesmann A, Kruse O., Plant Biotechnol J 11(6), 2013
PMID: 23551401
Benchmarking short sequence mapping tools.
Hatem A, Bozdağ D, Toland AE, Çatalyürek ÜV., BMC Bioinformatics 14(), 2013
PMID: 23758764
Comprehensive discovery and characterization of small RNAs in Corynebacterium glutamicum ATCC 13032.
Mentz A, Neshat A, Pfeifer-Sancar K, Pühler A, Rückert C, Kalinowski J., BMC Genomics 14(), 2013
PMID: 24138339
Whole genome sequencing reveals complex evolution patterns of multidrug-resistant Mycobacterium tuberculosis Beijing strains in patients.
Merker M, Kohl TA, Roetzer A, Truebe L, Richter E, Rüsch-Gerdes S, Fattorini L, Oggioni MR, Cox H, Varaine F, Niemann S., PLoS One 8(12), 2013
PMID: 24324807
Comprehensive analysis of the Corynebacterium glutamicum transcriptome using an improved RNAseq technique.
Pfeifer-Sancar K, Mentz A, Rückert C, Kalinowski J., BMC Genomics 14(), 2013
PMID: 24341750
SOAP3: ultra-fast GPU-based parallel alignment tool for short reads.
Liu CM, Wong T, Wu E, Luo R, Yiu SM, Li Y, Wang B, Yu C, Chu X, Zhao K, Li R, Lam TW., Bioinformatics 28(6), 2012
PMID: 22285832
Phenylacetic acid catabolism and its transcriptional regulation in Corynebacterium glutamicum.
Chen X, Kohl TA, Rückert C, Rodionov DA, Li LH, Ding JY, Kalinowski J, Liu SJ., Appl Environ Microbiol 78(16), 2012
PMID: 22685150
Long read alignment based on maximal exact match seeds.
Liu Y, Schmidt B., Bioinformatics 28(18), 2012
PMID: 22962447
The two-component system ChrSA is crucial for haem tolerance and interferes with HrrSA in haem-dependent gene regulation in Corynebacterium glutamicum.
Heyer A, Gätgens C, Hentschel E, Kalinowski J, Bott M, Frunzke J., Microbiology 158(pt 12), 2012
PMID: 23038807

14 References

Data provided by Europe PubMed Central.


AUTHOR UNKNOWN, lecture notes in computer science 520 1991(), 1991

AUTHOR UNKNOWN, bmc bioinformatics [electronic resource] 9(), 2008
Identification of common molecular subsequences.
Smith TF, Waterman MS., J. Mol. Biol. 147(1), 1981
PMID: 7265238
SHRiMP: accurate mapping of short color-space reads.
Rumble SM, Lacroute P, Dalca AV, Fiume M, Sidow A, Brudno M., PLoS Comput. Biol. 5(5), 2009
PMID: 19461883
SOAP2: an improved ultrafast tool for short read alignment.
Li R, Yu C, Li Y, Lam TW, Yiu SM, Kristiansen K, Wang J., Bioinformatics 25(15), 2009
PMID: 19497933
SWPS3 - fast multi-threaded vectorized Smith-Waterman for IBM Cell/B.E. and x86/SSE2.
Szalkowski A, Ledergerber C, Krahenbuhl P, Dessimoz C., BMC Res Notes 1(), 2008
PMID: 18959793
PASS: a program to align short sequences.
Campagna D, Albiero A, Bilardi A, Caniato E, Forcato C, Manavski S, Vitulo N, Valle G., Bioinformatics 25(7), 2009
PMID: 19218350
Ultrafast and memory-efficient alignment of short DNA sequences to the human genome.
Langmead B, Trapnell C, Pop M, Salzberg SL., Genome Biol. 10(3), 2009
PMID: 19261174
Fast and accurate short read alignment with Burrows-Wheeler transform.
Li H, Durbin R., Bioinformatics 25(14), 2009
PMID: 19451168

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Sources

PMID: 21450712
PubMed | Europe PMC

Search this title in

Google Scholar