Algorithms for SP-optimal multiple alignments

Affine gap-costs

The problem of finding an optimal pairwise alignment using a linear affine gap-cost-function can be solved in time complexity by means of 'help-matrices' (see above). As the number of the help-matrices grows exponentially with the number of sequences, the demand of space gets unacceptable in multiple alignments.

The so called quasi natural gap costs for mutiple alignments were introduced by Altschul in 1989 [Alt89]: Whether a blank in one row of the multiple alignment when aligned with a letter in another row is the opening of a new or the elongation of an existing gap is decided based on the entries in the previous column of the alignment, only. When penalizing gaps that way time complexity is of .