title: A simplified proof of the NP- and MAX SNP-hardness of multiple sequence tree alignment.
abstract: 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.
authors.affiliation: Computer Science Department, University of Victoria, British Columbia, Canada. harold@csr.uvic.ca
authors.forename: H T
authors.initials: HT
authors.lastname: Wareham
mesh_terms: D000465:Algorithms; D019143:Evolution, Molecular; D008433:Mathematics; D008957:Models, Genetic; D010802:Phylogeny; D016415:Sequence Alignment / Q000379:methods* / Q000706:statistics & numerical data