Format

Send to

Choose Destination
Math Biosci. 2016 Nov;281:92-97. doi: 10.1016/j.mbs.2016.09.004. Epub 2016 Sep 12.

A new mathematical modeling for pure parsimony haplotyping problem.

Author information

1
Department of Applied Mathematics, Faculty of Mathematical Science, University of Guilan, Namjoo street, Rasht, Iran.
2
Department of Applied Mathematics, Faculty of Mathematical Science, University of Guilan, Namjoo street, Rasht, Iran. Electronic address: mbagherian@guilan.ac.ir.
3
Department of Biology, Faculty of Science, University of Guilan, Najoo street, Rasht, Iran.

Abstract

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.

KEYWORDS:

Genotype; Haplotype; Mixed integer programing; Pure parsimony

PMID:
27633948
DOI:
10.1016/j.mbs.2016.09.004
[Indexed for MEDLINE]

Supplemental Content

Full text links

Icon for Elsevier Science
Loading ...
Support Center