On the complexity of fundamental computational problems in pedigree analysis. |
| |
| Authors: | Antonio Piccolboni Dan Gusfield |
| |
| Institution: | Computer Science Department, University of California, Davis 95616, USA. antonio-piccolboni@affymetrix.com |
| |
| 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. |
| |
| Keywords: | |
|
|
