10.3321/j.issn:1671-8836.2003.05.009
基因组重排问题的一个近似算法
分子生物学中基因无方向的反向基因组重排问题在数学上已被证明是一个NP困难问题.基于断点图的概念,给出一个时间复杂性为O(max{b3(π),nb(π)}),空间复杂性为O(n)的求其近似最优解的算法.其中n为基因组中基因个数,π=(π1,π2,...,πn)表示n个基因的一种排列,b(π)表示排列π中的断点数.数据实验的结果表明,该近似算法可以求得较好的结果.
基因组重排、反向排序、断点图、近似算法
49
O242;Q332(计算数学)
国家自然科学基金30170214;武汉大学校科研和教改项目
2004-02-20(万方平台首次上网日期,不代表论文的发表时间)
共5页
580-584