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

栾峻峰; 朱大铭; 马绍汉

引用本文:	栾峻峰,朱大铭,马绍汉.目标序列部分确定的翻转距离星树问题.软件学报,2003,14(2):183-189

【打印本页】【下载PDF全文】【查看/发表评论】【EndNote】【RefMan】【BibTex】

←前一篇|后一篇→

过刊浏览高级检索

本文已被：浏览 4293次下载 5585次	码上扫一扫！
分享到：微信更多字体:加大+\|默认\|缩小-
目标序列部分确定的翻转距离星树问题
栾峻峰¹, 朱大铭¹, 马绍汉¹
山东大学,计算机科学与技术学院,山东,济南,250100

摘要:

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

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

DOI：

分类号:

基金项目:

A Problem of Reversal Distance on Star-Tree with Object Partially Fixed

LUAN Jun-Feng,ZHU Da-Ming,MA Shao-Han

Abstract:

A problem of reversal distance on star-tree is discussed. The problem of 3SAT is induced to the problem of the reversal distance on star-tree with object partially fixed. The fact desribed below is proved, it is still NP-hard to solve the problem of reversal distance on star-tree in which only need to decide the signs of the other symbols to minimizing the sum of distance between object and the given sequences. A polynomial approximation algorithm for the problem is given.

Key words: algorithm computational complexity evolutionary tree genome reversal distance