Chaînes de Markov et absorption. Application à l’algorithme de Fu en génomique
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(W) d’occurences du mot W. Nous développons ici une approche duale, déterminant l’espérance et la variance du temps T(W) entre deux occurrences de W. Ceci s’appuie sur une CM auxilliaire dont les états sont les préfixes de W et T(W) 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(W) of occurrences of W. Here we develop a dual point of view dealing with the expectation and the variance of the time T(W) between two occurences of W. This is done by introducing an auxiliary MC whose states are the prefixs of W, and T(W) 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.

Mot clés : Absorption de chaînes de Markov, Mots exceptionnels, Algorithme de Fu
Keywords: Absorption of Matkov chains, Exceptional words, Fu algorithm 
@article{JSFS_2012__153_2_37_0,
     author = {Prum, Bernard},
     title = {Cha{\^\i}nes de {Markov} et absorption.  {Application} \`a l{\textquoteright}algorithme de {Fu} en g\'enomique},
     journal = {Journal de la soci\'et\'e fran\c{c}aise de statistique},
     pages = {37--51},
     publisher = {Soci\'et\'e fran\c{c}aise de statistique},
     volume = {153},
     number = {2},
     year = {2012},
     mrnumber = {3008598},
     zbl = {1316.60113},
     language = {fr},
     url = {https://numdam.org/item/JSFS_2012__153_2_37_0/}
}
TY  - JOUR
AU  - Prum, Bernard
TI  - Chaînes de Markov et absorption.  Application à l’algorithme de Fu en génomique
JO  - Journal de la société française de statistique
PY  - 2012
SP  - 37
EP  - 51
VL  - 153
IS  - 2
PB  - Société française de statistique
UR  - https://numdam.org/item/JSFS_2012__153_2_37_0/
LA  - fr
ID  - JSFS_2012__153_2_37_0
ER  - 
%0 Journal Article
%A Prum, Bernard
%T Chaînes de Markov et absorption.  Application à l’algorithme de Fu en génomique
%J Journal de la société française de statistique
%D 2012
%P 37-51
%V 153
%N 2
%I Société française de statistique
%U https://numdam.org/item/JSFS_2012__153_2_37_0/
%G fr
%F JSFS_2012__153_2_37_0
Prum, Bernard. Chaînes de Markov et absorption.  Application à l’algorithme de Fu en génomique. Journal de la société française de statistique, Tome 153 (2012) no. 2, pp. 37-51. https://numdam.org/item/JSFS_2012__153_2_37_0/

[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)