Abstract
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.
Key words:
multiple sequence tree alignment, computational complexity, approximability, NP-complete, MAX SNP-hard
Get full access to this article
View all access options for this article.