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 2(l-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.
Wang
Ying
Y
Department of Applied Mathematics, Dalian University of Technology, Dalian 116024, China. wwangying2003@yahoo.com.cn
Feng
Enmin
E
Wang
Ruisheng
R
Zhang
Dan
D
D000465:Algorithms; D005838:Genotype; D006239:Haplotypes; D008957:Models, Genetic