A new mathematical modeling for pure parsimony haplotyping problem

- The pure parsimony haplotyping problem has been considered in this manuscript.
- A corresponding number is assigned to each haplotype and genotype.
- Using numbers, instead of sequences, would lead to less complexity of the new model.
- A polynomial IP model is presented which does not have any variable nor constraint corresponding to heterozygous sites.
- The new model is smaller than the previous models, specially for instances which have many heterozygous sites.

Pure parsimony haplotyping (PPH) problem is important in bioinformatics because rational haplotyping inference plays important roles in analysis of genetic data, mapping complex genetic diseases such as Alzheimer's disease, heart disorders and etc. Haplotypes and genotypes are m-length sequences. Although several integer programing models have already been presented for PPH problem, its NP-hardness characteristic resulted in ineffectiveness of those models facing the real instances especially instances with many heterozygous sites. In this paper, we assign a corresponding number to each haplotype and genotype and based on those numbers, we set a mixed integer programing model. Using numbers, instead of sequences, would lead to less complexity of the new model in comparison with previous models in a way that there are neither constraints nor variables corresponding to heterozygous nucleotide sites in it. Experimental results approve the efficiency of the new model in producing better solution in comparison to two state-of-the art haplotyping approaches.