A haplotype is a sequence of Single Nucleotide Polymorphism () from a given DNA and provides valuable genetic information. is the most common form of structural variant and haplotypes encode in a single DNA. Haplotype information is useful in several genetics studies including mapping complex disease genes and drug design. Also, haplotype information is essential for understanding the detailed analysis of the mechanisms of some diseases. So the study of haplotypes and consequently reconstructing them has been an important research area in the recent years. However, retrieving haplotype directly from DNA samples using existing technologies is expensive and also time consuming. This motivates the increasing interests in techniques for reconstruction of haplotypes from fragments which can be obtained quickly and economically. Fragments obtained from sequencing instruments are always associated with errors, which makes the haplotype construction difficult. In particular, the problem based on the Minimum Error Correction (MEC) model, which is the most frequently used model, is NP- hard. A formal definition for the Haplotype Assembly problem is as follows: given a set of (inconsistent) fragments obtained by DNA sequencing, find and correct the errors in the data to retrieve a maximally consistent pair of haplotypes compatible with the corrected fragments. Various methods have been proposed since Lancia introduced the first algorithm to solve this problem in 2001. Methods for solving this problem are divided into two categories, namely exact and inexact methods. Because the size of real data is usually huge, unfortunately exact algorithms are not practical for such data. Hence, the uses of heuristic algorithms on these data are recommended. The current state-of-the-art method for the problem is HapSAT. This algorithm makes a sat-based model, and tries to solve the model by using an existing sat-solver. In this dissertation, three heuristic algorithms are proposed, each of which tries to improve the solution of current heuristic algorithm, with separation of homozygote columns from heterozygote ones. The separation operation is performed before constructing the sat-based model. The first algorithm, ErrHapSAT, is based on using the error rate of the underlying sequencing machine. In this algorithm, the error rate is used as a threshold for recognize the homozygous columns. The second algorithm, named BoundHapSAT, separates the homozygous columns from heterozygous ones, using statistical analyses of matrix. Finally, in the third algorithm, called MinedHapSAT, the separation task is performed using the C4.5 algorithm. The C4.5 is a decision tree induction algorithm, which is one of the methods in machine learning. The performance of proposed algorithm was evaluated on several datasets. The datasets are divided into two groups, namely random generated (simulated) and real datasets. One of the real datasets is obtained from the Phase II of the HapMap projects, and the other one is the HuRef data that is a commonly used dataset for such researches. Each algorithm is compared with the best current algorithm. The results indicate that the proposed methods, with no sensible effect on running-time, increase the accuracy of the reconstructed haplotypes, which is very plausible for the subsequent analyses of the obtained haplotypes. Therefore, the proposed methods replace the current state-of-the-art for the Haplotype Assembly problem. Keywords: Haplotype Reconstruction, Single Nucleotide Polymorphism (), Minimum Error Correction (MEC), heuristic algorithm, NP-hard.