Rxivist logo

Detecting High Scoring Local Alignments in Pangenome Graphs

By Tizian Schulz, Roland Wittler, S. Rahmann, Faraz Hach, Jens Stoye

Posted 03 Sep 2020
bioRxiv DOI: 10.1101/2020.09.03.280958

Motivation Increasing amounts of individual genomes sequenced per species motivate the usage of pangenomic approaches. Pangenomes may be represented as graphical structures, e.g. compacted colored de Bruijn graphs, which offer a low memory usage and facilitate reference-free sequence comparisons. While sequence-to-graph mapping to graphical pangenomes has been studied for some time, no local alignment search tool in the vein of BLAST has been proposed yet. Results We present a new heuristic method to find maximum scoring local alignments of a DNA query sequence to a pangenome represented as a compacted colored de Bruijn graph. Our approach additionally allows a comparison of similarity among sequences within the pangenome. We show that local alignment scores follow an exponential-tail distribution similar to BLAST scores, and we discuss how to estimate its parameters to separate local alignments representing sequence homology from spurious findings. An implementation of our method is presented, and its performance and usability are shown. Our approach scales sublinearly in running time and memory usage with respect to the number of genomes under consideration. This is an advantage over classical methods that do not make use of sequence similarity within the pangenome. ### Competing Interest Statement The authors have declared no competing interest.

Download data

  • Downloaded 152 times
  • Download rankings, all-time:
    • Site-wide: 88,758 out of 106,159
    • In bioinformatics: 8,526 out of 9,474
  • Year to date:
    • Site-wide: 45,352 out of 106,159
  • Since beginning of last month:
    • Site-wide: None out of 106,159

Altmetric data

Distribution of downloads per paper, site-wide


Sign up for the Rxivist weekly newsletter! (Click here for more details.)