Islands of tractability for parsimony haplotyping

Roded Sharan*, Bjarni V. Halldórsson, Sorin Istrail

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

21 Citations (Scopus)


We study the parsimony approach to haplotype inference, which calls for finding a set of haplotypes of minimum cardinality that explains an input set of genotypes. We prove that the problem is APX-hard even in very restricted cases. On the positive side, we identify islands of tractability for the problem, by focusing on instances with specific structure of haplotype sharing among the input genotypes. We exploit the structure of those instance to give polynomial and constant-approximation algorithms to the problem. We also show that the general parsimony haplotyping problem is fixed parameter tractable.

Original languageEnglish
Article number1668028
Pages (from-to)303-311
Number of pages9
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Issue number3
Publication statusPublished - Jul 2006

Other keywords

  • Analysis of algorithms and problem complexity
  • Biology and genetics
  • Graph algorithms


Dive into the research topics of 'Islands of tractability for parsimony haplotyping'. Together they form a unique fingerprint.

Cite this