The motivation of this paper is the research of exceptionaly frequent (or rare) motifs or words 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 of occurrences of . Here we develop a dual point of view dealing with the expectation and the variance of the time between two occurences of . This is done by introducing an auxiliary MC whose states are the prefixs of , and is the time this new MC needs to reach the complete word . A detailed presentation of the absoption for a finite MC is therefore presented.
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 d’occurences du mot . Nous développons ici une approche duale, déterminant l’espérance et la variance du temps entre deux occurrences de . Ceci s’appuie sur une CM auxilliaire dont les états sont les préfixes de et est alors le temps que met cette CM pour atteindre le mot complet . L’étude de l’absoption d’une CM est, pour ce faire, présentée en détail.
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 = {http://www.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 - http://www.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 http://www.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, Volume 153 (2012) no. 2, pp. 37-51. http://www.numdam.org/item/JSFS_2012__153_2_37_0/
[1] Distribution theory of runs : a Markov chain aopproach, J. Amer. Statist. Assoc., Volume 89 (1994), pp. 1050-1058 | MR | Zbl
[2] Analyse statistique des séquences biologiques, 2007 | MR
[3] Pattern Markov chains : optimal Markov chain embedding through deterministic finite automata, J. Appl. Proba., Volume 45 (2008), pp. 226-243 | MR | Zbl
[4] Finding words with unexpected frequencies in DNA sequences, J. Royal Statistical Society, Volume 57 (1995), pp. 205-220 | MR | Zbl
[5] Probabilistic and statistical properties of finite words in sequences, Applied Combinatorics in Words, Cambridge University Press (2005)