Online Lectures on Bioinformatics

Algorithms for SPoptimal multiple alignmentsThe exact solutionThe 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 twodimensional weighted editgraph (see previous sections). Analogously, the problem of finding an optimal alignmet between nsequences is eqivalent to finding the shortest path in a ndimensional weighted editgraph with (L+1)^{n} vertices and about L^{n}(2^{n}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 NPhard with regard to the number of sequences [WJ94]. Polynomial approximations were given by [Gus93] and [BLP94].
Comments are very welcome. luz@molgen.mpg.de 