A polynomial case of the parsimony haplotyping problem

DOI10.1016/j.orl.2005.05.007zbMath1092.92018OpenAlexW2029494815MaRDI QIDQ2494824

Giuseppe Lancia, Romeo Rizzi

Publication date: 30 June 2006

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2005.05.007

zbMATH Keywords

fixed parameter tractabilitycomputational biologyapproximation algorithmstotally unimodular matrices

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial optimization (90C27) Biochemistry, molecular biology (92C40) Approximation algorithms (68W25) Computational methods for problems pertaining to biology (92-08)

Related Items (12)

A new mathematical modeling for pure parsimony haplotyping problem ⋮ Mathematical programming in computational biology: an annotated bibliography ⋮ Mathematical Models and Solutions for the Analysis of Human Genotypes ⋮ Improved approximation bounds for the minimum rainbow subgraph problem ⋮ Solving haplotyping inference parsimony problem using a new basic polynomial formulation ⋮ The phasing of heterozygous traits: Algorithms and complexity ⋮ The pure parsimony haplotyping problem: overview and computational advances ⋮ Better lower and upper bounds for the minimum rainbow subgraph problem ⋮ Approximation algorithms for the minimum rainbow subgraph problem ⋮ Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems ⋮ Haplotype Inference Constrained by Plausible Haplotype Data ⋮ On the Approximability of Some Haplotyping Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Haplotyping Populations by Pure Parsimony: Complexity of Exact and Approximation Algorithms
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: A polynomial case of the parsimony haplotyping problem