Ideas for DDP
Use two levels of dynamic programming, to construct a high level scoring matrix that can be used for ordinary DP
For each residue pair (ai,bj ) this matrix should show how likely it is that the pair is on an optimal alignment
For each (ai,bj), this likelihood is found by a (low level) optimal alignment with the constraint that (ai,bj) is part of the alignment
The scores along the low level alignments are accumulated in the high level scoring matrix