Comparison of Acceleration Techniques for Selected Low-Level Bioinformatics Operations

Langenkämper D, Jakobi T, Feld D, Jelonek L, Goesmann A, Nattkemper TW (2016)
Frontiers in Genetics 7: 5.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
DOI
Autor*in
Langenkämper, DanielUniBi ; Jakobi, Tobias; Feld, Dustin; Jelonek, LukasUniBi; Goesmann, Alexander; Nattkemper, Tim WilhelmUniBi
Einrichtung
Technische Fakultät > AG Biodata Mining
Centrum für Biotechnologie > Graduate Center > Graduate Cluster Industrial Biotechnology
Technische Fakultät > AG Genominformatik
Abstract / Bemerkung
Within the recent years clock rates of modern processors stagnated while the demand for computing power continued to grow. This applied particularly for the fields of life sciences and bioinformatics, where new technologies keep on creating rapidly growing piles of raw data with increasing speed. The number of cores per processor increased in an attempt to compensate for slight increments of clock rates. This technological shift demands changes in software development, especially in the field of high performance computing where parallelization techniques are gaining in importance due to the pressing issue of large sized datasets generated by e.g., modern genomics. This paper presents an overview of state-of-the-art manual and automatic acceleration techniques and lists some applications employing these in different areas of sequence informatics. Furthermore, we provide examples for automatic acceleration of two use cases to show typical problems and gains of transforming a serial application to a parallel one. The paper should aid the reader in deciding for a certain techniques for the problem at hand. We compare four different state-of-the-art automatic acceleration approaches (OpenMP, PluTo-SICA, PPCG, and OpenACC). Their performance as well as their applicability for selected use cases is discussed. While optimizations targeting the CPU worked better in the complex k-mer use case, optimizers for Graphics Processing Units (GPUs) performed better in the matrix multiplication example. But performance is only superior at a certain problem size due to data migration overhead. We show that automatic code parallelization is feasible with current compiler software and yields significant increases in execution speed. Automatic optimizers for CPU are mature and usually no additional manual adjustment is required. In contrast, some automatic parallelizers targeting GPUs still lack maturity and are limited to simple statements and structures.
Stichworte
FPGA; GPU; automatic; bioinformatics; high throughput; multi-core; parallelization; sequence analysis
Erscheinungsjahr
2016
Zeitschriftentitel
Frontiers in Genetics
Band
7
Art.-Nr.
5
ISSN
1664-8021
Page URI
https://pub.uni-bielefeld.de/record/2900943

Zitieren

Langenkämper D, Jakobi T, Feld D, Jelonek L, Goesmann A, Nattkemper TW. Comparison of Acceleration Techniques for Selected Low-Level Bioinformatics Operations. Frontiers in Genetics. 2016;7: 5.
Langenkämper, D., Jakobi, T., Feld, D., Jelonek, L., Goesmann, A., & Nattkemper, T. W. (2016). Comparison of Acceleration Techniques for Selected Low-Level Bioinformatics Operations. Frontiers in Genetics, 7, 5. doi:10.3389/fgene.2016.00005
Langenkämper, Daniel, Jakobi, Tobias, Feld, Dustin, Jelonek, Lukas, Goesmann, Alexander, and Nattkemper, Tim Wilhelm. 2016. “Comparison of Acceleration Techniques for Selected Low-Level Bioinformatics Operations”. Frontiers in Genetics 7: 5.
Langenkämper, D., Jakobi, T., Feld, D., Jelonek, L., Goesmann, A., and Nattkemper, T. W. (2016). Comparison of Acceleration Techniques for Selected Low-Level Bioinformatics Operations. Frontiers in Genetics 7:5.
Langenkämper, D., et al., 2016. Comparison of Acceleration Techniques for Selected Low-Level Bioinformatics Operations. Frontiers in Genetics, 7: 5.
D. Langenkämper, et al., “Comparison of Acceleration Techniques for Selected Low-Level Bioinformatics Operations”, Frontiers in Genetics, vol. 7, 2016, : 5.
Langenkämper, D., Jakobi, T., Feld, D., Jelonek, L., Goesmann, A., Nattkemper, T.W.: Comparison of Acceleration Techniques for Selected Low-Level Bioinformatics Operations. Frontiers in Genetics. 7, : 5 (2016).
Langenkämper, Daniel, Jakobi, Tobias, Feld, Dustin, Jelonek, Lukas, Goesmann, Alexander, and Nattkemper, Tim Wilhelm. “Comparison of Acceleration Techniques for Selected Low-Level Bioinformatics Operations”. Frontiers in Genetics 7 (2016): 5.

Zitationen in Europe PMC

Daten bereitgestellt von Europe PubMed Central.

76 References

Daten bereitgestellt von Europe PubMed Central.

Basic local alignment search tool.
Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ., J. Mol. Biol. 215(3), 1990
PMID: 2231712
PE-Assembler: de novo assembler using short paired-end reads.
Ariyaratne PN, Sung WK., Bioinformatics 27(2), 2010
PMID: 21149345
ARACHNE: a whole-genome shotgun assembler.
Batzoglou S, Jaffe DB, Stanley K, Butler J, Gnerre S, Mauceli E, Berger B, Mesirov JP, Lander ES., Genome Res. 12(1), 2002
PMID: 11779843
Phys 487 critical review paper: approaching the physical limits of integrated circuit miniaturization
Bendavid J.., 2006
Accurate whole human genome sequencing using reversible terminator chemistry.
Bentley DR, Balasubramanian S, Swerdlow HP, Smith GP, Milton J, Brown CG, Hall KP, Evers DJ, Barnes CL, Bignell HR, Boutell JM, Bryant J, Carter RJ, Keira Cheetham R, Cox AJ, Ellis DJ, Flatbush MR, Gormley NA, Humphray SJ, Irving LJ, Karbelashvili MS, Kirk SM, Li H, Liu X, Maisinger KS, Murray LJ, Obradovic B, Ost T, Parkinson ML, Pratt MR, Rasolonjatovo IM, Reed MT, Rigatti R, Rodighiero C, Ross MT, Sabot A, Sankar SV, Scally A, Schroth GP, Smith ME, Smith VP, Spiridou A, Torrance PE, Tzonev SS, Vermaas EH, Walter K, Wu X, Zhang L, Alam MD, Anastasi C, Aniebo IC, Bailey DM, Bancarz IR, Banerjee S, Barbour SG, Baybayan PA, Benoit VA, Benson KF, Bevis C, Black PJ, Boodhun A, Brennan JS, Bridgham JA, Brown RC, Brown AA, Buermann DH, Bundu AA, Burrows JC, Carter NP, Castillo N, Chiara E Catenazzi M, Chang S, Neil Cooley R, Crake NR, Dada OO, Diakoumakos KD, Dominguez-Fernandez B, Earnshaw DJ, Egbujor UC, Elmore DW, Etchin SS, Ewan MR, Fedurco M, Fraser LJ, Fuentes Fajardo KV, Scott Furey W, George D, Gietzen KJ, Goddard CP, Golda GS, Granieri PA, Green DE, Gustafson DL, Hansen NF, Harnish K, Haudenschild CD, Heyer NI, Hims MM, Ho JT, Horgan AM, Hoschler K, Hurwitz S, Ivanov DV, Johnson MQ, James T, Huw Jones TA, Kang GD, Kerelska TH, Kersey AD, Khrebtukova I, Kindwall AP, Kingsbury Z, Kokko-Gonzales PI, Kumar A, Laurent MA, Lawley CT, Lee SE, Lee X, Liao AK, Loch JA, Lok M, Luo S, Mammen RM, Martin JW, McCauley PG, McNitt P, Mehta P, Moon KW, Mullens JW, Newington T, Ning Z, Ling Ng B, Novo SM, O'Neill MJ, Osborne MA, Osnowski A, Ostadan O, Paraschos LL, Pickering L, Pike AC, Pike AC, Chris Pinkard D, Pliskin DP, Podhasky J, Quijano VJ, Raczy C, Rae VH, Rawlings SR, Chiva Rodriguez A, Roe PM, Rogers J, Rogert Bacigalupo MC, Romanov N, Romieu A, Roth RK, Rourke NJ, Ruediger ST, Rusman E, Sanches-Kuiper RM, Schenker MR, Seoane JM, Shaw RJ, Shiver MK, Short SW, Sizto NL, Sluis JP, Smith MA, Ernest Sohna Sohna J, Spence EJ, Stevens K, Sutton N, Szajkowski L, Tregidgo CL, Turcatti G, Vandevondele S, Verhovsky Y, Virk SM, Wakelin S, Walcott GC, Wang J, Worsley GJ, Yan J, Yau L, Zuerlein M, Rogers J, Mullikin JC, Hurles ME, McCooke NJ, West JS, Oaks FL, Lundberg PL, Klenerman D, Durbin R, Smith AJ., Nature 456(7218), 2008
PMID: 18987734
Ray: simultaneous assembly of reads from a mix of high-throughput sequencing technologies.
Boisvert S, Laviolette F, Corbeil J., J. Comput. Biol. 17(11), 2010
PMID: 20958248
Compiling affine loop nests for distributed-memory parallel architectures
Bondhugula U.., 2013
User's guide to mpich, a portable implementation of mpi
Bridges P., Doss N., Gropp W., Karrels E., Lusk E., Skjellum A.., 1995
QSRA: a quality-value guided de novo short read assembler.
Bryant DW Jr, Wong WK, Mockler TC., BMC Bioinformatics 10(), 2009
PMID: 19239711

Butenhof D.., 1997
ALLPATHS: de novo assembly of whole-genome shotgun microreads.
Butler J, MacCallum I, Kleber M, Shlyakhter IA, Belmonte MK, Lander ES, Nusbaum C, Jaffe DB., Genome Res. 18(5), 2008
PMID: 18340039

AUTHOR UNKNOWN, 2011
Openmp: an industry standard api for shared-memory programming
Dagum L., Menon R.., 1998
The scalable heterogeneous computing (shoc) benchmark suite
Danalis A., Marin G., McCurdy C., Meredith J., Roth P., Spafford K.., 2010
Mapreduce: simplified data processing on large clusters
Dean J., Ghemawat S.., 2008

Developers O.., 2013
TACOA: taxonomic classification of environmental genomic fragments using a kernelized nearest neighbor approach.
Diaz NN, Krause L, Goesmann A, Niehaus K, Nattkemper TW., BMC Bioinformatics 10(), 2009
PMID: 19210774
SHARCGS, a fast and highly accurate short-read assembly algorithm for de novo genomic sequencing.
Dohm JC, Lottaz C, Borodina T, Himmelbauer H., Genome Res. 17(11), 2007
PMID: 17908823
A comprehensive performance comparison of cuda and opencl
Fang J., Varbanescu A., Sips H.., 2011
Facilitate SIMD-Code-Generation in the polyhedral model by hardware-aware automatic code-transformation
Feld D., Soddemann T., Jünger M., Mallach S.., 2013
Hardware-aware automatic code-transformation to support compilers in exploiting the multi-level parallel potential of modern cpus
Feld D., Soddemann T., Jünger M., Mallach S.., 2015
The anatomy of the grid: enabling scalable virtual organizations
Foster I., Kesselman C., Tuecke S.., 2001
Open mpi: goals, concept, and design of a next generation mpi implementation
Gabriel E., Fagg G., Bosilca G., Angskun T., Dongarra J., Squyres J.., 2004
Crystallizing short-read assemblies around seeds.
Hossain MS, Azimi N, Skiena S., BMC Bioinformatics 10 Suppl 1(), 2009
PMID: 19208115
Extending assembly of short DNA sequences to handle error.
Jeck WR, Reinhardt JA, Baltrus DA, Hickenbotham MT, Magrini V, Mardis ER, Dangl JL, Jones CD., Bioinformatics 23(21), 2007
PMID: 17893086
Comparison of GPU- and CPU-implementations of mean-firing rate neural networks on parallel hardware.
Dinkelbach HU, Vitay J, Beuth F, Hamker FH., Network 23(4), 2012
PMID: 23140422
BLAT--the BLAST-like alignment tool.
Kent WJ., Genome Res. 12(4), 2002
PMID: 11932250

AUTHOR UNKNOWN, 2014
BarraCUDA - a fast short read sequence aligner using graphics processing units.
Klus P, Lam S, Lyberg D, Cheung MS, Pullan G, McFarlane I, Yeo GSh, Lam BY., BMC Res Notes 5(), 2012
PMID: 22244497
Evaluating performance and portability of opencl programs
Komatsu K., Sato K., Arai Y., Koyama K., Takizawa H., Kobayashi H.., 2010
The cache performance and optimizations of blocked algorithms
Lam M., Rothberg E., Wolf M.., 1991
AKE - the Accelerated k-mer Exploration web-tool for rapid taxonomic classification and visualization.
Langenkamper D, Goesmann A, Nattkemper TW., BMC Bioinformatics 15(), 2014
PMID: 25495116
Fast gapped-read alignment with Bowtie 2.
Langmead B, Salzberg SL., Nat. Methods 9(4), 2012
PMID: 22388286
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
Fast and accurate long-read alignment with Burrows-Wheeler transform.
Li H, Durbin R., Bioinformatics 26(5), 2010
PMID: 20080505
A survey of sequence alignment algorithms for next-generation sequencing.
Li H, Homer N., Brief. Bioinformatics 11(5), 2010
PMID: 20460430
Mapping short DNA sequencing reads and calling variants using mapping quality scores.
Li H, Ruan J, Durbin R., Genome Res. 18(11), 2008
PMID: 18714091
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
De novo assembly of human genomes with massively parallel short read sequencing.
Li R, Zhu H, Ruan J, Qian W, Fang X, Shi Z, Li Y, Li S, Shan G, Kristiansen K, Li S, Yang H, Wang J, Wang J., Genome Res. 20(2), 2009
PMID: 20019144
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
Cushaw2-gpu: empowering faster gapped short-read alignment using gpu computing
Liu Y., Schmidt B.., 2014
CUSHAW: a CUDA compatible short read aligner to large genomes based on the Burrows-Wheeler transform.
Liu Y, Schmidt B, Maskell DL., Bioinformatics 28(14), 2012
PMID: 22576173
SOAP3-dp: fast, accurate and sensitive GPU-based short read aligner.
Luo R, Wong T, Zhu J, Liu CM, Zhu X, Wu E, Lee LK, Lin H, Zhu W, Cheung DW, Ting HF, Yiu SM, Peng S, Yu C, Li Y, Li R, Lam TW., PLoS ONE 8(5), 2013
PMID: 23741504
Genome sequencing in microfabricated high-density picolitre reactors.
Margulies M, Egholm M, Altman WE, Attiya S, Bader JS, Bemben LA, Berka J, Braverman MS, Chen YJ, Chen Z, Dewell SB, Du L, Fierro JM, Gomes XV, Godwin BC, He W, Helgesen S, Ho CH, Ho CH, Irzyk GP, Jando SC, Alenquer ML, Jarvie TP, Jirage KB, Kim JB, Knight JR, Lanza JR, Leamon JH, Lefkowitz SM, Lei M, Li J, Lohman KL, Lu H, Makhijani VB, McDade KE, McKenna MP, Myers EW, Nickerson E, Nobile JR, Plant R, Puc BP, Ronan MT, Roth GT, Sarkis GJ, Simons JF, Simpson JW, Srinivasan M, Tartaro KR, Tomasz A, Vogt KA, Volkmer GA, Wang SH, Wang Y, Weiner MP, Yu P, Begley RF, Rothberg JM., Nature 437(7057), 2005
PMID: 16056220
Hyperbolic SOM-based clustering of DNA fragment features for taxonomic visualization and classification.
Martin C, Diaz NN, Ontrup J, Nattkemper TW., Bioinformatics 24(14), 2008
PMID: 18535082
Accurate phylogenetic classification of variable-length DNA fragments.
McHardy AC, Martin HG, Tsirigos A, Hugenholtz P, Rigoutsos I., Nat. Methods 4(1), 2006
PMID: 17179938
Aggressive assembly of pyrosequencing reads with mates.
Miller JR, Delcher AL, Koren S, Venter E, Walenz BP, Brownley A, Johnson J, Li K, Mobarry C, Sutton G., Bioinformatics 24(24), 2008
PMID: 18952627
A whole-genome assembly of Drosophila.
Myers EW, Sutton GG, Delcher AL, Dew IM, Fasulo DP, Flanigan MJ, Kravitz SA, Mobarry CM, Reinert KH, Remington KA, Anson EL, Bolanos RA, Chou HH, Jordan CM, Halpern AL, Lonardi S, Beasley EM, Brandon RC, Chen L, Dunn PJ, Lai Z, Liang Y, Nusskern DR, Zhan M, Zhang Q, Zheng X, Rubin GM, Adams MD, Venter JC., Science 287(5461), 2000
PMID: 10731133
SSAHA: a fast search method for large DNA databases.
Ning Z, Cox AJ, Mullikin JC., Genome Res. 11(10), 2001
PMID: 11591649

AUTHOR UNKNOWN, 2015

AUTHOR UNKNOWN, 2013

AUTHOR UNKNOWN, 2014

AUTHOR UNKNOWN, 2015

AUTHOR UNKNOWN, 2013

AUTHOR UNKNOWN, 2015
Having a BLAST with bioinformatics (and avoiding BLASTphemy).
Pertsemlidis A, Fondon JW 3rd., Genome Biol. 2(10), 2001
PMID: 11597340
An Eulerian path approach to DNA fragment assembly.
Pevzner PA, Tang H, Waterman MS., Proc. Natl. Acad. Sci. U.S.A. 98(17), 2001
PMID: 11504945

Rajic H., Brobst R., Chan W., Ferstl F., Gardiner J., Haas A.., 2004
Human genome 10th anniversary. Will computers crash genomics?
Pennisi E., Science 331(6018), 2011
PMID: 21310981
DNA sequencing with chain-terminating inhibitors.
Sanger F, Nicklen S, Coulson AR., Proc. Natl. Acad. Sci. U.S.A. 74(12), 1977
PMID: 271968
Human-mouse alignments with BLASTZ.
Schwartz S, Kent WJ, Smit A, Zhang Z, Baertsch R, Hardison RC, Haussler D, Miller W., Genome Res. 13(1), 2003
PMID: 12529312
Accurate multiplex polony sequencing of an evolved bacterial genome.
Shendure J, Porreca GJ, Reppas NB, Lin X, McCutcheon JP, Rosenbaum AM, Wang MD, Zhang K, Mitra RD, Church GM., Science 309(5741), 2005
PMID: 16081699
ABySS: a parallel assembler for short read sequence data.
Simpson JT, Wong K, Jackman SD, Schein JE, Jones SJ, Birol I., Genome Res. 19(6), 2009
PMID: 19251739
Minimus: a fast, lightweight genome assembler.
Sommer DD, Delcher AL, Salzberg SL, Pop M., BMC Bioinformatics 8(), 2007
PMID: 17324286
A comprehensive benchmark study of multiple sequence alignment methods: current challenges and future perspectives.
Thompson JD, Linard B, Lecompte O, Poch O., PLoS ONE 6(3), 2011
PMID: 21483869

TimeLogic A.., 2013

AUTHOR UNKNOWN, 2013
Polyhedral parallel code generation for cuda
Verdoolaege S., Carlos J., Cohen A., Ignacio J., Tenllado C., Catthoor F.., 2013
Designing modular hardware accelerators in c with roccc 2.0
Villarreal J., Park A., Najjar W., Halstead R.., 2010
GPU-BLAST: using graphics processors to accelerate protein sequence alignment.
Vouzis PD, Sahinidis NV., Bioinformatics 27(2), 2010
PMID: 21088027
Assembling millions of short DNA sequences using SSAKE.
Warren RL, Sutton GG, Jones SJ, Holt RA., Bioinformatics 23(4), 2006
PMID: 17158514
GMAP: a genomic mapping and alignment program for mRNA and EST sequences.
Wu TD, Watanabe CK., Bioinformatics 21(9), 2005
PMID: 15728110
Slurm: simple linux utility for resource management
Yoo A., Jette M., Grondona M.., 2003
Velvet: algorithms for de novo short read assembly using de Bruijn graphs.
Zerbino DR, Birney E., Genome Res. 18(5), 2008
PMID: 18349386
G-BLASTN: accelerating nucleotide alignment by graphics processors.
Zhao K, Chu X., Bioinformatics 30(10), 2014
PMID: 24463183
Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®
Quellen

PMID: 26904094
PubMed | Europe PMC

Suchen in

Google Scholar