A brief introduction to computational problems in haplotype Inference

Haplotype inference is a field that results from a technological limitation: it is expensive to separate the paternal and maternal chromosomes of an organism. However, being able to do so would be useful, particuarly when one tries to identify genetic variations partly responsible for common diseases. Haplotype inference is the computation problem of inferring these different chromosome sequences, by optimizing some combinatorial or statistical requirement. What makes haplotype inference attractive to computer scientists is that one can very quickly abstract away many biological details, and focus on the underlying mathematical structure of the various problems in the field. Moreover, in many cases, this structure is attractive, making this an appealing area in which to do research. We will discuss a few of these different problems and their properties, and for one problem, the Haplotype Inference by Pure Parsimony problem, focus on some of the mathematical structure that we have discovered.