Solving haplotype inference problem with non-genotyped founders via integer linear programming

摘要

In Cheng et al. (Acta Math. Appl. Sin. (English Ser.), 25:475–486, 2009), the authors present a cubic time zero-recombination haplotyping algorithm that can handle some incomplete pedigrees. More specifically, the algorithm can handle pedigrees with non-genotyped founders, provided that for each nuclear family at least one parent is genotyped and each non-genotyped founder appears in at most one nuclear family. The importance of this lies in that such cases frequently happen in real data, because some founders may have passed away and their genotype data can no longer be collected. In this paper, we further generalize the above algorithm by removing the first restriction. We present a new integer linear programming based algorithm that handles pedigrees with non-genotyped founders. The new algorithm allows the pedigrees to have nuclear families where both parents are non-genotyped founders, provided that each non-genotyped founder appears in at most one nuclear family.