Computational Complexity of Consistency Checking
Translated title
Authors
Term
4. term
Education
Publication year
2002
Submitted on
2012-02-14
Abstract
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.
Documents