Islands of tractability for Parsimony Haplotyping

Bjarni V. Halldorsson
Reykjavik University and DeCODE Genetics

Thursday, August 3rd, 3:00 pm
Wean Hall 4625

Abstract

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.

This is joint work with Roded Sharan and Sorin Istrail.

Bio

Bjarni V. Halldorsson received his Ph.D. from the Carnegie Mellon University ACO program in 2001 and was also a participant in the Merck Computational Biology and Chemistry Graduate program. Bjarni has worked at Celera Genomics and deCODE genetics and is currently an associate professor at Reykjavik University and consultant at deCODE genetics.