On Counting the Number of Consistent Genotype Assignments for Pedigrees
Jirí Srba September 2005 |
Abstract:
Consistency checking of genotype information in pedigrees plays
an important role in genetic analysis and for complex pedigrees the
computational complexity is critical. We present here a detailed complexity
analysis for the problem of counting the number of complete consistent
genotype assignments. Our main result is a polynomial time algorithm for
counting the number of complete consistent assignments for non-looping
pedigrees. We further classify pedigrees according to a number of natural
parameters like the number of generations, the number of children per
individual and the cardinality of the set of alleles. We show that even if we
assume all these parameters as bounded by reasonably small constants, the
counting problem becomes computationally hard (#P-complete) for looping
pedigrees. The border line for counting problems computable in polynomial
time (i.e. belonging to the class FP) and #P-hard problems is completed by
showing that even for general pedigrees with unlimited number of generations
and alleles but with at most one child per individual and for pedigrees with
at most two generations and two children per individual the counting problem
is in FP.
Available as PostScript, PDF, DVI. |