Maximum parsimony xor haplotyping by sparse dictionary selection

Elmas, Abdulkadir; Jajamovich, Guido H.; Wang, Xiaodong

Background: Xor-genotype is a cost-effective alternative to the genotype sequence of an individual. Recent methods developed for haplotype inference have aimed at finding the solution based on xor-genotype data. Given the xor-genotypes of a group of unrelated individuals, it is possible to infer the haplotype pairs for each individual with the aid of a small number of regular genotypes. Results: We propose a framework of maximum parsimony inference of haplotypes based on the search of a sparse dictionary, and we present a greedy method that can effectively infer the haplotype pairs given a set of xor-genotypes augmented by a small number of regular genotypes. We test the performance of the proposed approach on synthetic data sets with different number of individuals and SNPs, and compare the performances with the state-of-the-art xor-haplotyping methods PPXH and XOR-HAPLOGEN. Conclusions: Experimental results show good inference qualities for the proposed method under all circumstances, especially on large data sets. Results on a real database, CFTR, also demonstrate significantly better performance. The proposed algorithm is also capable of finding accurate solutions with missing data and/or typing errors.


  • thumnail for 1471-2164-14-645-S1.ZIP 1471-2164-14-645-S1.ZIP binary/octet-stream 64.4 KB Download File

Also Published In

More About This Work

Academic Units
Electrical Engineering
BioMed Central
Published Here
September 9, 2014