1 Search Results for "Labbé, Martine"

A Column Generation Approach for Pure Parsimony Haplotyping

Authors: Veronica Dal Sasso, Luigi De Giovanni, and Martine Labbé

Published in: OASIcs, Volume 50, 5th Student Conference on Operational Research (SCOR 2016)

The knowledge of nucleotides chains that compose the double DNA chain of an individual has a relevant role in detecting diseases and studying populations. However, determining experimentally the single nucleotides chains that, paired, form a certain portion of the DNA is expensive and time-consuming. Mathematical programming approaches have been proposed instead, e.g. formulating the Haplotype Inference by Pure Parsimony problem (HIPP). Abstractly, we are given a set of genotypes (strings over a ternary alphabet {0,1,2}) and we want to determine the smallest set of haplotypes (binary strings over the set {0,1}) so that each genotype can be "generated" by some pair of haplotypes, meaning that they are compatible with the genotype and can fully explain its structure. A polynomial-sized Integer Programming model was proposed by Catanzaro, Godi and Labbé (2010), which is highly efficient but hardly scalable to instances with a large number of genotypes. In order to deal with larger instances, we propose a new model involving an exponential number of variables to be solved via column generation, where variables are dynamically introduced into the model by iteratively solving a pricing problem. We compared different ways of solving the pricing problem, based on integer programming, smart enumeration and local search heuristic. The efficiency of the approach is improved by stabilization and by a heuristic to provide a good initial solution. Results show that, with respect to the linear relaxations of both the polynomial and exponential-size models, our approach yields a tighter formulation and outperforms in both efficiency and effectiveness the previous model for instances with a large number of genotypes.

Cite as

Veronica Dal Sasso, Luigi De Giovanni, and Martine Labbé. A Column Generation Approach for Pure Parsimony Haplotyping. In 5th Student Conference on Operational Research (SCOR 2016). Open Access Series in Informatics (OASIcs), Volume 50, pp. 5:1-5:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

  author =	{Dal Sasso, Veronica and De Giovanni, Luigi and Labb\'{e}, Martine},
  title =	{{A Column Generation Approach for Pure Parsimony Haplotyping}},
  booktitle =	{5th Student Conference on Operational Research (SCOR 2016)},
  pages =	{5:1--5:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-004-0},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{50},
  editor =	{Hardy, Bradley and Qazi, Abroon and Ravizza, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SCOR.2016.5},
  URN =		{urn:nbn:de:0030-drops-65174},
  doi =		{10.4230/OASIcs.SCOR.2016.5},
  annote =	{Keywords: computational biology, haplotyping, column generation, integer programming, combinatorial optimization}
  • Refine by Author
  • 1 Dal Sasso, Veronica
  • 1 De Giovanni, Luigi
  • 1 Labbé, Martine

  • Refine by Classification

  • Refine by Keyword
  • 1 column generation
  • 1 combinatorial optimization
  • 1 computational biology
  • 1 haplotyping
  • 1 integer programming

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail