论多序列比对的复杂性。
On the complexity of multiple sequence alignment.
作者信息
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.
PMID:8790475
Abstract
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难问题。我们还考虑了给定系统发育情况下树形比对的复杂性。
Zotero 插件