Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Algebraic structure of computational problems in haplotype inference


Speaker: Prof. Daniel Brown, U. of Waterloo
Location: 2112 MSB
Start time: Fri, May 26 2006, 12:10PM

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. This is joint work with PhD student Ian Harrower.