| 摘要: |
| 讨论基于基因组翻转距离的星型进化树问题的算法和复杂性.首先证明星树问题是NP-难解的,再证明该问题不存在绝对近似求解算法,最后给出一个求解星树问题的常数近似算法,近似性能比为2. |
| 关键词: 算法 进化树 基因组 NP-完全性 近似性能比 |
| DOI： |
| 分类号: |
| 基金项目:国家自然科学基金资助项目(60073042);国家教育部青年教师基金资助项目(y66053;060602);山东省中青年科学家奖励基金资助项目(01bs03) |
|
| Computational Complexity and an Approximation Algorithm for Star-Tree Phylogeny Problem with Reversal Distance |
|
ZHU Da-ming,MA Shao-han,LEI Peng
|
| Abstract: |
| 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. |
| Key words: algorithm phylogeny genome NP-completeness approximation ratio |
