摘要翻译：
单倍型推断是生物信息学中一个具有挑战性的问题，它是根据二倍体生物的基因型来推断其基本遗传结构。这些信息使研究人员能够对与疾病有关的遗传变异和个体对治疗药物的反应进行关联研究。解决该问题的一个值得注意的方法是将其编码为组合问题（在某些假设下，如纯简约准则下），并使用现成的组合优化技术来解决它。目前用于单倍型推断的主要方法有简单的贪婪启发式方法或精确方法（整数线性规划、半定规划、SAT编码），这些方法仅适用于中等规模的实例。我们相信，元启发式和混合方法可以提供更好的可伸缩性。此外，元启发式可以很容易地与特定问题启发式相结合，也可以与基于树的搜索技术相结合，从而为混合系统提供了一个很有前途的框架，在该框架中可以很好地兼顾效率和效率。本文对该方法进行了可行性研究，并讨论了一些相关的设计问题，如结合构造性启发式、基于局部搜索的改进策略和学习机制的近似求解器的建模和设计。除了与单倍型推理问题本身的相关性之外，这个初步分析也是一个有趣的案例研究，因为该问题的表述在建模和混合元启发式求解器设计方面提出了一些挑战，可以推广到其他问题。
---
英文标题：
《A preliminary analysis on metaheuristics methods applied to the
  Haplotype Inference Problem》
---
作者：
Luca Di Gaspero, Andrea Roli
---
最新提交年份：
2007
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Computational Engineering, Finance, and Science        计算工程、金融和科学
分类描述：Covers applications of computer science to the mathematical modeling of complex systems in the fields of science, engineering, and finance. Papers here are interdisciplinary and applications-oriented, focusing on techniques and tools that enable challenging computational simulations to be performed, for which the use of supercomputers or distributed computing platforms is often required. Includes material in ACM Subject Classes J.2, J.3, and J.4 (economics).
涵盖了计算机科学在科学、工程和金融领域复杂系统的数学建模中的应用。这里的论文是跨学科和面向应用的，集中在技术和工具，使挑战性的计算模拟能够执行，其中往往需要使用超级计算机或分布式计算平台。包括ACM学科课程J.2、J.3和J.4（经济学）中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Discrete Mathematics        离散数学
分类描述：Covers combinatorics, graph theory, applications of probability. Roughly includes material in ACM Subject Classes G.2 and G.3.
涵盖组合学，图论，概率论的应用。大致包括ACM学科课程G.2和G.3中的材料。
--
一级分类：Quantitative Biology        数量生物学
二级分类：Quantitative Methods        定量方法
分类描述：All experimental, numerical, statistical and mathematical contributions of value to biology
对生物学价值的所有实验、数值、统计和数学贡献
--

---
英文摘要：
  Haplotype Inference is a challenging problem in bioinformatics that consists in inferring the basic genetic constitution of diploid organisms on the basis of their genotype. This information allows researchers to perform association studies for the genetic variants involved in diseases and the individual responses to therapeutic agents.   A notable approach to the problem is to encode it as a combinatorial problem (under certain hypotheses, such as the pure parsimony criterion) and to solve it using off-the-shelf combinatorial optimization techniques. The main methods applied to Haplotype Inference are either simple greedy heuristic or exact methods (Integer Linear Programming, Semidefinite Programming, SAT encoding) that, at present, are adequate only for moderate size instances.   We believe that metaheuristic and hybrid approaches could provide a better scalability. Moreover, metaheuristics can be very easily combined with problem specific heuristics and they can also be integrated with tree-based search techniques, thus providing a promising framework for hybrid systems in which a good trade-off between effectiveness and efficiency can be reached.   In this paper we illustrate a feasibility study of the approach and discuss some relevant design issues, such as modeling and design of approximate solvers that combine constructive heuristics, local search-based improvement strategies and learning mechanisms. Besides the relevance of the Haplotype Inference problem itself, this preliminary analysis is also an interesting case study because the formulation of the problem poses some challenges in modeling and hybrid metaheuristic solver design that can be generalized to other problems.
---
PDF链接：
https://arxiv.org/pdf/0708.0505