A polynomial case of the parsimony haplotyping problem
From MaRDI portal
Publication:2494824
DOI10.1016/j.orl.2005.05.007zbMath1092.92018OpenAlexW2029494815MaRDI QIDQ2494824
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
fixed parameter tractabilitycomputational biologyapproximation algorithmstotally unimodular matrices
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