Abstract: Haplotype detection has expansive application in inherited gene＇s orientation,medicine reaction＇s research and individual identification. The haplotype assembly problem is the computing problem of inducing a individual＇s haplotypes based on several optima

Key words: Single-nucleotide polymorphisms,Genotype,Haplotype, NP-hard problem