Algorithms for SP-optimal multiple alignments

Motivation

• a multiple alignment gives a stronger signal for sequence similarities than a pairwise alignment, i.e. in

  -

  sequence assembly

  -

  molecular modelling

  -

  database search

  -

  primer design

• ambiguities in the alignment may be resolved by a multiple alignment
• looking into the relationship between the sequences leads to reconstructing a phylogenetic tree (see next section)