The paper "On the Complexity of Multiple Sequence Alignment" by Lusheng Wang and Tao Jiang from McMaster University studies the computational complexity of two key problems in multiple sequence alignment: multiple alignment with SP-score and multiple tree alignment. The authors show that multiple alignment with SP-score is NP-complete, while multiple tree alignment is MAX SNP-hard. They also investigate the complexity of tree alignment when a given phylogenetic structure is provided, proving that it is NP-complete for binary trees and MAX SNP-hard for star trees. The paper provides detailed reductions and proofs to support these findings, highlighting the challenges in efficiently solving these problems.The paper "On the Complexity of Multiple Sequence Alignment" by Lusheng Wang and Tao Jiang from McMaster University studies the computational complexity of two key problems in multiple sequence alignment: multiple alignment with SP-score and multiple tree alignment. The authors show that multiple alignment with SP-score is NP-complete, while multiple tree alignment is MAX SNP-hard. They also investigate the complexity of tree alignment when a given phylogenetic structure is provided, proving that it is NP-complete for binary trees and MAX SNP-hard for star trees. The paper provides detailed reductions and proofs to support these findings, highlighting the challenges in efficiently solving these problems.