• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>AI communications >Inferring phylogenetic trees using pseudo-Boolean optimization
【24h】

Inferring phylogenetic trees using pseudo-Boolean optimization

机译：使用伪布尔优化推断系统发育树

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

摘要

Phylogenetic inference concerns the construction of the most probable tree of evolution, taking into account the knowledge about organisms we have at our disposal. There are various inference methods for building a phylogenetic tree, each with its set of assumptions about what can happen in Nature. Assumptions limit the expressiveness of the methods, but are necessary for making them viable to use. More recently, computational methods are being used to validate results obtained from manual methods. Computational methods allow to address problems that require the analysis of larger sets of data in order to construct more complete phytogenies. In this paper we propose the use of Pseudo-Boolean Optimization (PBO), a well known extension of Propositional Satisfiability (SAT), in order to solve the Maximum Compatibility (MC) problem. Assuming that each organism is associated with a set of characteristics, the goal in the MC problem is to find a phylogenetic tree such that the maximum number of characteristics are compatible. Our contribution is a set of new PBO formulations that improve on the performance of the state of the art tool. Comparative results, using real and generated instances, show that the proposed implementations allow the resolution of problem instances with twice the size of the state of the art implementation.
机译：系统发生推理涉及最可能的进化树的构建，同时考虑到我们掌握的生物知识。建立系统发育树的推理方法多种多样，每种方法都有其关于自然界中可能发生的假设的集合。假设限制了方法的表达性，但使它们可行时是必需的。最近，计算方法被用于验证从手动方法获得的结果。计算方法可以解决那些需要分析较大数据集以构建更完整的植物遗传学的问题。在本文中，我们提出使用伪布尔优化（PBO）（一种命题可满足性（SAT）的众所周知的扩展）来解决最大兼容性（MC）问题。假设每个生物都具有一组特征，则MC问题的目标是找到一个系统进化树，以使最大数目的特征兼容。我们的贡献是改进了最新工具性能的一组新的PBO公式。使用实际实例和生成的实例进行的比较结果表明，所提出的实施方案可以用两倍于最新实施方案的大小来解决问题实例。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号