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].
Comments are very welcome.