Improvement of dynamic programming time for a long haplotype in the problem of haplotype inference on a pedigree containing some missing alleles

Abstract

This study concerns with the problem of inferring haplotypes from a genotype data for each member in a pedigree using a minimum-recombinant criterion, which is useful for reducing the cost of typical laboratory techniques. Most available methods for finding the exact solutions of this problem showed the feasibility for only short haplotypes. Based on the recent method that uses a dynamic programming algorithm, we propose some improvements to make it feasible with long haplotypes and able to work with the data containing some missing alleles. Our improvements also allow the occurrence of a few Mendelian inconsistent alleles which can possibly appear in the data. The experimental results show that the computing time of our method outperforms the original method for the case of inferring long haplotypes (more than 20 loci) in a moderate-size pedigree (15-25 members)