title: On the complexity of multiple sequence alignment.
abstract: 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.
authors.affiliation: Department of Electrical and Computer Engineering, McMaster University, Hamilton, Ontario, Canada.
authors.forename: L
authors.initials: L
authors.lastname: Wang
authors.forename: T
authors.initials: T
authors.lastname: Jiang
mesh_terms: D000465:Algorithms; D008962:Models, Theoretical; D010802:Phylogeny; D016415:Sequence Alignment / Q000379:methods*