• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Algebraic Biology(AB 2007); 20070702-04; Castle of Hagenberg(AT) >Efficient Haplotype Inference with Pseudo-boolean Optimization
【24h】

Efficient Haplotype Inference with Pseudo-boolean Optimization

机译：伪布尔优化的有效单倍型推断

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

摘要

Haplotype inference from genotype data is a key computational problem in bioinformatics, since retrieving directly haplotype information from DNA samples is not feasible using existing technology. One of the methods for solving this problem uses the pure parsimony criterion, an approach known as Haplotype Inference by Pure Parsimony (HIPP). Initial work in this area was based on a number of different Integer Linear Programming (ILP) models and branch and bound algorithms. Recent work has shown that the utilization of a Boolean Satisfiability (SAT) formulation and state of the art SAT solvers represents the most efficient approach for solving the HIPP problem. Motivated by the promising results obtained using SAT techniques, this paper investigates the utilization of modern Pseudo-Boolean Optimization (PBO) algorithms for solving the HIPP problem. The paper starts by applying PBO to existing ILP models. The results are promising, and motivate the development of a new PBO model (RPoly) for the HIPP problem, which has a compact representation and eliminates key symmetries. Experimental results indicate that RPoly outperforms the SAT-based approach on most problem instances, being, in general, significantly more efficient.
机译：从基因型数据推断单倍型是生物信息学中的关键计算问题，因为使用现有技术直接从DNA样本中检索单倍型信息是不可行的。解决此问题的方法之一是使用纯简约准则，即纯简约（HIPP）称为单倍型推断的方法。该领域的最初工作基于许多不同的整数线性规划（ILP）模型以及分支定界算法。最近的工作表明，使用布尔可满足性（SAT）公式和最新的SAT求解器代表了解决HIPP问题的最有效方法。基于使用SAT技术获得的有希望的结果，本文研究了利用现代伪布尔优化（PBO）算法解决HIPP问题的方法。本文首先将PBO应用于现有的ILP模型。结果令人鼓舞，并刺激了针对HIPP问题的新PBO模型（RPoly）的开发，该模型具有紧凑的表示形式并且消除了关键的对称性。实验结果表明，在大多数问题实例中，RPoly均优于基于SAT的方法，通常效率更高。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号