Wareham H T
Computer Science Department, University of Victoria, British Columbia, Canada.
J Comput Biol. 1995 Winter;2(4):509-14. doi: 10.1089/cmb.1995.2.509.
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.
我们给出了一个简单的证明，表明分子生物学中的多序列树比对问题既是NP完全问题，也是MAX SNP困难问题。我们对MAX SNP困难性的证明比Wang和Jiang之前给出的证明更简单。这些结果表明，多序列树比对问题不太可能有能产生最优解或代价可任意接近最优解的近似解的多项式时间算法。
