Computational complexity of multiple sequence alignment
The best scoring alignment should be the most likely
hypothesis about the evolutionarily correct alignment.
Finding the best scoring alignment for a given scoring
scheme is called the multiple sequence alignment problem.
The size of an instance is given by the number k of
sequences to be aligned and the length n of the longest
sequence. For any fixed k the problem can be solved
in time O(nk) by a variant of the Smith-Waterman
algorithm. Can we do any better?