In this paper we address the pure parsimony haplotyping problem: Find a minimum number of haplotypes that explains a given set of genotypes. We prove that the problem is APX-hard and present a 2(k-1)-approximation algorithm for the case in which each genotype has at most k ambiguous positions. We further give a new integer-programming formulation that has (for the first time) a polynomial number variables and constraints. Finally, we give approximation algorithms, not based on linear programming, whose running times are almost linear in the input size.

Haplotyping Populations by Pure Parsimony: Complexity, Exact, and Approximation Algorithms

RIZZI, ROMEO
2004-01-01

Abstract

In this paper we address the pure parsimony haplotyping problem: Find a minimum number of haplotypes that explains a given set of genotypes. We prove that the problem is APX-hard and present a 2(k-1)-approximation algorithm for the case in which each genotype has at most k ambiguous positions. We further give a new integer-programming formulation that has (for the first time) a polynomial number variables and constraints. Finally, we give approximation algorithms, not based on linear programming, whose running times are almost linear in the input size.
2004
pure parsimony haplotyping; SNPs; deterministic rounding; node cover; compact integer program
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/409588
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 106
  • ???jsp.display-item.citation.isi??? 78
social impact