Haplotyping Populations by Pure Parsimony: Complexity of Exact and Approximation Algorithms
From MaRDI portal
Publication:2890436
DOI10.1287/ijoc.1040.0085zbMath1239.90076OpenAlexW2110917138MaRDI QIDQ2890436
Giuseppe Lancia, Romeo Rizzi, Maria Cristina Pinotti
Publication date: 8 June 2012
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/6c9d8a5c83e1783d5962631be321551ab97c739b
Related Items (24)
Comparing Integer Linear Programming to SAT-Solving for Hard Problems in Computational and Systems Biology ⋮ The complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiability ⋮ 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 ⋮ Phylogeny- and parsimony-based haplotype inference with constraints ⋮ Haplotype Inferring Via Galled-Tree Networks Is NP-Complete ⋮ 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 ⋮ Boosting haplotype inference with local search ⋮ The pure parsimony haplotyping problem: overview and computational advances ⋮ Better lower and upper bounds for the minimum rainbow subgraph problem ⋮ Exact and heuristic approaches for the set cover with pairs problem ⋮ Mathematical properties and bounds on haplotyping populations by pure parsimony ⋮ Haplotype inference with pseudo-Boolean optimization ⋮ Haplotyping populations by pure parsimony based on compatible genotypes and greedy heuris\-tics ⋮ Approximation algorithms for the minimum rainbow subgraph problem ⋮ A polynomial case of the parsimony haplotyping problem ⋮ Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems ⋮ Haplotype Inference Constrained by Plausible Haplotype Data ⋮ On the Approximability of Some Haplotyping Problems ⋮ Haplotype inferring via galled-tree networks using a hypergraph covering problem for special genotype matrices ⋮ MINIMUM MOSAIC INFERENCE OF A SET OF RECOMBINANTS
This page was built for publication: Haplotyping Populations by Pure Parsimony: Complexity of Exact and Approximation Algorithms