Algorithms for SP-optimal multiple alignments

Definition

Regarding more than two sequences, the generalization of a pairwise alignment leads to a multiple alignment which may be represented by a matrix:

        - A C C G T C

        T A G - G T A

        C A C C C T -
              :
              :

The number of rows in the matrix corresponds to the number of sequences, the number of columns is the resulting length of the alignment.

Formally this means:

Given the sequences s⁽¹⁾, s⁽²⁾,...,s⁽ⁿ⁾ over an alphabet . Then the matrix

1.

2.

Omitting the blanks, the i th column reproduces the sequence s⁽ⁱ⁾.

3.

There is no row consisting of blanks only.