MODELS FOR DNA SEQUENCES

We use Markov chain models of order m > 0 (or m = 0), denoted by Mm. The order m of the model means that the probability that a letter A, C, G or T occurs at a given position in the sequence depends on the m previous letters.

For instance, in a 1-order Markov chain (model M1), the probability of observing an A at a position i depends on the letter at position i - 1; we then have the probabilities of observing an A after an A, an A after a G, an A after a C and an A after a T, denoted respectively (A,A), (G,A), (C,A) and (T,A), and known as transition probabilities.

M0 is the simplest model where the sequence letters are independent.

To take into account the phase in coding DNA sequences, we may use Markov chains with 3-periodic transition probabilities, meaning that we distinguish the probability of observing an A (for instance) on phase 1 from an A on phase 2 and an A on phase 3. This class of model is denoted by Mm_3.

For instance, in the model M1_3, the probability of observing an A at a position i depends both on the phase associated with the i^th letter of the sequence and the letter at position i -1.

We then have the probabilities of observing an A on phase 1 after an A ((A,A)), an A on phase 1 after a G ((G,A)), an A on phase 1 after a C ((C,A)), and so on up to an A on phase 3 after a T ((T,A)).

Finding words with unexpected frequencies in DNA sequences. 11.9.98 Page: 3 of 21