A master thesis from Aalborg University
Computational Complexity of Consistency Checking
Author(s)
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
Colophon: This page is part of the AAU Student Projects portal, which is run by Aalborg University. Here, you can find and download publicly available bachelor's theses and master's projects from across the university dating from 2008 onwards. Student projects from before 2008 are available in printed form at Aalborg University Library.
If you have any questions about AAU Student Projects or the research registration, dissemination and analysis at Aalborg University, please feel free to contact the VBN team. You can also find more information in the AAU Student Projects FAQs.