Speaker: Yufeng Wu
Day:  Wednesday, 09/19/2007
Room: ITEB 336
Time: 2:00-3:00pm

 
Algorithms for Reconstructing Mosaic Pattern of a set of Recombinants.
 
Abstract
 
In this talk, I will go over a combinatorial problem arising in population genetics.  We consider a set of DNA sequences collected in a population.  These sequences are descendents of a small number of founder sequences.  Due to recombination, a current sequence is composed of blocks of founder sequences. Therefore, the set of current sequences look like a mosaic, where segments in the mosaic are inherited from the founder sequences. An interesting combinatorial question is, given a set of sequences M and assume the number of founders is fixed to be K, find the mosaic structure for M with the smallest number of blocks in the mosaic. I will describe some of current known results about this problem, including efficient algorithms for some special cases and complexity results for some other cases.