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.