| 基因组重排问题的一个近似算法 |
| |
| 引用本文： | 陶玉敏,莫忠息,刘扬,任清华,李素贞.基因组重排问题的一个近似算法[J].武汉大学学报(理学版),2003,49(5):580-584. |
| |
| 作者姓名： | 陶玉敏 莫忠息 刘扬 任清华 李素贞 |
| |
| 作者单位： | 武汉大学,数学与统计学院,湖北,武汉,430072 |
| |
| 基金项目： | 国家自然科学基金(30170214);武汉大学自强基金资助 |
| |
| 摘 要： | 分子生物学中基因无方向的反向基因组重排问题在数学上已被证明是一个NP困难问题．基于断点图的概念，给出一个时间复杂性为O(max{b^(π)，nb(π)})，空间复杂性为0(n)的求其近似最优解的算法．其中n为基因组中基因个数，π=(π1,π2，…，πn)表示n个基因的一种排列，b(π)表示排列π中的断点数．数据实验的结果表明，该近似算法可以求得较好的结果．
|
| 关 键 词： | 分子生物学 反向基因组重排 反向排序 断点图 近似算法 最优解 分枝定界算法 |
| 文章编号： | 1671-8836(2003)05-0580-05 |
| 修稿时间： | 2003年1月16日 |
An Approximation Algorithm for Genome Rearrangement Problem |
| |
| TAO Yu-min,MO Zhong-xi,LIU Yang,REN Qing-hua,LI Su-zhen.An Approximation Algorithm for Genome Rearrangement Problem[J].JOurnal of Wuhan University:Natural Science Edition,2003,49(5):580-584. |
| |
| Authors: | TAO Yu-min MO Zhong-xi LIU Yang REN Qing-hua LI Su-zhen |
| |
| Abstract: | |
| |
| Keywords: | genome rearrangement sorting by reversals breakpoint graph approximation algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
