When aligning long sequences we need to constrain the alignment in order to avoid taking too much CPU time (and RAM).
allow constraints that residue x[i] is within some distance of residue y[j] instead of requiring that they align exactly.
allow alignments within some "envelope" around an initial alignment
The problem here is that dynamic programming for 3 or more sequences allows constraints like x[i] <= y[i]. However, we must then decompose the alignment of three sequences into three pairwise alignments. This relaxes the ordering imposed encoding the alignments into paths through the dynamic programming matrix.
Ideas
Can we impose "not-less-than" constraints instead of "<=" constraints?
When aligning long sequences we need to constrain the alignment in order to avoid taking too much CPU time (and RAM).
The problem here is that dynamic programming for 3 or more sequences allows constraints like x[i] <= y[i]. However, we must then decompose the alignment of three sequences into three pairwise alignments. This relaxes the ordering imposed encoding the alignments into paths through the dynamic programming matrix.
Ideas