Maximum parsimony xor haplotyping by sparse dictionary selection

Abdulkadir Elmas, Guido H. Jajamovich, Xiaodong Wang

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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.

Original languageEnglish
Article number645
JournalBMC Genomics
Issue number1
StatePublished - 23 Sep 2013
Externally publishedYes


Dive into the research topics of 'Maximum parsimony xor haplotyping by sparse dictionary selection'. Together they form a unique fingerprint.

Cite this