• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Bioinformatics research and applications >A Polynomial Algebra Method for Computing Exemplar Breakpoint Distance
【24h】

A Polynomial Algebra Method for Computing Exemplar Breakpoint Distance

机译：计算示例断点距离的多项式代数方法

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The exemplar breakpoint distance problem is NP-hard. Assume two genomes have at most n genes from m gene families. We develop an O(2~mn~(O(1))) time algorithm to compute the exemplar breakpoint distance if one of them has no repetition. We develop an O(2~mm!n~(O(1))) time algorithm to compute the exemplar breakpoint distance between two arbitrary genomes. If one of the given genomes has at most d repetitions for each gene, the computation time of the second algorithm is only O((2d)~mn~(O(1))). Our algorithms are based on a polynomial algebra approach which uses a multilinear monomial to represent a solution for the exemplar breakpoint distance problem.
机译：示例性的断点距离问题是NP-难的。假设两个基因组最多具有m个基因家族中的n个基因。我们开发了O（2〜mn〜（O（1）））时间算法来计算示例断点距离（如果其中一个没有重复）。我们开发了O（2〜mm！n〜（O（1）））时间算法来计算两个任意基因组之间的示例断点距离。如果给定的基因组中每个基因最多具有d个重复，则第二种算法的计算时间仅为O（（2d）〜mn〜（O（1）））。我们的算法基于多项式代数方法，该方法使用多线性单项式来表示示例断点距离问题的解决方案。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号