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.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Abstract / Bemerkung
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.
Page URI


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. https://doi.org/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.

46 Zitationen in Europe PMC

Daten bereitgestellt von Europe PubMed Central.

Redox-Sensing Under Hypochlorite Stress and Infection Conditions by the Rrf2-Family Repressor HypR in Staphylococcus aureus.
Loi VV, Busche T, Tedin K, Bernhardt J, Wollenhaupt J, Huyen NTT, Weise C, Kalinowski J, Wahl MC, Fulde M, Antelmann H., Antioxid Redox Signal 29(7), 2018
PMID: 29237286
GRIM-Filter: Fast seed location filtering in DNA read mapping using processing-in-memory technologies.
Kim JS, Senol Cali D, Xin H, Lee D, Ghose S, Alser M, Hassan H, Ergin O, Alkan C, Mutlu O., BMC Genomics 19(suppl 2), 2018
PMID: 29764378
Harmonized Genome Wide Typing of Tubercle Bacilli Using a Web-Based Gene-By-Gene Nomenclature System.
Kohl TA, Harmsen D, Rothgänger J, Walker T, Diel R, Niemann S., EBioMedicine 34(), 2018
PMID: 30115606
Drug-resistance profiling and transmission dynamics of multidrug-resistant Mycobacterium tuberculosis in Saudi Arabia revealed by whole genome sequencing.
Al-Ghafli H, Kohl TA, Merker M, Varghese B, Halees A, Niemann S, Al-Hajoj S., Infect Drug Resist 11(), 2018
PMID: 30519060
Short Read Mapping: An Algorithmic Tour.
Canzar S, Salzberg SL., Proc IEEE Inst Electr Electron Eng 105(3), 2017
PMID: 28502990
A joint cross-border investigation of a cluster of multidrug-resistant tuberculosis in Austria, Romania and Germany in 2014 using classic, genotyping and whole genome sequencing methods: lessons learnt.
Fiebig L, Kohl TA, Popovici O, Mühlenfeld M, Indra A, Homorodean D, Chiotan D, Richter E, Rüsch-Gerdes S, Schmidgruber B, Beckert P, Hauer B, Niemann S, Allerberger F, Haas W., Euro Surveill 22(2), 2017
PMID: 28106529
New Mycobacterium tuberculosis Complex Sublineage, Brazzaville, Congo.
Malm S, Linguissi LS, Tekwu EM, Vouvoungui JC, Kohl TA, Beckert P, Sidibe A, Rüsch-Gerdes S, Madzou-Laboum IK, Kwedi S, Penlap Beng V, Frank M, Ntoumi F, Niemann S., Emerg Infect Dis 23(3), 2017
PMID: 28221129
Monitoring global protein thiol-oxidation and protein S-mycothiolation in Mycobacterium smegmatis under hypochlorite stress.
Hillion M, Bernhardt J, Busche T, Rossius M, Maaß S, Becher D, Rawat M, Wirtz M, Hell R, Rückert C, Kalinowski J, Antelmann H., Sci Rep 7(1), 2017
PMID: 28446771
Refined annotation of the complete genome of the phytopathogenic and xanthan producing Xanthomonas campestris pv. campestris strain B100 based on RNA sequence data.
Alkhateeb RS, Rückert C, Rupp O, Pucker B, Hublik G, Wibberg D, Niehaus K, Pühler A, Vorhölter FJ., J Biotechnol 253(), 2017
PMID: 28506932
Physiological roles of sigma factor SigD in Corynebacterium glutamicum.
Taniguchi H, Busche T, Patschkowski T, Niehaus K, Pátek M, Kalinowski J, Wendisch VF., BMC Microbiol 17(1), 2017
PMID: 28701150
Graphics processing units in bioinformatics, computational biology and systems biology.
Nobile MS, Cazzaniga P, Tangherloni A, Besozzi D., Brief Bioinform 18(5), 2017
PMID: 27402792
Emended description of Mycobacterium abscessus, Mycobacterium abscessus subsp. abscessus and Mycobacteriumabscessus subsp. bolletii and designation of Mycobacteriumabscessus subsp. massiliense comb. nov.
Tortoli E, Kohl TA, Brown-Elliott BA, Trovato A, Leão SC, Garcia MJ, Vasireddy S, Turenne CY, Griffith DE, Philley JV, Baldan R, Campana S, Cariani L, Colombo C, Taccetti G, Teri A, Niemann S, Wallace RJ, Cirillo DM., Int J Syst Evol Microbiol 66(11), 2016
PMID: 27499141
Deciphering the Transcriptional Response Mediated by the Redox-Sensing System HbpS-SenS-SenR from Streptomycetes.
Busche T, Winkler A, Wedderhoff I, Rückert C, Kalinowski J, Ortiz de Orué Lucana D., PLoS One 11(8), 2016
PMID: 27541358
Three-base periodicity of sites of sequence variation in Pseudomonas aeruginosa and Staphylococcus aureus core genomes.
Morán Losada P, Fischer S, Chouvarine P, Tümmler B., FEBS Lett 590(20), 2016
PMID: 27664047
Interclonal gradient of virulence in the Pseudomonas aeruginosa pangenome from disease and environment.
Hilker R, Munder A, Klockgether J, Losada PM, Chouvarine P, Cramer N, Davenport CF, Dethlefsen S, Fischer S, Peng H, Schönfelder T, Türk O, Wiehlmann L, Wölbeling F, Gulbins E, Goesmann A, Tümmler B., Environ Microbiol 17(1), 2015
PMID: 25156090
Evolutionary history and global spread of the Mycobacterium tuberculosis Beijing lineage.
Merker M, Blin C, Mona S, Duforet-Frebourg N, Lecher S, Willery E, Blum MG, Rüsch-Gerdes S, Mokrousov I, Aleksic E, Allix-Béguec C, Antierens A, Augustynowicz-Kopeć E, Ballif M, Barletta F, Beck HP, Barry CE, Bonnet M, Borroni E, Campos-Herrero I, Cirillo D, Cox H, Crowe S, Crudu V, Diel R, Drobniewski F, Fauville-Dufaux M, Gagneux S, Ghebremichael S, Hanekom M, Hoffner S, Jiao WW, Kalon S, Kohl TA, Kontsevaya I, Lillebæk T, Maeda S, Nikolayevskyy V, Rasmussen M, Rastogi N, Samper S, Sanchez-Padilla E, Savic B, Shamputa IC, Shen A, Sng LH, Stakenas P, Toit K, Varaine F, Vukovic D, Wahl C, Warren R, Supply P, Niemann S, Wirth T., Nat Genet 47(3), 2015
PMID: 25599400
Detoxifying Escherichia coli for endotoxin-free production of recombinant proteins.
Mamat U, Wilke K, Bramhill D, Schromm AB, Lindner B, Kohl TA, Corchero JL, Villaverde A, Schaffer L, Head SR, Souvignier C, Meredith TC, Woodard RW., Microb Cell Fact 14(), 2015
PMID: 25890161
Direct DNA Extraction from Mycobacterium tuberculosis Frozen Stocks as a Reculture-Independent Approach to Whole-Genome Sequencing.
Bjorn-Mortensen K, Zallet J, Lillebaek T, Andersen AB, Niemann S, Rasmussen EM, Kohl TA., J Clin Microbiol 53(8), 2015
PMID: 26019203
Boosting the FM-Index on the GPU: Effective Techniques to Mitigate Random Memory Access.
Chacón A, Marco-Sola S, Espinosa A, Ribeca P, Moure JC., IEEE/ACM Trans Comput Biol Bioinform 12(5), 2015
PMID: 26451818
Phenotypic Heterogeneity Affects Stenotrophomonas maltophilia K279a Colony Morphotypes and β-Lactamase Expression.
Abda EM, Krysciak D, Krohn-Molt I, Mamat U, Schmeisser C, Förstner KU, Schaible UE, Kohl TA, Nieman S, Streit WR., Front Microbiol 6(), 2015
PMID: 26696982
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
ReadXplorer--visualization and analysis of mapped sequences.
Hilker R, Stadermann KB, Doppmeier D, Kalinowski J, Stoye J, Straube J, Winnebald J, Goesmann A., Bioinformatics 30(16), 2014
PMID: 24790157
Whole-genome-based Mycobacterium tuberculosis surveillance: a standardized, portable, and expandable approach.
Kohl TA, Diel R, Harmsen D, Rothgänger J, Walter KM, Merker M, Weniger T, Niemann S., J Clin Microbiol 52(7), 2014
PMID: 24789177
CLAST: CUDA implemented large-scale alignment search tool.
Yano M, Mori H, Akiyama Y, Yamada T, Kurokawa K., BMC Bioinformatics 15(), 2014
PMID: 25495907
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

17 References

Daten bereitgestellt von Europe PubMed Central.

A block-sorting lossless data compression algorithm
Burrows, 1994
FLASH: A fast look-up algorithm for string homology
Califano, 2002
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
Two algorithms for approximate string matching in static texts
Jokinen, Lecture Notes in Computer Science 520/1991(), 1991
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
Bio-sequence database scanning on a GPU
Liu, 2006
Fast and accurate short read alignment with Burrows-Wheeler transform.
Li H, Durbin R., Bioinformatics 25(14), 2009
PMID: 19451168
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
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
Identification of common molecular subsequences.
Smith TF, Waterman MS., J. Mol. Biol. 147(1), 1981
PMID: 7265238
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


Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®


PMID: 21450712
PubMed | Europe PMC

Suchen in

Google Scholar