This paper studies the computational complexity of two 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. Multiple sequence alignment is a key problem in computational biology, used for finding conserved regions in biological sequences and inferring evolutionary history. The SP-score is a popular scoring method for multiple alignment, and the paper shows that the problem of finding an optimal alignment under SP-score is NP-complete. For tree alignment, it is shown that the problem is MAX SNP-hard, implying that there is no polynomial-time approximation scheme (PTAS) for the problem unless P=NP. The paper also considers the complexity of tree alignment with a given phylogeny, showing that it is NP-complete even when the phylogeny is a binary tree, and MAX SNP-hard when the phylogeny is a star. The results highlight the computational difficulty of these problems and the limitations of approximation algorithms for them.This paper studies the computational complexity of two 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. Multiple sequence alignment is a key problem in computational biology, used for finding conserved regions in biological sequences and inferring evolutionary history. The SP-score is a popular scoring method for multiple alignment, and the paper shows that the problem of finding an optimal alignment under SP-score is NP-complete. For tree alignment, it is shown that the problem is MAX SNP-hard, implying that there is no polynomial-time approximation scheme (PTAS) for the problem unless P=NP. The paper also considers the complexity of tree alignment with a given phylogeny, showing that it is NP-complete even when the phylogeny is a binary tree, and MAX SNP-hard when the phylogeny is a star. The results highlight the computational difficulty of these problems and the limitations of approximation algorithms for them.