L’étude de la distribution des fréquences de mots ou de motifs dans les séquences markoviennes a de nombreuses applications dans des domaines aussi variés que la fiabilité, la linguistique ou la bio-informatique. Cela explique d’ailleurs pourquoi ce thème de recherche a fait l’objet depuis près d’un demi-siècle d’efforts considérables de la part de la communauté scientifique et des statisticiens et probabilistes en particulier. De nombreuses méthodes concurrentes ont été proposées, qu’elles soient exactes (séries génératrices, approches combinatoires, familles exponentielles, finite Markov chain imbedding, ...) ou asymptotiques (approximation gaussiennes, de Poisson, binomiales, grandes déviations). Pour toutes ces méthodes, la cardinalité r des motifs considérés (il s’agit du nombre de mots contenus dans le motif, par exemple, la cardinalité du motif aa[actg]t[ac] est r=8) est un paramètre important car il intervient au moins de manière linéaire dans leurs complexités. Ainsi, le traitement de motifs hautement dégénérés (r=1E+10 ou même r=1E+30) tels qu’on en rencontre par exemple en biologie (motifs nucléiques structurés dans les promoteurs, motifs PROSITE) est en général impossible.

Nicodème et al (2002) et Stefanov et Crochemore (2003) ont cependant récemment proposée une approche de ce problème fondée sur les Automates Finis Déterministes (AFD) afin de déterminer de manière efficace la série génératrice associée à un motif donné. S’il faut indiscutablement saluer cette découverte, on peut regretter que cette idée n’ait été exploitée que dans le cadre des séries génératrices alors que, comme on l’a vu, de nombreuses approches concurrentes (et parfois algorithmiquement plus efficaces) sont disponibles.

Dans le cadre de cet exposé, nous nous proposons d’étendre cette technique à un grand nombre d’approches statistiques en introduisant la notion de Pattern Markov Chain (PMC) qui permet de ramener de manière optimale l’étude de la fréquence d’un motif quelconque dans une chaîne de Markov d’ordre m à celle de la fréquence d’un sous-ensemble d’états dans une chaîne de Markov d’ordre 1 (la PMC). Nous expliquons en détails comment adapter un grand nombre de méthodes classiques à la notion de PMC et quels avantages apporte cette nouvelle vision du problème. Nous comparons ensuite l’ensemble de ces approches aussi bien sur le plan des complexités (théoriques comme empiriques) que sur la qualité des approximations.

Le package SPatt (Statistics for Patterns) implémente les méthodes présentées et est mis à disposition de la communauté : http://stat.genopole.cnrs.fr/spatt/