HAPLOTYPE INFERENCE MODELS AND ALGORITHMS
With complete genome sequences for humans and many organisms available in the postgenomics era, one of the most important tasks in biological and medical research is to identify the genes related to diseases. The genetic study to find the association between genes and common complex diseases needs to assign a phenotype to a genetic region that is identified by one or several markers such as a single nucleotide polymorphism (SNP), microsatellite. Haplotype is a set of neighboring SNPs (or other genetic markers) that are transmitted together on the same chromosome. Because they capture information about regions descended from ancestral chromosomes, haplotypes generally have higher power than individual markers in association studies of the common complex diseases [3, 80]. Haplotypes also play a very important role in other areas of genetics such as population history studies.
Although the haplotypes can be determined by the use of existing experimental techniques , the current laboratory approaches for obtaining haplotypes directly from DNA samples are considerably expensive and time consuming; therefore they are not practical [93, 98, 92]. Hence, computational methods that offer a way of inferring haplotypes from existing data (e.g., DNA sequencing data and genotype data) become attractive alternatives. There are two classes of in silico haplotyping problems: the haplotype assembly problem and ...