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.

Di Gaspero, L., Roli, A. (2009). Flexible stochastic local search for haplotype inference [10.1007/978-3-642-11169-3_6].

Flexible stochastic local search for haplotype inference

ROLI, ANDREA
2009

Abstract

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.
2009
74
88
Di Gaspero, L., Roli, A. (2009). Flexible stochastic local search for haplotype inference [10.1007/978-3-642-11169-3_6].
Di Gaspero, L.; Roli, Andrea
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/85747
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact