Computational Complexity of Consistency Checking
Authors
Johnsen, Jacob ; Knudsen, John ; Hansen, Jens Alsted
Term
4. term
Education
Publication year
2002
Abstract
Konsistenskontrol er en opgave i bioinformatik: givet et slægtstræ (pedigree) og genotypedata skal man afgøre, om de følger Mendels arvelove. Denne afhandling beviser, at opgaven er NP-komplet, hvilket betyder, at der sandsynligvis ikke findes en generel, hurtig algoritme, der altid løser den; dette er nyt for både bioinformatik- og datalogimiljøerne. Klassifikationen medfører også, at flere beslægtede opgaver er NP-hårde. Vi præsenterer den biologiske model og en formel ramme til at ræsonnere om konsistens og bruger den både i NP-komplethedsbeviset og til at analysere relaterede problemer. Vi konkluderer, at antallet af løkker (cykler) i et slægtstræ er en vigtig faktor for sværhedsgraden: slægtstræer uden løkker kan kontrolleres inden for en polynomiel tidsgrænse.
Consistency checking is a task in bioinformatics: given a pedigree (family tree) and genotype data, decide whether they follow Mendel's laws of inheritance. This thesis proves that this task is NP-complete, meaning there is unlikely to be a general, fast algorithm that always solves it; this is new to both the bioinformatics and computer science communities. The classification also implies that several related tasks are NP-hard. We present the underlying biological model and a formal framework for reasoning about consistency, and use it to give the NP-completeness proof and to analyze related problems. We conclude that the number of loops (cycles) in a pedigree is a key factor in the problem's difficulty: pedigrees without loops can be checked within a polynomial time bound.
[This abstract was generated with the help of AI]
Documents