On Counting the Number of Consistent Genotype Assignments for Pedigrees

SRBA, Jiří. On Counting the Number of Consistent Genotype Assignments for Pedigrees. In Proceedings of 25th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'05). Netherlands: Spring-Verlag, 2005, s. 1-12.

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ří (203 Česká republika, garant).
• 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

• Originální 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í
• Kód RIV: RIV/00216224:14330/05:00014167
• Organizační jednotka: Fakulta informatiky
• UT WoS: 000234885800038
• Klíčová slova anglicky: pedigree; counting problem; linkage algorithms
• Štítky: counting problem, linkage algorithms, pedigree
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

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.

Anotace č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: Název: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů

• MSM0021622419, záměr: Název: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy

• 1M0545, projekt VaV: Název: Institut Teoretické Informatiky

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky