title: On the complexity of fundamental computational problems in pedigree analysis.
abstract: 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 NP-hard even for pedigrees that contain no inbreeding loops.
authors: Computer Science Department, University of California, Davis 95616, USA. antonio-piccolboni@affymetrix.com
authors: Antonio
authors: A
authors: Piccolboni
authors: Dan
authors: D
authors: Gusfield
mesh_terms: D019295:Computational Biology / Q000379:methods; D008957:Models, Genetic; D010375:Pedigree; D011336:Probability