On the Complexity of Fundamental Computational Problems in Pedigree Analysis
Antonio Piccolboni, Dan Gusfield · Journal of Computational Biology · 2003
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.