Wang L, Jiang T
Department of Electrical and Computer Engineering, McMaster University, Hamilton, Ontario, Canada.
J Comput Biol. 1994 Winter;1(4):337-48. doi: 10.1089/cmb.1994.1.337.
We study the computational complexity of two popular problems in multiple sequence alignment: multiple alignment with SP-score and multiple tree alignment. It is shown that the first problem is NP-complete and the second is MAX SNP-hard. The complexity of tree alignment with a given phylogeny is also considered.
带SP分数的多重比对和多重树形比对。结果表明，第一个问题是NP完全问题，第二个问题是MAX SNP难问题。我们还考虑了给定系统发育情况下树形比对的复杂性。
