Humans are diploid. Human chromosomes consist of two copies, one inherited from the mother and the other from the father. The difference between two chromosomes of an individual is called Single Nucleotide Poly­ morphism (SNP). SNPs of a chromosome are listed sequentially and the result is called the haplotype. Single Individual Haplotyping (SIH) problem is the problem of obtaining a pair of haplotypes from a given set of SNP fragments. SIH has many applications in genetics and medical studies. It is a well­known fact that, in the presence of errors, SIH is an NP­hard problem. Due to the hardness of the problem, many inexact approaches have been introduced to solve the problem in a reasonable polynomial time, but at the cost of sacrificing the optimality. Still, exact algorithms are of great value. For instance, they can usually be used to eva‎luate the effectiveness of a heuristic algorithm. One of the most promising exact approaches to solve the problem is to reduce it to the Integer Linear Programming (ILP) problem. In this work, the goal is to strengthen the best presently available ILP formulations for the SIH problem, which are due to Etemadi et al. (2018), by adding valid inequalities (cutting planes). This is done for both the all­heterozygous case and the general case of the problem. The proposed valid inequalities can remarkably tighten the LP relaxations of the original models. Consequently, the strengthened models can be solved in significantly shorter times compared to the original models, as demonstrated by the experimental results.

حسين فلسفين

زينب مالكي، جلال ذهبي