The haplotype assembly model with genotype information and iterative local-exhaustive search algorithm

The minimum error correction (MEC) model for haplotype reconstruction is efficient only when the error rate in SNP fragments is low. In order to improve reconstruction rate, additional genotype information is added into MEC model as an extension to MEC model. In this paper, we first establish a new mathematical model for haplotype assembly problem with genotype information. Several properties of the mathematical model are proved. Then an iterative local-exhaustive search algorithm is proposed based on the model and its properties. The main idea is to find the optimal pair among 2l−12l−1 (l denotes the number of heterozygous sites of a genotype) haplotype pairs by performing local exhaustive search for the promising haplotype pair step by step. By experiments and comparison, extensive numerical results on real data and simulated data indicate that our algorithm outperforms the other algorithms in terms of efficiency and robustness.