|
The Complexity of Checking Consistency of Pedigree Information and
Related Problems
Luca Aceto
March 2003 |
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 with focus on a single gene and 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, and of pedigrees without loops, can be done in
polynomial time
Available as PostScript, PDF. |