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 piece of 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) and to solve it using off-the-shelf combinatorial optimization techniques. In this paper, we present and discuss an approach based on hybridization of two metaheuristics, one being a population based learning algorithm and the other a local search. We test our approach by solving instances from common Haplotype Inference benchmarks. Results show that this approach achieves an improvement on solution quality with respect to the application of a single "pure" algorithm.
Towards a highly scalable hybrid metaheuristic for haplotype inference under parsimony
DI GASPERO, Luca;
2008-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 piece of 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) and to solve it using off-the-shelf combinatorial optimization techniques. In this paper, we present and discuss an approach based on hybridization of two metaheuristics, one being a population based learning algorithm and the other a local search. We test our approach by solving instances from common Haplotype Inference benchmarks. Results show that this approach achieves an improvement on solution quality with respect to the application of a single "pure" algorithm.File | Dimensione | Formato | |
---|---|---|---|
his2008.pdf
non disponibili
Tipologia:
Documento in Pre-print
Licenza:
Non pubblico
Dimensione
349.98 kB
Formato
Adobe PDF
|
349.98 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.