Colloquium Speaker

Speaker:Antonio Piccolboni
International Computer Science Institute
Berkeley, California
Topic:"On The Complexity Of Fundamental Computational Problems In Pedigree Analysis"
Date:Tuesday, April 4, 2000
Time:11:00 AM
Place:Gould-Simpson, Room 701

Refreshments will be served in the 7th-floor lobby of Gould-Simpson at 10:45 AM


Pedigree analysis is a central component of many current efforts to locate genes that contribute to diseases or to valuable traits. The analysis usually involves solving one of two very computation-intense problems. We analyze the complexity of these two problems. Surprisingly, we show that both problems are computationally intractable even in the very simple setting of single-locus genotype and inbreeding-free pedigrees. This is joint work with Dan Gusfield.