[BiO BB] Optimal Sequence Alignment - Affine Gap Penalty

[Alex Dow]

Hello,

I'm looking for a source related to optimal alignments with an affine
gap penalty. To explain my query, I assume basic knowledge of dynamic
programming and affine gap penalty.

Consider aligning 2 sequences. The obvious method of using dynamic
programming requires 3 matrices (or, equivalently, 3 values in each
cell of a single matrix), one that results from a gap in one sequence,
one from a gap in the other, and one that results from a gap in
neither sequence. Durbin, et al.'s Biological Sequence Analysis (1998)
refers to an algorithm that uses only 2 matrices, one that results
from a gap in either sequence, and one that results from a gap in
neither sequence (pages 30-31). They claim that a constraint on the
cost function will guarantee optimal results from this algorithm, only
he offers no proof or citation. Certainly there is a paper that
demonstrates this result, only I have been unable to find it.

I would appreciate any information you may have on this, whether it is
a citation or even an assurance that such a paper exists.

Thanks,

Alex