Abstract

Pangenomes, either as a graph or as a collection of genomes, inherently capture more variability than a single reference genome. To make the transition from a reference genome as a string to a pangenome graph, it is important to have procedures for the construction of pangenome graphs that are suitable for the application of sequence-to-graph tools while working with the increasing amount of genomes demand novel methods to efficiently and accurately deal with pangenomes.

We present an approach to construct variation graphs starting from a multiple sequence alignment (MSA), leveraging the notion of maximal blocks, called pangeblocks. The MSA naturally highlights similarities and differences between a set of genomic sequences, and blocks capture a subset of sequences in an interval of columns sharing a substring in the MSA. pangeblocks is an Integer Linear programming approach that finds a tiling of the MSA using blocks. The construction is guided by…