A simplified proof of the NP- and MAX SNP-hardness of multiple sequence tree alignment.
We give a simple proof which shows that the multiple sequence tree alignment problem from molecular biology is both NP-complete and MAX SNP-hard. Our proof of MAX SNP-hardness is simpler than that given previously by Wang and Jiang. These results suggest that it is unlikely that the multiple sequence tree alignment problem has polynomial-time algorithms that produce either optimal solutions or approximate solutions whose cost may be arbitrarily close to optimal.
Wareham
H T
HT
Computer Science Department, University of Victoria, British Columbia, Canada. harold@csr.uvic.ca
D000465:Algorithms; D019143:Evolution, Molecular; D008433:Mathematics; D008957:Models, Genetic; D010802:Phylogeny; D016415:Sequence Alignment / Q000379:methods* / Q000706:statistics & numerical data