[ssml] Algorithm for optimal sequence alignment with an affine gap penalty

[Alex Dow]

Hello,

I'm looking for a source related to optimal alignments with an affine
gap penalty. I previously posted this request to BiO_Bulletin_Board
and was referred here.

Consider aligning 2 sequences with an affine gap penalty. The obvious
method of using dynamic programming requires 3 matrices (or,
equivalently, 3 values in each cell of a single matrix). One matrix
will have values computed from the costs of subalignments ending with
a gap in one of the sequences. Another of the matrices will have
values computed from the cost of subalignments ending with a gap in
the other sequence. The remaining matrix will result from
subalignments that end without a gap in either sequence. Durbin, et
al.'s Biological Sequence Analysis (1998) refers to an algorithm that
uses only 2 matrices, one that results from subalignments ending in a
gap in either sequence, and one that results from subalignments ending
in 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