...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Constraints >Boosting Haplotype Inference with Local Search
【24h】

Boosting Haplotype Inference with Local Search

机译：通过本地搜索增强单倍型推断

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

摘要

A very challenging problem in the genetics domain is to infer haplotypes from genotypes. This process is expected to identify genes affecting health, disease and response to drugs. One of the approaches to haplotype inference aims to minimise the number of different haplotypes used, and is known as haplotype inference by pure parsimony (HIPP). The HIPP problem is computationally difficult, being NP-hard. Recently, a SAT-based method (SHIPs) has been proposed to solve the HIPP problem. This method iteratively considers an increasing number of haplotypes, starting from an initial lower bound. Hence, one important aspect of SHIPs is the lower bounding procedure, which reduces the number of iterations of the basic algorithm, and also indirectly simplifies the resulting SAT model. This paper describes the use of local search to improve existing lower bounding procedures. The new lower bounding procedure is guaranteed to be as tight as the existing procedures. In practice the new procedure is in most cases considerably tighter, allowing significant improvement of performance on challenging problem instances.
机译：遗传学领域的一个非常具有挑战性的问题是从基因型推断单倍型。预期该过程将鉴定影响健康，疾病和对药物反应的基因。一种用于单倍型推断的方法旨在最小化所使用的不同单倍型的数量，并且被纯简约（HIPP）称为单倍型推断。 HIPP问题在计算上很困难，是NP难题。近来，已经提出了基于SAT的方法（SHIP）来解决HIPP问题。从初始下限开始，此方法反复考虑增加的单倍型。因此，SHIP的一个重要方面是下限过程，它减少了基本算法的迭代次数，还间接简化了所得的SAT模型。本文介绍了使用局部搜索来改善现有的下限过程。保证新的下限过程与现有过程一样严格。在实践中，新程序在大多数情况下要严格得多，从而可以显着提高具有挑战性的问题实例的性能。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号