Algorithms for SP-optimal multiple alignments

The exact solution

The problem of finding an optimal alignment between two sequences was solved by the dynamic programming algorithm, which resulted in finding the shortest path in a two-dimensional weighted edit-graph (see previous sections).

Analogously, the problem of finding an optimal alignmet between nsequences is eqivalent to finding the shortest path in a n-dimensional weighted edit-graph with (L+1)ⁿ vertices and about Lⁿ(2ⁿ-1) edges (with L being the sequence length).

The correspomding algorithm, which was introduced by Waterman, Smith and Beyer in 1976 [WSB76], takes time in and space in .

It was shown that finding an optimal multiple alignment with the SP measure is NP-hard with regard to the number of sequences [WJ94].

Polynomial approximations were given by [Gus93] and [BLP94].