Using tree decomposition for general pedigree inference

Thumbnail Image



Journal Title

Journal ISSN

Volume Title


University of New Brunswick


Genotype-phenotype linkage analysis is becoming more promising with recent advances in high-throughput sequencing technology and the HapMap project. Genetic investigation of heritability and SNP co-location works with haplotypes, single copies of genes; however, researchers often initially find genotype sequences, reflecting both copies of a gene, rather than haplotype sequences, partly because of economic and time concerns. As a result, an effective computational method of haplotype phasing, to infer haplotypes from genotypes, is needed. The haplotype phasing problem can be classified into two subproblems concerning the existence of the relationship between individuals. This work focuses on individuals from a pedigree, and this phasing problem has been defined as the multi-recombinant haplotype configuration problem[24]. In this work, we propose a parameterized time algorithm, namely DPTH1, to infer haplotypes from the genotypes of individuals related in a pedigree, using dynamic programming over a tree decomposition of the pedigree. 1 DPTH stands for using Dynamic Programming over Tree decomposition of pedigree to find optimal Haplotype configuration for MRHC problem.