Improved Approach for Haplotype Inference Based on Markov Chain

摘要

Variable-order Markov model (VMM) is an important statistical method for haplotypeinference problem. It is well-suited for sparse marker maps and large-scale data. The existingalgorithm, HaploRec, solves VMM by a greedy algorithm with pruning strategy. We present animproved Expectation-Maximization (EM) algorithm for VMM, which is based on dynamic pro-gramming (DP). The computational experimental results with simulated and real data show that theproposed 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 avail-able from the interne.