Consistency checking is a problem that has its origin in the field of bioinformatics. The problem is to investigate whether a pedigree and associated genotype information adhere to the Mendelian laws of inheritance.
The main result of the thesis is the proof of consistency checking being NP-complete, which is a new result to the bioinformatics and computer science communities.Furthermore, this complexity classification causes several related problem s to be NP-hard.
Initially, the biological model is presented. On the basis of this model, we establish a formalization that enables reasoning about consistency checking. The usage of the formalization is illustrated by the NP-completeness proof and arguments on the complexity of related problems.
We conclude that an essential factor in the complexity of consistency checking is the number of loops that exists in a pedigree. This conclusion is supported by the NP-completeness proof and an argumentation on how consistency checking can be performed in non looping pedigrees within a polynomial time bound.