Optimal choice of word length when comparing two Markov sequences using a χ ²-statistic

Alignment-free sequence comparison using counts of word patterns (grams, k-tuples) has become an active research topic due to the large amount of sequence data from the new sequencing technologies. Genome sequences are frequently modelled by Markov chains and the likelihood ratio test or the corresponding approximate χ ²-statistic has been suggested to compare two sequences. However, it is not known how to best choose the word length k in such studies.

We develop an optimal strategy to choose k by maximizing the statistical power of detecting differences between two sequences. Let the orders of the Markov chains for the two sequences be r ₁ and r ₂, respectively. We show through both simulations and theoretical studies that the optimal k= max(r ₁,r ₂)+1 for both long sequences and next generation sequencing (NGS) read data. The orders of the Markov chains may be unknown and several methods have been developed to estimate the orders of Markov chains based on both long sequences and NGS reads. We study the power loss of the statistics when the estimated orders are used. It is shown that the power loss is minimal for some of the estimators of the orders of Markov chains.

Our studies provide guidelines on choosing the optimal word length for the comparison of Markov sequences.