目标序列部分确定的翻转距离星树问题

摘要：

讨论翻转距离星树问题,将3SAT问题归约到目标序列部分固定的翻转距离星树问题,证明实例中当有向符号序列个数为3时,若目标序列符号顺序固定,且有部分符号方向给定,则只确定其余符号方向以使得目标序列与已知3条给定序列翻转距离之和最小所对应的翻转距离星树问题也是NP-难解问题.同时,还给出了该问题的多项式时间近似算法.

关键词：算法、计算复杂性、进化树、基因组、翻转距离

所属期刊栏目：14

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金60073042

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：183-189