International Computer Science Institute
|Topic:||"On The Complexity Of Fundamental Computational Problems In Pedigree Analysis"|
|Date:||Tuesday, April 4, 2000|
|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.