期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

翻转距离星树问题的计算复杂度和近似算法 被引量：3

Computational Complexity and an Approximation Algorithm for Star-Tree Phylogeny Problem with Reversal Distance
下载PDF
导出
摘要 讨论基于基因组翻转距离的星型进化树问题的算法和复杂性.首先证明星树问题是NP-难解的,再证明该问题不存在绝对近似求解算法,最后给出一个求解星树问题的常数近似算法,近似性能比为2. In this paper, the algorithms and the computational complexity of Star-Tree phylogeny problem are studied. The Star-Tree phylogeny problem is proved to be NP-complete first. Then it is proved that there is no absolute approximation algorithm for this problem. At last, a polynomial approximation algorithm of ratio 2 is presented to compute the Star-Tree phylogeny problem.
作者 朱大铭 马绍汉 雷鹏
机构地区 山东大学计算机科学技术学院
出处 《软件学报》 EI CSCD 北大核心 2002年第6期1117-1122,共6页 Journal of Software
基金 国家自然科学基金资助项目(60073042) 国家教育部青年教师基金资助项目(y66053 060602) 山东省中青年科学家奖励基金资助项目(01bs03)~~
关键词 翻转距离星树问题 计算复杂度 近似算法 数据结构 星型进化树 algorithm phylogeny genome NP-completeness approximation ratio
分类号 TP311.12 [自动化与计算机技术—计算机软件与理论]
  • 相关文献

参考文献8

  • 1Wang, Lu-sheng, Jiang Tao. Approximation algorithms for tree alignment with a given phylogeny. Algorithmica, 1996, 16(3):302～315.
  • 2Gusfield, D. Efficient algorithms for inferring evolutionary trees. Networks, 1991,21(1):19～28.
  • 3Kececioglu, J., Sankoff, D. Exact and approximation algorithms for the reversal distance between two permutations. Algorithmica, 1995,13(1):180～210.
  • 4Kececioglu, J., Sankoff, D. Efficient bounds for oriented chromosome inversion distance. In: Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science 807, 1994. 307～325.
  • 5Bafna, V., Pevzner, P.A. Sorting by reversals: genome rearrangements in plants organelles and evolutionary history of X chromosome. Molecular Biology and Evolution, 1995,12:239～246.
  • 6Kececioglu, J.D., Myers, E.W. Combinatorial algorithms for DNA sequence assembly. Algorithmica, 1995,13(1):7～15.
  • 7Hannenhalli, S., Pevzner, P.A. Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals). In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC'95). ACM press, 1995. 178～189.
  • 8Ma, Shao-han, Designation and Analysis of Algorithms. Ji'nan: Shandong University Press, 1992 (in Chinese).

同被引文献6

  • 1栾峻峰 朱大铭 马绍汉.目标序列符号顺序固定的翻转距离星树问题[J].计算机科学,2001,28(9):177-181.
  • 2D Sankoff, G Leduc, N Antoine et al. Gen order comparisons for phylogenetic inference: Evolution of the mitochondrial. Proc of the National Academy of Sciences 1992, 1992, 89:6575--6579.
  • 3J Kececioglu, D Sankoff. Exact and approximation algorithms for the reversal distance between two permutations. Algorithmica,1995, 13(1/2): 180--210.
  • 4J Kececioglu, D Sankoff. Efficient hounds for oriented chromosome inversion distance. In: Proc of 5th Annual Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science-807. Berlin: Springer-Verlag, 1994. 307--325.
  • 5V Bafna, P Pevzner. Sorting by reversals: Genome rearrangements in plants organelles and evolutionary history of X chromosome Molecular Biology and Evolution, 1995, 12 ( 2 ):239 ~ 246.
  • 6S Hannenhalli, P A Pevzner. Transforming cabbage into turnip--Polynomial algorithm for sorting signed permutations by reversals.In: Proc of STOC'95, 1995. 178--179.

引证文献3

软件学报
2002年 第6期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部