2005
On Counting the Number of Consistent Genotype Assignments for Pedigrees
SRBA, JiříZákladní údaje
Originální název
On Counting the Number of Consistent Genotype Assignments for Pedigrees
Název česky
Pocitani moznych konzistentnich prirazeni genove informace pro dedicne stromy
Autoři
SRBA, Jiří
Vydání
Netherlands, Proceedings of 25th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'05), od s. 1-12, 12 s. 2005
Nakladatel
Spring-Verlag
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Nizozemské království
Utajení
není předmětem státního či obchodního tajemství
Označené pro přenos do RIV
Ano
Kód RIV
RIV/00216224:14330/05:00014167
Organizační jednotka
Fakulta informatiky
UT WoS
Klíčová slova anglicky
pedigree; counting problem; linkage algorithms
Štítky
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 6. 7. 2007 09:03, RNDr. JUDr. Vladimír Šmíd, CSc.
V originále
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.
Česky
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.
Návaznosti
| MSM 143300001, záměr |
| ||
| MSM0021622419, záměr |
| ||
| 1M0545, projekt VaV |
|