A. Swiercz, W. Frohmberg, M. Kierzynka, P. Wojciechowski, P. Zurkowski,
J. Badura, A. Laskowski, M. Kasprzak, J. Blazewicz
"GRASShopPER − An algorithm for de novo assembly based on
GPU alignments"
PLoS ONE
13 (2018) e0202355.
Download full text
Abstract:
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.
Back to the List of publications
20 Aug 2018