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.