The Complexity of Checking Consistency of Pedigree Information andRelated Problems

Consistency checking is a fundamental computational problem ingenetics. Given a pedigree and information on the genotypes (ofsome) of the individuals in it, the aim of consistency checking isto determine whether these data are consistent with the classicMendelian laws of inheritance. This problem arose originally fromthe geneticists' need to filter their input data from erroneousinformation, and is well motivated from both a biological and asociological viewpoint. This paper shows that consistency checkingis NP-complete, even with focus on a single gene and in the presenceof three alleles. Several other results on the computationalcomplexity of problems from genetics that are related to consistencychecking are also offered. In particular, it is shown that checkingthe consistency of pedigrees over two alleles, and of pedigreeswithout loops, can be done in polynomial time.