On the Complexity of Multiple Sequence Alignment
Lusheng Wang, Tao Jiang · Journal of Computational Biology · 1994
We study the computational complexity of two popular problems in multiple sequence alignment: multiple alignment with SP-score and multiple tree alignment. It is shown that the first problem is NP-complete and the second is MAX SNP-hard. The complexity of tree alignment with a given phylogeny is also considered.