Chaînes de Markov et absorption. Application à l’algorithme de Fu en génomique

Prum, Bernard

Journal de la société française de statistique, Tome 153 (2012) no. 2, pp. 37-51.

Cet article est motivé par la recherche de mots ou de motifs exceptionnellement rares ou exceptionnellement présents dans une séquence d’ADN chromosomique. Cette approche permettra en effet de découvrir des motifs ayant un rôle biologique néfaste ou bénéfique pour l’organisme qui le porte. On modélise alors la séquence par une chaîne de Markov (CM) et l’approche classique cherche l’espérance et la variance du nombre $N\left(W\right)$ d’occurences du mot $W$. Nous développons ici une approche duale, déterminant l’espérance et la variance du temps $T\left(W\right)$ entre deux occurrences de $W$. Ceci s’appuie sur une CM auxilliaire dont les états sont les préfixes de $W$ et $T\left(W\right)$ est alors le temps que met cette CM pour atteindre le mot complet $W$. L’étude de l’absoption d’une CM est, pour ce faire, présentée en détail.

The motivation of this paper is the research of exceptionaly frequent (or rare) motifs or words $W$ in a chromosomal DNA sequence : this approach often allows the identification of motifs playing a beeficial (or harmful) role for the organism carrying this chromosome. The sequence is modelized by a Markov chain (MC), and the classical approach consists in computing the expectation and the variance of the number $N\left(W\right)$ of occurrences of $W$. Here we develop a dual point of view dealing with the expectation and the variance of the time $T\left(W\right)$ between two occurences of $W$. This is done by introducing an auxiliary MC whose states are the prefixs of $W$, and $T\left(W\right)$ is the time this new MC needs to reach the complete word $W$. A detailed presentation of the absoption for a finite MC is therefore presented.

[1] Fu, J.C.; Koutras, M.W. Distribution theory of runs : a Markov chain aopproach, J. Amer. Statist. Assoc., Volume 89 (1994), pp. 1050-1058 | MR | Zbl

[2] Nuel, G.; Prum, B. Analyse statistique des séquences biologiques, 2007 | MR

[3] Nuel, G. Pattern Markov chains : optimal Markov chain embedding through deterministic finite automata, J. Appl. Proba., Volume 45 (2008), pp. 226-243 | MR | Zbl

[4] Prum, B.; Rodolphe, F.; de Turckheim, E. Finding words with unexpected frequencies in DNA sequences, J. Royal Statistical Society, Volume 57 (1995), pp. 205-220 | MR | Zbl

[5] Reinert, G.; Schbath, S.; Waterman, S. Probabilistic and statistical properties of finite words in sequences, Applied Combinatorics in Words, Cambridge University Press (2005)