2009 | OriginalPaper | Buchkapitel
Flexible Stochastic Local Search for Haplotype Inference
verfasst von : Luca Di Gaspero, Andrea Roli
Erschienen in: Learning and Intelligent Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
of the
entropy minimization
criteria) and to solve it using off-the-shelf combinatorial optimization techniques.
In this paper, we present and discuss an approach based on local search metaheuristics. A flexible solver is designed to tackle the Haplotype Inference under the criterion of choice, that could be defined by the user. We test our approach by solving instances from common Haplotype Inference benchmarks both under the hypothesis of pure parsimony and entropy minimization. Results show that the approach achieves a good trade-off between solution quality and execution time and compares favorably with the state of the art.