An Information Theoretic Viewpoint on Haplotype Reconstruction from SNP Fragments

The problem of haplotype reconstruction based on aligned single nucleotide polymorphism (SNP) fragments is formulated as decoding over a discrete memoryless channel. An information theoretic view point is used to illustrate the deficiency of parsimonious models such as minimum error correction model. A new computational model with genotype information is proposed and a low complexity reconstruction algorithm for this model is shown to guarantee the desired reconstruction rate by increasing the number of SNP fragments sequentially. The advantage of using genotype information is quantified by exploiting a simplified statistical model for haplotype sequences.