Online Lectures on Bioinformatics

Algorithms for SPoptimal multiple alignmentsAffine gapcostsThe problem of finding an optimal pairwise alignment using a linear affine gapcostfunction can be solved in time complexity by means of 'helpmatrices' (see above). As the number of the helpmatrices 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 . Comments are very welcome. luz@molgen.mpg.de 