**Sujet**: Loi jointes et conditionnelles de nombres d'occurrences de
motifs dans des chaînes de Markov

**Durée**: 4 à 6 mois

**Niveau**: 2ème ou 3ème année d'école d'ingénieur

**Descriptif**:

La distribution du nombre d'occurrences d'un motif dans une chaîne de
Markov a été largement étudiée pour ses applications dans l'étude des
séquences biologiques ou en fiabilité par exemple. De nombreuses
approches concurrentes existent, certaines fondées sur des calculs
exacts (séries génératrices, simples récurrences, Markov Chain
Embedding) et d'autres sur des approximations asymptotiques
(gaussiennes, binomiales, Poisson, grandes déviations).

Récemment, des travaux ont montré que l'on pouvait unifier l'essentiel
de ces approches au travers d'une réécriture optimale du problème à
l'aide de la théorie des languages et automates, sous la forme d'une
chaîne de Markov (Pattern Markov Chain) d'ordre un dans laquelle les
occurrences du motif correspondent à des occurrences de lettres. Cette
nouvelle approche permet notamment le traitement de motifs hautement
dégénérés tels qu'on en rencontre souvent en biologie (motifs Prosite,
motifs structurés chez les promoteurs, ...) et ouvre donc de nouvelles
perspectives d'applications très prometteuses.

Parallèlement à et état des lieux, il existe de nombreux problèmes pour
lesquels le manque d'outils permettant d'étudier les lois jointes ou
conditionnelles pour le nombre d'occurrences de motifs est un frein
important à l'obtention de résultats. Dans le cas des séquences
biologiques par exemple, où la présence d'un grand nombre de signaux
connus (motifs chi, signal uptake, RBS, ...) peut perturber la
recherche de nouveaux motifs d'intérêt.

L'objectif de ce stage est d'adapter l'usage des PMC au problème des
lois jointes et conditionnelles d'occurrences de motufs, de faire
l'inventaire des méthodes existante permettant d'effectuer les calculs
(exacts ou approchés), d'en évaluer la pertinence et l'efficacité et, de
développer de nouvelles approches innovantes pour les mettre à
disposition de la communauté scientifiques (bioinformaticiens en
particulier) sous la forme de logiciels performants.

NB: Ce travail pourra le cas échéant se poursuivre sous la forme d'une
thèse.

**Encadrant**: Gregory Nuel, CR CNRS

**Structure d'accueil**:
Laboratoire MAP5, UMR 8145
Université Paris Descartes,
45, rue des Saint Pères,
75006 Paris

**Rémunération**: Environ 650 euros/mois pendant 3 mois.

**Contact**: gregory.nuel@parisdescartes.fr, tel: +33 1 42 86 33 09

**Plus de détails**:
http://www.math-info.univ-paris5.fr/...nd_pattern.pdf