Exact Distribution of the Local Score for Markovian Sequences

Let be a sequence of letters taken in a finite alphabet Θ. Let be a scoring function and the corresponding score sequence where X _i = s(A _i ). The local score is defined as follows: . We provide the exact distribution of the local score in random sequences in several models. We will first consider a Markov model on the score sequence , and then on the letter sequence . The exact P-value of the local score obtained with both models are compared thanks to several datasets. They are also compared with previous results using the independent model.