previous section previous page next page next section
CMB

Online Lectures on Bioinformatics

navigation


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 $ \mathcal{O}(L^n2^n) $ and space in $ \mathcal{O}(L^n) $.

$\underline{\smash{\hbox{Theorem:}}}$

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].




Comments are very welcome.
luz@molgen.mpg.de