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 BiologyThe complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiabilityA new mathematical modeling for pure parsimony haplotyping problemMathematical programming in computational biology: an annotated bibliographyMathematical Models and Solutions for the Analysis of Human GenotypesPhylogeny- and parsimony-based haplotype inference with constraintsHaplotype Inferring Via Galled-Tree Networks Is NP-CompleteImproved approximation bounds for the minimum rainbow subgraph problemSolving haplotyping inference parsimony problem using a new basic polynomial formulationThe phasing of heterozygous traits: Algorithms and complexityBoosting haplotype inference with local searchThe pure parsimony haplotyping problem: overview and computational advancesBetter lower and upper bounds for the minimum rainbow subgraph problemExact and heuristic approaches for the set cover with pairs problemMathematical properties and bounds on haplotyping populations by pure parsimonyHaplotype inference with pseudo-Boolean optimizationHaplotyping populations by pure parsimony based on compatible genotypes and greedy heuris\-ticsApproximation algorithms for the minimum rainbow subgraph problemA polynomial case of the parsimony haplotyping problemComputational Complexity of Perfect-Phylogeny-Related Haplotyping ProblemsHaplotype Inference Constrained by Plausible Haplotype DataOn the Approximability of Some Haplotyping ProblemsHaplotype inferring via galled-tree networks using a hypergraph covering problem for special genotype matricesMINIMUM MOSAIC INFERENCE OF A SET OF RECOMBINANTS




This page was built for publication: Haplotyping Populations by Pure Parsimony: Complexity of Exact and Approximation Algorithms