Improved Approach for Haplotype Inference Based on Markov Chain

Variable-order Markov model (VMM) is an important statistical method for haplotype inference problem. It is well-suited for sparse marker maps and large-scale data. The existing algorithm, HaploRec, solves VMM by a greedy algorithm with pruning strategy. We present an improved Expectation-Maximization (EM) algorithm for VMM, which is based on dynamic programming (DP). The computational experimental results with simulated and real data show that the proposed algorithm can greatly improve the accuracy of VMM with an acceptable running time. The methods described in this paper are implemented in a software package, HMC, which is available from the internet.