Dynamic Programming Alignments With Skips

The outcome of a Multiple Sequence Alignment (MSA) can be compactly represented by means of Elastic-Degenerate Strings (ED-strings) by collapsing conserved fragments into standard linear strings, while representing gaps and variants as sets of alternative strings. These alternative variants can differ in size and can possibly include the empty string. In 2022, Lee et al. introduced Partial Order Alignment (POA) to enable the alignment of a string against a graph-like structure derived from an MSA. However, the POA edit transcript (the sequence of edit operations that describe the alignment) does not reflect the possible elasticity of the MSA (such as different gaps sizes in the aligned string), leaving room for possible misalignment and its propagation in progressive MSA strategies. In this paper, we propose a dynamic programming based method that optimally aligns a string to an ED-string, the latter compactly representing an MSA, overcoming the ambiguity in the POA edit transcript while maintaining its time and space complexity. Moreover, since pangenomes ca also be represented using ED-strings, our algorithm paves the way to a new class of sequence to graph alignment methods capable of taking into account possible gaps in the pangenome representation, thus offering a richer and more flexible model for pangenomic analysis.