GGAKE: GPU Based Genome Assembly Using K-Mer Extension

The genome assembly problem involves constructing the complete genome sequence from the reads generated by the sequencers. The Next Generation Sequencing (NGS) platforms produce a large number of short reads at a very low cost. Many assemblers have been developed to work with NGS reads. The assembly process is computation intensive and also requires a large amount of memory to store the reads. Numerous efforts are being made in recent times to parallelize the assembly process in order to reduce computation time. In this paper we present the design and development of a GPU based genome assembler (GGAKE). Our assembler works using the concept of k-mer extension. Prefix and suffix k-mers are spotted out of every read. Suffix k-mers are matched with prefix k-mers and extensions for every read are noted. Contigs are generated by extending the reads. We have implemented GGAKE on Nvidia´s GPU using the CUDA programming model and benchmarked it on five bacterial genomes. Our results prove that at high coverage GGAKE is capable of producing good quality assembly in a small amount of time.