n detta papper vi behandlar den rena parsimon haplotyping problem: Hitta ett minimum av haplotyper som förklarar en given uppsättning genotyper. Vi bevisar att problemet är APX-hård och presentera en 2 k‐1 - approximation algoritm för det fall där varje genotyp har som mest k tvetydiga positioner. Vi ger ytterligare en ny heltal-programmering formulering som har (för första gången) ett polynom antal variabler och begränsningar. Slutligen ger vi approximationsalgoritmer, inte baserade på linjär programmering, vars körtider är nästan linjära i ingångsstorleken.
Nyligen, Lancia et al. REF visade att problemet är APX-hård och gav en 2 k‐1 - approximation algoritm för datamängder där varje genotyp har som mest k tvetydiga positioner 2.
Haplotyping Populations by Pure Parsimony: Complexity of Exact and Approximation Algorithms
{'venue': 'INFORMS J. Comput.', 'journal': 'INFORMS J. Comput.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}