Computational complexity of multiple sequence alignment
Theorem 1: (Just) For every scoring scheme used by
biologists, the multiple sequence alignment problem is
NP-hard. This remains true even if the number and size
of gaps that can be inserted into each sequence is
restricted in the most severe way possible.
Theorem 2: (Just) There exists a scoring scheme for
which the multiple alignment problem has no PTAS, even
if the number and size of gaps that can be inserted into
each sequence is most severely restricted.