A haplotype is a set of Single Nucleotide Polymorphisms from a given DNA and has valuable genetic information. are the most common genetic structural variants and haplotypes encode in a single DNA. Haplotype has a relevant role in several genetics studies like mapping complex disease gens, drug design and so on. However retrieving directly haplotype from DNA sample using existing technonolgies is expensive and also time consuming. This motivates the increasing interests in techniques for inferring haplotype data from genotypes which can be obtained quickly and economically. Each genotype is a description of the conflated on two haplotypes inherited from both parents. Although a number of association studies can be done using only genotypes, haplotype information is essential for the detailed analysis of the mechanisms of disease. While assessing the genetic contribution to traits, it may often be much more informative to have haplotype data rather than to have only genotype data. The haplotype inference problem under the assumption of pure parsimony consists in finding the smallest number of haplotypes that explain a given set of genotypes. This problem is proved to be NP-hard. Several methods have been proposed since Clarck introduced the first algorithm to solve haplotype inference problem in 1990. Methods for solving this problem are divided into two algorithms, namely exact and inexact methods. Existing exact methods guarantee obtaining purely parsimonious solutions but have exponential time-complexities and are not practical for large number or length of genotypes. However, inexact methods are relatively fast but do not always obtain optimum solutions. In this dissertation at frist an exact algorithm called ISHIPs is proposed which has an improvement on an existing sat-based algorithm namelySHIPs. SHIPs is the best current exact algorithm for haplotype inference probleb by pure parsimony. ISHIPs uses a heuristic algorithm namely Collhaps to compute an upper bound for the problem in the preprocessing phase. Then make a sat-based model given genotypes. And try to solve the model by using an existing sat-solver. In the next part of the dissertation a heuristic method proposed to solve haplotype inference problem called freeCollhaps. freeCollhaps algorithm introduces freedom degree concept and uses it to compute differences between a pair haplotypes.freeCollhaps has an iterative procedure. In the next step we use freeCollhaps as preprocessing phase of ISHIPs algorithm. For improving freeCollhaps algorithm, we add a simplification phase to this algorithm. The simplification phase causes to reduce the complexity of the problem instances.the best current heuristic until now is Collhaps which has a good performance on large scale datasets. The performance of proposed algorithm was evaluated on several datasets. Datasets are divided into two groups, random generated (simulated) da
