{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T15:44:25Z","timestamp":1772725465285,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"S13","license":[{"start":{"date-parts":[[2020,9,1]],"date-time":"2020-09-01T00:00:00Z","timestamp":1598918400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,9,17]],"date-time":"2020-09-17T00:00:00Z","timestamp":1600300800000},"content-version":"vor","delay-in-days":16,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>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.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>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.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Conclusions<\/jats:title>\n                <jats:p>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 <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/github.com\/Tongdongq\/darwin-gpu\">https:\/\/github.com\/Tongdongq\/darwin-gpu<\/jats:ext-link>.<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/s12859-020-03685-1","type":"journal-article","created":{"date-parts":[[2020,9,17]],"date-time":"2020-09-17T00:03:04Z","timestamp":1600300984000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["GPU acceleration of Darwin read overlapper for de novo assembly of long DNA reads"],"prefix":"10.1186","volume":"21","author":[{"given":"Nauman","family":"Ahmed","sequence":"first","affiliation":[]},{"given":"Tong Dong","family":"Qiu","sequence":"additional","affiliation":[]},{"given":"Koen","family":"Bertels","sequence":"additional","affiliation":[]},{"given":"Zaid","family":"Al-Ars","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,9,17]]},"reference":[{"issue":"7","key":"3685_CR1","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/BF01188580","volume":"13","author":"JD Kececioglu","year":"1995","unstructured":"Kececioglu JD, Myers EW. Combinatorial algorithms for dna sequence assembly. Algorithmica. 1995; 13(7):7\u201351.","journal-title":"Algorithmica"},{"key":"3685_CR2","unstructured":"Myers G, Tischler G, Cunial F, Pippel M. DAZZLER: Dresden Azzembler for Long Read DNA Projects. https:\/\/https:\/\/dazzlerblog.wordpress.com. Accessed 2 July 2019."},{"issue":"3","key":"3685_CR3","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1101\/gr.126953.111","volume":"22","author":"JT Simpson","year":"2012","unstructured":"Simpson JT, Durbin R. Efficient de novo assembly of large genomes using compressed data structures. Genome Res. 2012; 22(3):549\u201356.","journal-title":"Genome Res"},{"issue":"17","key":"3685_CR4","doi-asserted-by":"publisher","first-page":"9748","DOI":"10.1073\/pnas.171285098","volume":"98","author":"PA Pevzner","year":"2001","unstructured":"Pevzner PA, Tang H, Waterman MS. An eulerian path approach to dna fragment assembly. Proc Natl Acad Sci U S A. 2001; 98(17):9748\u201353.","journal-title":"Proc Natl Acad Sci U S A"},{"key":"3685_CR5","doi-asserted-by":"publisher","first-page":"074492","DOI":"10.1101\/gr.074492.107","volume":"18","author":"D Zerbino","year":"2008","unstructured":"Zerbino D, Birney E. Velvet: algorithms for de novo short read assembly using de bruijn graphs. Genome Res. 2008; 18:074492.","journal-title":"Genome Res"},{"key":"3685_CR6","doi-asserted-by":"publisher","first-page":"089532","DOI":"10.1101\/gr.089532.108","volume":"19","author":"JT Simpson","year":"2009","unstructured":"Simpson JT, Wong K, Jackman SD, Schein JE. Abyss: a parallel assembler for short read sequence data. Genome Res. 2009; 19:089532.","journal-title":"Genome Res"},{"issue":"18","key":"3685_CR7","first-page":"1","volume":"1","author":"R Luo","year":"2012","unstructured":"Luo R, Liu B, Xie Y, Li Z. Soapdenovo2: an empirically improved memory-efficient short-read de novo assembler. Gigascience. 2012; 1(18):1\u20136.","journal-title":"Gigascience"},{"key":"3685_CR8","volume-title":"Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems. ASPLOS \u201918","author":"GB Yatish Turakhia","year":"2018","unstructured":"Yatish Turakhia GB, Dally WJ. Darwin: genomics co-processor provides up to 15,000X acceleration on long read assembly. In: Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems. ASPLOS \u201918. Williamsburg: ACM: 2018. p. 199\u2013213."},{"issue":"1","key":"3685_CR9","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1186\/s12859-019-3086-9","volume":"20","author":"N Ahmed","year":"2019","unstructured":"Ahmed N, L\u00e9vy J, Ren S, Mushtaq H, Bertels K, Al-Ars Z. GASAL2: a GPU accelerated sequence alignment library for high-throughput NGS data. BMC Bioinformatics. 2019; 20(1):520.","journal-title":"BMC Bioinformatics"},{"issue":"2","key":"3685_CR10","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1186\/s12864-019-5468-9","volume":"20","author":"S Ren","year":"2019","unstructured":"Ren S, Ahmed N, Bertels K, Al-Ars Z. GPU accelerated sequence alignment with traceback for GATK HaplotypeCaller. BMC Genomics. 2019; 20(2):184.","journal-title":"BMC Genomics"},{"key":"3685_CR11","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.compbiolchem.2018.03.024","volume":"75","author":"EJ Houtgast","year":"2018","unstructured":"Houtgast EJ, Sima V-M, Bertels K, Al-Ars Z. Hardware acceleration of bwa-mem genomic short read mapping for longer read lengths. Comput Biol Chem. 2018; 75:54\u201364.","journal-title":"Comput Biol Chem"},{"issue":"1","key":"3685_CR12","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"TF Smith","year":"1981","unstructured":"Smith TF, Waterman MS. Identification of common molecular subsequences. J Mol Biol. 1981; 147(1):195\u20137.","journal-title":"J Mol Biol"},{"key":"3685_CR13","volume-title":"2016 IEEE International Conference on Bioinformatics and Biomedicine (BIBM)","author":"N Ahmed","year":"2016","unstructured":"Ahmed N, Bertels K, Al-Ars Z. A comparison of seed-and-extend techniques in modern dna read alignment algorithms. In: 2016 IEEE International Conference on Bioinformatics and Biomedicine (BIBM). Piscataway: IEEE: 2016. p. 1421\u20138."},{"issue":"3","key":"3685_CR14","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"SF Altschul","year":"1990","unstructured":"Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ. Basic local alignment search tool. J Mol Biol. 1990; 215(3):403\u201310.","journal-title":"J Mol Biol"},{"issue":"18","key":"3685_CR15","doi-asserted-by":"publisher","first-page":"3363","DOI":"10.1093\/bioinformatics\/bth408","volume":"20","author":"M Roberts","year":"2004","unstructured":"Roberts M, Hayes W, Hunt BR, Mount SM. Reducing storage requirements for biological sequence comparison. Bioinformatics. 2004; 20(18):3363\u20139.","journal-title":"Bioinformatics"},{"issue":"5","key":"3685_CR16","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1186\/s12918-018-0614-6","volume":"12","author":"E Rucci","year":"2018","unstructured":"Rucci E, Garcia C, Botella G, De Giusti A, Naiouf M, Prieto-Matias M. SWIFOLD: Smith-Waterman implementation on FPGA with OpenCL for long DNA sequences. BMC Syst Biol. 2018; 12(5):96.","journal-title":"BMC Syst Biol"},{"issue":"2","key":"3685_CR17","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1093\/bioinformatics\/btl582","volume":"23","author":"M Farrar","year":"2007","unstructured":"Farrar M. Striped smith\u2013waterman speeds database searches six times over other SIMD implementations. Bioinformatics. 2007; 23(2):156\u201361.","journal-title":"Bioinformatics"},{"issue":"6","key":"3685_CR18","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"DS Hirschberg","year":"1975","unstructured":"Hirschberg DS. A Linear Space Algorithm for Computing Maximal Common Subsequences. Commun ACM. 1975; 18(6):341\u20133.","journal-title":"Commun ACM"},{"issue":"5","key":"3685_CR19","first-page":"481","volume":"8","author":"KM Chao","year":"1992","unstructured":"Chao KM, Pearson WR, Miller W. Aligning two sequences within a specified diagonal band. Comput Appl Biosci CABIOS. 1992; 8(5):481\u20137.","journal-title":"Comput Appl Biosci CABIOS"},{"issue":"8","key":"3685_CR20","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1016\/j.parco.2009.05.002","volume":"35","author":"C Trapnell","year":"2009","unstructured":"Trapnell C, Schatz MC. Optimizing data intensive gpgpu computations for dna sequence alignment. Parallel Comput. 2009; 35(8):429\u201340.","journal-title":"Parallel Comput"},{"key":"3685_CR21","doi-asserted-by":"publisher","unstructured":"de O Sandes EF, de Melo ACMA. Smith-waterman alignment of huge sequences with gpu in linear space. In: 2011 IEEE International Parallel Distributed Processing Symposium. Piscataway: IEEE: 2011. p. 1199\u2013211. https:\/\/doi.org\/10.1109\/IPDPS.2011.114. https:\/\/ieeexplore.ieee.org\/document\/6012857\/.","DOI":"10.1109\/IPDPS.2011.114"},{"issue":"1","key":"3685_CR22","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1109\/MDAT.2013.2284198","volume":"31","author":"Y Liu","year":"2014","unstructured":"Liu Y, Schmidt B. CUSHAW2-GPU: Empowering Faster Gapped Short-Read Alignment Using GPU Computing. Des Test IEEE. 2014; 31(1):31\u201339.","journal-title":"Des Test IEEE"},{"key":"3685_CR23","volume-title":"Proc. International Symposium on Highly-Efficient Accelerators and Reconfigurable Technologies","author":"EJ Houtgast","year":"2016","unstructured":"Houtgast EJ, Sima VM, Bertels KLM, Al-Ars Z. An efficient gpu-accelerated implementation of genomic short read mapping with bwa-mem. In: Proc. International Symposium on Highly-Efficient Accelerators and Reconfigurable Technologies. Hong Kong, China: ACM: 2016."},{"key":"3685_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1756-0500-4-261","volume":"4","author":"L Hasan","year":"2011","unstructured":"Hasan L, Kentie MA, Al-Ars Z. Dopa: Gpu-based protein alignment using database and memory access optimizations. BMC Res Notes. 2011; 4:1\u201311.","journal-title":"BMC Res Notes"},{"key":"3685_CR25","volume-title":"Proc. IEEE International Conference on Bioinformatics and Biomedicine","author":"N Ahmed","year":"2017","unstructured":"Ahmed N, Mushtaq H, Bertels KLM, Al-Ars Z. Gpu accelerated api for alignment of genomics sequencing data. In: Proc. IEEE International Conference on Bioinformatics and Biomedicine. Piscataway: IEEE: 2017. p. 510\u2013515."},{"key":"3685_CR26","doi-asserted-by":"crossref","unstructured":"Turakhia Y. Darwin: A co-processor for long read alignment. https:\/\/github.com\/yatisht\/darwin. Accessed 5 Nov 2018.","DOI":"10.1145\/3173162.3173193"},{"key":"3685_CR27","unstructured":"Data release: 54x long-read coverage for PacBio-only de novo human genome assembly. 2014. https:\/\/www.pacb.com\/blog\/data-release-54x-long-read-coverage-for\/. Accessed 2 July 2019."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-020-03685-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-020-03685-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-020-03685-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,16]],"date-time":"2021-09-16T23:11:07Z","timestamp":1631833867000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-020-03685-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9]]},"references-count":27,"journal-issue":{"issue":"S13","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["3685"],"URL":"https:\/\/doi.org\/10.1186\/s12859-020-03685-1","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9]]},"assertion":[{"value":"17 September 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"388"}}