Related Experiment Videos
A simplified proof of the NP- and MAX SNP-hardness of multiple sequence tree alignment
1Computer Science Department, University of Victoria, British Columbia, Canada. harold@csr.uvic.ca
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.