• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE/ACM transactions on computational biology and bioinformatics >Consensus Genetic Maps as Median Orders from Inconsistent Sources
【24h】

Consensus Genetic Maps as Median Orders from Inconsistent Sources

机译：来自不一致来源的中位顺序一致的遗传图谱

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

摘要

A genetic map is an ordering of geneticmarkers calculated from a population of known lineage.While traditionally a map has been generated from a singlepopulation for each species, recently researchers have createdmaps from multiple populations. In the face of thesenew data, we address the need to find a consensus map — a map that combines the information from multiple partialand possibly inconsistent input maps. We model eachinput map as a partial order and formulate the consensusproblem as finding a median partial order. Finding themedian of multiple total orders (preferences or rankings)is a well studied problem in social choice. We choose tofind the median using the weighted symmetric differencedistance, a more general version of both the symmetricdifference distance and the Kemeny distance. Finding amedian order using this distance is NP-hard. We showthat for our chosen weight assignment, a median ordersatisfies the positive responsiveness, extended Condorcet,and unanimity criteria. Our solution involves finding themaximum acyclic subgraph of a weighted directed graph.We present a method that dynamically switches betweenan exact branch and bound algorithm and a heuristicalgorithm, and show that for real data from closely relatedorganisms, an exact median can often be found.We presentexperimental results using seven populations of the cropplant Zea mays.
机译：遗传图谱是从已知谱系种群中计算出的遗传标记的顺序。传统上，每个物种的单一种群都生成了一个图谱，但最近，研究人员已经从多个种群中创建了图谱。面对这些新数据，我们满足了寻找共识地图的需求-一张地图将来自多个局部且可能不一致的输入地图的信息组合在一起。我们将每个输入映射建模为偏序，并将共识问题公式化为找到中位数偏序。寻找多个总订单（偏好或排名）的主题是社会选择中一个经过充分研究的问题。我们选择使用加权对称差异距离（对称差异距离和Kemeny距离的更通用版本）来查找中位数。使用该距离寻找中间阶是NP难的。我们表明，对于我们选择的体重分配，中位数命令可以满足积极的响应能力，扩展的Condorcet和一致同意标准。我们的解决方案涉及找到加权有向图的最大无环子图。我们提出了一种在精确的分支定界算法和启发式算法之间动态切换的方法，并表明对于来自密切相关的有机体的真实数据，经常可以找到精确的中位数。使用七个玉米作物种群的结果。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号