A Simplified Proof of the NP- and MAX SNP-Hardness of Multiple Sequence Tree Alignment
H. Todd Wareham · Journal of Computational Biology · 1995
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. Key words: multiple sequence tree alignment, computational complexity, approximability, NP-complete, MAX SNP-hard