| 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 |
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.