Groupe de Travail de Statistique du
MAP5, Année 2006-2007.
Exposé du 30 Mars 2007
PMC pour l'étude des occurrences
de motifs dans les séquences markoviennes
Grégory Nuel,
Génopôle, Université d'Evry.
Résumé:
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/