[BiO BB] Optimal Sequence Alignment - Affine Gap Penalty
alexdow at gmail.com
Tue Sep 7 18:46:55 EDT 2004
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.
More information about the BBB