The pure parsimony haplotyping problem: overview and computational advances

DOI10.1111/j.1475-3995.2009.00716.xzbMath1187.92068MaRDI QIDQ3563606

Martine Labbé, Daniele Catanzaro

Publication date: 31 May 2010

Published in: International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1111/j.1475-3995.2009.00716.x

zbMATH Keywords

integer programming; computational biology; SNPs; pure parsimony haplotyping

Mathematics Subject Classification ID

90C10: Integer programming

92C40: Biochemistry, molecular biology

92D10: Genetics and epigenetics

92C42: Systems biology, networks

Related Items

A new mathematical modeling for pure parsimony haplotyping problem, Exact and heuristic approaches for the set cover with pairs problem, Better lower and upper bounds for the minimum rainbow subgraph problem, A \textit{branch} \& \textit{price} algorithm for the minimum cost clique cover problem in max-point tolerance graphs, Effective heuristics for the Set Covering with Pairs Problem

Uses Software

• RPOLY

Cites Work

• Solving haplotyping inference parsimony problem using a new basic polynomial formulation
• The phasing of heterozygous traits: Algorithms and complexity
• The haplotyping problem: an overview of computational models and solutions
• A polynomial case of the parsimony haplotyping problem
• Haplotyping Populations by Pure Parsimony: Complexity of Exact and Approximation Algorithms
• A Class Representative Model for Pure Parsimony Haplotyping
• A Set-Covering Approach with Column Generation for Parsimony Haplotyping
• Stochastic local search for large-scale instances of the haplotype inference problem by pure parsimony
• Hybrid Metaheuristics in Combinatorial Optimization: A Tutorial
• The minimum evolution problem: Overview and classification
• Computational Methods for SNPs and Haplotype Inference
• Efficient Haplotype Inference with Pseudo-boolean Optimization