Multipath alignments and vg mpmap

This wiki page describes a graph-based alignment concept that we sometimes work with in vg and describes how to produce and work with this alignment concept using the vg software toolkit.

Most of the sequence-to-graph alignment field has focused on aligning a sequence to a path through a graph. For instance, this is the alignment concept behind the GAM file format that is produced by vg map. In some applications, however, it can useful to work with a generalized alignment concept, which we call a multipath alignment. The same way a genome reference graph is a compressed representation of a collection of genomes, a multipath alignment is a compressed representation of a collection of alignments to these genomes. We allow the multipath alignment to bifurcate and rejoin so that it can align the same part of a sequence to multiple paths through the graph. Another way to think about this is that the multipath alignment is a graph of partial alignments. If you concatenate the partial alignments along a path in the multipath alignment's graph, it forms a sequence-to-path alignment like those contained in a GAM record.

This diagram demonstrates the multipath alignment concept. The read (top) is aligned to a graph (middle) as a sequence-to-path alignment (bottom left) and a multipath alignment (bottom right). Notice that multipath alignment aligns the same part of the read to multiple places in the graph, all of which it considers plausible. Also notice that the sequence-to-path alignment corresponds to a single path through the multipath alignment.