The Haplotyping Problem: An Overview of Computational Models and Solutions

The investigation of geneticdifferences among humans has given evidence that mutations in DNAsequences are responsible for some genetic diseases. The most commonmutation is the one that involves only a single nucleotide of the DNAsequence, which is called a single nucleotide polymorphism (SNP).As a consequence, computing a complete map of all SNPs occurring in thehuman populations is one of the primary goals of recent studies in humangenomics.The construction of such a map requires to determine the DNA sequencesthat from all chromosomes. In diploid organisms like humans, eachchromosome consists of two sequences called haplotypes.Distinguishing the information contained in both haplotypes whenanalyzing chromosome sequences poses several new computational issueswhich collectively form a new emerging topic of Computational Biologyknown as Haplotyping.This paper is a comprehensive study of some new combinatorial approachesproposed in this research area and it mainly focuses on the formulationsand algorithmic solutions of some basic biological problems. Threestatistical approaches are briefly discussed at the end of the paper.