GPU acceleration of Darwin read overlapper for de novo assembly of long DNA reads

Nauma Ahmed, Tong Dong Qiu, Koen Bertels, Zaid Al-Ars

Research output: Contribution to journalArticleScientificpeer-review

4 Citations (Scopus)
33 Downloads (Pure)


BACKGROUND: In Overlap-Layout-Consensus (OLC) based de novo assembly, all reads must be compared with every other read to find overlaps. This makes the process rather slow and limits the practicality of using de novo assembly methods at a large scale in the field. Darwin is a fast and accurate read overlapper that can be used for de novo assembly of state-of-the-art third generation long DNA reads. Darwin is designed to be hardware-friendly and can be accelerated on specialized computer system hardware to achieve higher performance. RESULTS: This work accelerates Darwin on GPUs. Using real Pacbio data, our GPU implementation on Tesla K40 has shown a speedup of 109x vs 8 CPU threads of an Intel Xeon machine and 24x vs 64 threads of IBM Power8 machine. The GPU implementation supports both linear and affine gap, scoring model. The results show that the GPU implementation can achieve the same high speedup for different scoring schemes. CONCLUSIONS: The GPU implementation proposed in this work shows significant improvement in performance compared to the CPU version, thereby making it accessible for utilization as a practical read overlapper in a DNA assembly pipeline. Furthermore, our GPU acceleration can also be used for performing fast Smith-Waterman alignment between long DNA reads. GPU hardware has become commonly available in the field today, making the proposed acceleration accessible to a larger public. The implementation is available at .

Original languageEnglish
Article number388
Pages (from-to)1-17
Number of pages17
JournalBMC Bioinformatics
Publication statusPublished - 2020
EventAPBC 2020: The 18th Asia Pacific Bioinformatics Conference - Seoul, Korea, Republic of
Duration: 18 Aug 202020 Aug 2020


  • De novo assembly
  • Genomics
  • GPU acceleration
  • Long DNA reads
  • Read overlapper


Dive into the research topics of 'GPU acceleration of Darwin read overlapper for de novo assembly of long DNA reads'. Together they form a unique fingerprint.

Cite this