Soutenance mémoire
Techniques de génération aléatoire uniforme : Le cas non-contextuel
Outils et lexique
Nous présentons ici quelques outils et techniques utilisés dans la suite de ce document. La plupart sont rattachés à la théorie des langages ou à la combinatoire, énumérative ou analytique.
Grammaires formelles
Les grammaires non-contextuelles apparaissent lors de l’établissement de la hiérarchie des langage formels de Chomsky-Schützenberger. Un langage formel est un ensemble potentiellement infini de séquences (ou mots) sur un alphabet. Une grammaire est un mécanisme de réécriture à base de règles qui engendrent, par dérivations successives à partir d’un symbole initial, un langage. La position d’un langage dans la hiérarchie de Chomsky-Schützenberger dépend du type des règles nécessaires pour engendrer exactement ce langage :
– Type 3 : Les grammaires régulières :
Leurs règles sont toutes de forme S → t N ou S → t ( ou toutes de forme S → N t ou S → t, mais pas de cohabitation possible de ces deux types de règle au sein d’une même grammaire régulière ). Ces règles suffisent pour engendrer les langages reconnus par un automate fini, ou ceux dénotés par une expression régulière.
– Type 2 : Les grammaires hors-contexte ou algébriques :
Leurs règles sont de la forme S → α où α est une séquence non contrainte de symboles terminaux ou non-terminaux. Ces grammaires permettent de décrire les langages horscontexte, qui sont reconnus par des automates à pile.
– Type 1 : Les grammaires contextuelles :
Elles admettent des règles de la forme αSβ → αηβ où α, β et η sont des séquences noncontraintes de symboles. De telles grammaires permettent d’engendrer les langages contextuels, reconnus par des machines de Türing travaillant sur mémoire linéaire sur la taille du mot en entrée.
– Type 0 : Les grammaires générales :
Toutes les règlesα → β, où αet β sont des séquences de symboles, sont autorisées. Toute la puissance expressive de la machine de Türing est nécessaire pour reconnaître les langages construits à partir de cette grammaire, une telle machine ne s’arrêtant pas nécessairement sur de telles entrées.
Les règles étant de façon évidente d’expressivités strictement croissantes, il est donc possible de mimer une grammaire utilisant des règles d’une catégorie donnée avec une grammaire utilisant des règles d’une catégorie supérieure. Cette hiérarchie des grammaires induit donc une hiérarchie sur les langages formels ainsi engendrés. On retrouve en outre cette hiérarchie dans les modèles de calculs nécessaires pour tester l’appartenance d’un mot à un langage. Cette hiérarchie se retrouve aussi dans la complexité des algorithmes nécessaires pour engendrer uniformément un mot du langage.
Modèles syntaxiques/modèles statistiques
Les langages formels induisent ce qu’on est tenté d’appeler des modèles syntaxiques sur les séquences génomiques. Parmi l’ensemble des séquences sur un alphabet donné (A,C,G,U pour l’ARN), ils ne font que distinguer les séquences autorisées des interdites. En l’absence d’informations supplémentaires, on est forcé de supposer que les séquences autorisées sont équiprobables, soit parmi les séquences d’une taille donnée, soit parmi l’ensemble des séquences autorisées. C’est pourquoi de nombreux formalismes se sont attachés à adjoindre une distribution de probabilité aux séquences autorisées. Les chaînes de Markov peuvent par exemple être utilisées dans une version dégénérée, en annulant certaines probabilités de transition, ce qui interdit alors l’apparition de certains motifs de tailles supérieures à l’ordre. Cependant, l’expressivité réduite sur le plan syntaxique de ce formalisme permet uniquement l’adjonction de contraintes simples, du type motif exclu, au modèle. Celles-ci peuvent en outre avoir un impact non-négligeable sur la distribution des séquences. Les grammaires stochastiques de Searls semblent conjuguer l’expressivité des grammaires non-contextuelles et la puissance d’une distribution de probabilité non-uniforme. De plus, les paramètres du modèles peuvent être appris à partir d’un ensemble de séquences par une stratégie maximiser la vraisemblance. Malheureusement, ce formalisme n’offre que peu de prise sur l’espérance de la taille des séquences engendrées, et est donc peu adapté à la génération aléatoire. Nous nous intéressons donc à un autre formalisme, introduit par Denise et al., les grammaires non-contextuelles pondérées qui, via l’introduction de la notion de pondérations, permet d’altérer la distribution des séquences et ce faisant de contraindre les espérances des différentes lettres dans les séquences générées.
Définitions formelles
Langages
Soit Σ∗ le monoïde libre, c’est à dire l’ensemble constitué des k-uplets d’élément de Σ, k ≥ 0, doté d’un produit . non-commutatif, associatif, tel que a,b ∈ Σ∗ ⇒ a.b ∈ Σ∗ , et enrichi d’un élément ε neutre pour le produit.
On appellera Σ le vocabulaire ou le lexique.
Les éléments de Σ sont alors appelés les symboles.
Les éléments de Σ∗ sont quant à eux les mots ou séquences.
On note ε le mot vide, de taille nul et élément neutre pour le produit de concaténation.
Méthode récursive
La méthode récursive repose sur l’existence d’une récurrence sur les nombres d’objets accessibles à partir d’un choix local. A partir de celle-ci, et au prix d’un précalcul, il est possible de déterminer avec quelles probabilités opérer ce choix local afin d’engendrer les objets d’une classe selon la distribution souhaitée. Un tel algorithme se décompose donc en deux phases :
– Précalcul : On calcule des valeurs (cardinaux, poids, fonction de partition) définies par récurrence pour chacun des choix locaux.
– Génération : On opère une série de poids locaux avec des probabilités judicieusement déduites des valeurs précalculées, et qui restreignent de plus en plus l’ensemble des futurs possibles (objets accessibles), jusqu’à obtenir le singleton ne contenant que l’objet engendré selon la distribution de probabilité souhaitée.
On trouve naturellement une telle récurrence dans la structure récursive qu’est une grammaire non-contextuelle. Cependant, confronté à une règle ayant pour partie droite de nombreux non-terminaux, on se pose la question de la répartition des lettres à engendrer parmi les différents non-terminaux. Une telle répartition, implémentée de façon naïve, risquerait d’être exponentielle sur le nombre maximal de non-terminaux apparaissant en partie droite d’une règle. C’est pourquoi on utilise une forme normale, la forme normale de Chomsky, qui fait apparaître au plus deux termes dans chaque partie droite de règle.
La forme normale de Chomsky : Décomposition canonique des grammaires non contextuelles .
Dans le cas général, la méthode récursive présuppose de l’existence d’une décomposition nonambiguë de la classe combinatoire considérée. Dans le cas des grammaires non-contextuelles, une telle décomposition peut être trouvée dans la forme normale de Chomsky .
Définition (Forme Normale de Chomsky (FNC)) :
Une grammaire G = (Σ,N ,X,δ) est en forme normale de Chomsky ssi, pour tout S ∈ N l’ensemble R(σ,S) = {(S,α) ∈ δ} des règles ayant S pour partie gauche est tel que :
R(δ,S) = {S → t}, t ∈ Σ
ou R(δ,S) = {S → S1S2}, S1,S2 ∈ N
ou R(δ,S) = {(S → S1), (S → S2)}, S1,S2 ∈ N
Plus simplement, on pourra dire et noter que chaque non-terminal S d’une grammaire en forme normale de Chomsky n’est concerné que par une des trois situations ci-dessous :
Règle Terminale : S → t, t ∈ Σ
Règle Produit : S → S1S2, S1,S2 ∈ N
Règle Union : S → S1 | S2, S1,S2 ∈ N
On notera F l’ensemble des grammaires en forme normale de Chomsky.
Proposition (Existence de la forme normale de Chomsky) : Pour toute grammaire G non-ambiguë, il existe une grammaire G′ en forme normale de Chomsky reconnaissant le même language, moins éventuellement le mot vide :
∀G,∃G′ ∈ F telle que L (G′) = L (G)\{ε}
On donne ci-dessous une idée de l’algorithme utilisé pour une telle mise en forme :
1. Binarisation des conjonctions
2. Restriction des productions ε à l’axiome
3. Suppression des règles unaires solitaires
4. Réécriture des règles impliquant des terminaux
5. Binarisation des disjonctions .
L’ordre des opérations lors de la mise en forme normale de Chomsky devra toutefois respecter quelques contraintes, sous peine d’obtenir une grammaire en FNC de taille exponentielle par rapport à celle de la grammaire initiale.
|
Table des matières
INTRODUCTION
1. Remerciements
2. Introduction
Partie I Etude et enrichissement des modèles pris en charge par GenRGenS
3. Techniques de génération aléatoire uniforme : Le cas non-contextuel
3.1 Outils et lexique
3.1.1 Grammaires formelles
3.1.2 Modèles syntaxiques/modèles statistiques
3.2 Définitions formelles
3.2.1 Langages
3.2.2 Grammaires non-contextuelles
3.2.3 Classe combinatoire
3.2.4 Analyse combinatoire
3.3 Principes de génération aléatoire
3.3.1 Complexité arithmétique ou complexité binaire ?
3.3.2 Méthode par rejet
3.3.3 Méthode récursive
3.3.4 Méthode de Boltzmann pour la génération d’objets combinatoires [36]
4. Application aux grammaires non-contextuelles pondérées
4.1 Génération récursive pondérée[29]
4.2 Extension de la méthode de Boltzmann aux grammaires pondérées
4.3 Grammaires pondérées et modèles markoviens
4.4 Calcul des pondérations liées à des fréquences attendues
4.4.1 Avant propos : Une optimisation de la génération en fréquence exacte
4.4.2 Evaluation de la fréquence d’un symbole dans une grammaire pondérée
4.4.3 Calcul des pondérations
5. GenRGenS : Génération de séquences et structures aléatoires
5.1 Motivation
5.2 Fonctionnement général
5.3 Modèles pris en charge
5.3.1 Modèles de Markov
5.3.2 Expressions régulières, motifs PROSITE
5.3.3 Grammaires non contextuelles pondérées
5.3.4 Modèles hiérarchiques
5.3.5 Perspectives
Partie II Etudes de l’ARN et ses structures
6. Notions de biologie moléculaires
6.1 Les macromolécules
6.1.1 L’ADN
6.1.2 L’Acide Ribonucléique (ARN)
6.2 Le dogme central de la biologie moléculaire
6.2.1 La réplication
6.2.2 La transcription
6.2.3 La traduction
6.3 Structures des ARN
6.3.1 Représentations de la structure d’une molécule
6.3.2 Structure secondaire de l’ARN : Discussion
6.3.3 Origine des données structurales
6.3.4 Fonctions et structures
7. Génération aléatoire de structures d’ARN réalistes
CONCLUSION
