GRASShopPER—An algorithm for de novo assembly based on GPU alignments

• DOI: 10.1371/journal.pone.0202355
• Publication Date: 2018-08-16T17:40:29Z
• Authors: Aleksandra Swiercz; Wojciech Frohmberg; Michal Kierzynka; Pawel Wojciechowski; Piotr Zurkowski; Jan Badura; Artur Laskowski; Marta Kasprzak; Jacek Blazewicz
• Keywords: Chromosomes, Human, Pair 14; Science; Q; 0206 medical engineering; R; High-Throughput Nucleotide Sequencing; Genomics; Sequence Analysis, DNA; 02 engineering and technology; Actinomycetales; Medicine; Animals; Humans; Caenorhabditis elegans; Algorithms; Research Article

Next generation sequencers produce billions of short DNA sequences in a massively parallel manner, which causes a great computational challenge in accurately reconstructing a genome sequence de novo using these short sequences. Here, we propose the GRASShopPER assembler, which follows an approach of overlap-layout-consensus. It uses an efficient GPU implementation for the sequence alignment during the graph construction stage and a greedy hyper-heuristic algorithm at the fork detection stage. A two-part fork detection method allows us to identify repeated fragments of a genome and to reconstruct them without misassemblies. The assemblies of data sets of bacteria Candidatus Microthrix, nematode Caenorhabditis elegans, and human chromosome 14 were evaluated with the golden standard tool QUAST. In comparison with other assemblers, GRASShopPER provided contigs that covered the largest part of the genomes and, at the same time, kept good values of other metrics, e.g., NG50 and misassembly rate.