Checking Consistency of Pedigree Information is NP-complete
(Preliminary Report)
Luca Aceto
October 2002 |
Abstract:
Consistency checking is a fundamental computational problem
in genetics. Given a pedigree and information on the genotypes of some of the
individuals in it, the aim of consistency checking is to determine whether
these data are consistent with the classic Mendelian laws of inheritance.
This problem arose originally from the geneticists' need to filter their
input data from erroneous information, and is well motivated from both a
biological and a sociological viewpoint. This paper shows that consistency
checking is NP-complete, even in the presence of three alleles. Several other
results on the computational complexity of problems from genetics that are
related to consistency checking are also offered. In particular, it is shown
that checking the consistency of pedigrees over two alleles can be done in
polynomial time
Available as PostScript, PDF. |