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