Computational complexity of multiple sequence alignment
With respect to the number of sequences k, the multiple
sequence alignment problem is NP-hard. This was shown
around 1993 by Wang and Jiang. Unfortunately, their
proof uses a biologically totally irrelevant scoring scheme.
It was not clear until recently whether the problem might
become tractable for scoring schemes that are actually
used by biologists, or if we limit the number of gaps that
can be inserted. It was also unknown whether there might
be always a PTAS (polynomial time approximation