Publication details

On Counting the Number of Consistent Genotype Assignments for Pedigrees



Year of publication 2005
Type Article in Proceedings
Conference Proceedings of 25th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'05)
MU Faculty or unit

Faculty of Informatics

Field Informatics
Keywords pedigree; counting problem; linkage algorithms
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info