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.

Flexible stochastic local search for haplotype inference

DI GASPERO, Luca;
2009-01-01

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
9783642111686
File in questo prodotto:
File Dimensione Formato  
lion3.pdf

non disponibili

Tipologia: Documento in Post-print
Licenza: Non pubblico
Dimensione 446.38 kB
Formato Adobe PDF
446.38 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/11390/861992
 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