• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Workshop on Algorithms in Bioinformatics >Genome Rearrangements on Both Gene Order and Intergenic Regions
【24h】

Genome Rearrangements on Both Gene Order and Intergenic Regions

机译：基因阶和基因区的基因组重排

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

All combinatorial works on genome rearrangements have so far ignored the influence of intergene sizes, i.e. the number of nucleotides between consecutive genes, although it was recently shown decisive for the accuracy of the inference methods [3,4]. In this line, we define a new genome rearrangement model called wDCJ, a generalization of the well-known Double Cut and Join (or DCJ) model that allows for modifying both the gene order and the intergene size distribution of a genome. We first provide a generic formula for the wDCJ distance between two genomes, and show that computing this distance is strongly NP-complete. We then propose an approximation algorithm of ratio 3/2, and two exact ones: a fixed parameterized (FPT) algorithm and an ILP formulation. We finally provide theoretical and empirical bounds on the expected growth of the parameter at the center of our FPT and ILP algorithms, assuming a probabilistic model of evolution under wDCJ, which shows that both these algorithms should run reasonably fast in practice.
机译：迄今为止，所有组合工程都忽略了内改尺寸的影响，即连续基因之间的核苷酸的数量，尽管最近显示了推理方法的准确性的决定性[3,4]。在这一行中，我们定义了一种名为WDCJ的新的基因组重新安排模型，众所周知的双切割和连接（或DCJ）模型的概括，其允许改变基因组的基因阶数和基因组的介导尺寸分布。我们首先为两个基因组之间提供WDCJ距离的通用公式，并显示计算该距离的强烈NP完整。然后，我们提出了一种比率3/2的近似算法和两个精确的算法：固定参数化（FPT）算法和ILP制剂。假设WDCJ下的演化概率模型，我们最终提供了对FPT和ILP算法的预期增长的理论和经验界限，这表明这两种算法应该在实践中合理地运行。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号