目标序列符号顺序固定的翻转距离星树问题

摘要：

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

关键词： 进化树 基因组 目标序列符号 翻转距离星树

作者: 栾峻峰 朱大铭 马绍汉

作者单位: 山东大学计算机科学与技术学院(济南)

会议类型: 国内会议

会议名称: 2001年全国理论计算机科学学术会议

会议地点: 福州

会议语种:中文

页码: 177-181

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