An Efficient GPU-based de Bruijn Graph Construction Algorithm for Micro-Assembly

Shanshan Ren, Nauman Ahmed, Koen Bertels, Zaid Al-Ars

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

3 Citations (Scopus)
151 Downloads (Pure)

Abstract

In order to improve the accuracy of indel detection, micro-assembly is used in multiple variant callers, such as the GATK HaplotypeCaller to reassemble reads in a specific region of the genome. Assembly is a computationally intensive process that causes runtime bottlenecks. In this paper, we propose a GPU-based de Bruijn graph construction algorithm for micro-assembly in the GATK HaplotypeCaller to improve its performance. Various synthetic datasets are used to compare the performance of the GPU-based de Bruijn graph construction implementation with the software-only baseline, which achieves a speedup of up to 3x. An experiment using two human genome datasets is used to evaluate the performance shows a speedup of up to 2.66x.
Original languageEnglish
Title of host publicationProceedings - 2018 IEEE 18th annual IEEE International Conference on BioInformatics and BioEngineering (BIBE 2018)
EditorsNikolaos G. Bourbakis, Despina Kavraki
Place of PublicationPiscataway, NJ, USA
PublisherIEEE
Pages67-72
Number of pages6
ISBN (Electronic)978-153866216-8
DOIs
Publication statusPublished - 2018
EventBIBE 2018 : 18th International Conference on Bioinformatics and Bioengineering - Taichung, Taiwan
Duration: 6 Dec 20186 Dec 2018

Conference

ConferenceBIBE 2018 : 18th International Conference on Bioinformatics and Bioengineering
Country/TerritoryTaiwan
CityTaichung
Period6/12/186/12/18

Keywords

  • De Bruijn graph construction
  • GPU acceleration
  • Micro-assembly
  • Repeat k-mers

Fingerprint

Dive into the research topics of 'An Efficient GPU-based de Bruijn Graph Construction Algorithm for Micro-Assembly'. Together they form a unique fingerprint.

Cite this