# 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)n vertices and about Ln(2n-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].