Donc, soit $(S, z)$ la solution du système complet, on a :

$$S(z, x) = \frac{1 - \pi x z - z^2 - \sqrt{z^4 - 2\pi x z^3 \pi - 2z^2 + \pi^2 x^2 \pi^2 z^2 - 2\pi x z + 1)}{2z^2}$$
$$z_1(x) = \frac{\pi x}{2} + 1 + \frac{\sqrt{\pi^2 x^2 + 4\pi x}}{2} \quad \text{ou} \quad z_2(x) = \frac{\pi x}{2} + 1 - \frac{\sqrt{\pi^2 x^2 + 4\pi x}}{2}$$

On choisi $z_2$ car, d'après Drmota, $\mu_c = -\frac{\partial z(1)}{\partial x z(0)}$. Or, si l'on choisi $z_1$, alors $\mu_c$ est négatif. On obtient donc :

$$\pi = \frac{4\mu^2}{1 - \mu^2}$$

On remarque que $0 \le \mu < 1$. De plus, si on impose $\pi = 1$ avant d'inverser, on retrouve la proportion $\frac{1}{\sqrt{5}}$ de bases non appariées dans une structure secondaire aléatoire uniforme.

### 10.3.2 Grammaire complète : Discussion

Essayons maintenant d'appliquer ce théorème à notre grammaire complète. Il est alors possible de satisfaire la plupart des conditions d'application du théorème 22. Cependant, la forte connexité du graphe de dépendance de la grammaire n'est triviallement pas respectée.

On a donc cherché une grammaire équivalente, et dont le graphe de dépendance serait forte-ment connexe, mais cela semble impossible, à partir du moment où on souhaite distinguer les boucles. En effet, celles ci sont des éléments terminaux de ma grammaire. Donc d'une part il faut un non terminal spécifique qui remplisse les boucles avec des caractères spéciaux. D'autre part, ce non terminal ne peut pas appeler un non terminal associé à une autre sous structure, donc il ne lui est pas possible de se concatenéner à la composante connexe centrale. Peut être est ce une limite inhérente à une décomposition correspondant de trop près à la structure ?

Cependant, Drmota explique dans [5] la condition de forte connexité par la possible apparition de distributions *pathologiques* si la condition est violée. Or l'analyse asymptotique a prouvé que les espérances des différents caractères suivent toutes (sauf t3et t5) la loi invoquée par Drmota. Il nous faudrait donc des études plus poussées dans le domaine de la combinatoire analytique pour déterminer si ces conditions sont nécessaires. De plus, les résultats du théorème de Drmota vont plus loin que donner une formule pour la proportion $\mu$ des symboles à l'asymptotique. Il en déduit la variance et une expansion des coefficients à $O(\sqrt{n})$ près.

Il n'est donc pas encore possible d'appliquer ces principes à la grammaire complète, cependant nous pensons prouver à court terme d'adaptation de la grammaire au cadre du théorème.
BIBLIOGRAPHIE

[1] Peter De Rijk an Jan Wuyts and Rupert De Wachter. Rnaviz2: an improved representation of rna secondary structure. *Bioinformatics*, 2(19):299-300, 2003.

[2] M. Vauchaussade de Chaumont and G. Viennot. Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire. Séminaire Lotharingien de Combinatoire, 1983.

[3] A. Denise. Structures aléatoires, modèles et analyse des génomes, 2001. *Mémoire d'habilitation à diriger des recherches*.

[4] A. Denise, O. Roques, and M. Termier. Random generation of words of context-free languages according to the frequencies of letters. In D. Gardy and A. Mokkadem, editors, *Mathematics and Computer Science: Algorithms, Trees, Combinatorics and probabilities*, Trends in Mathematics, pages 113-125. Birkhäuser, 2000.

[5] Michael Drmota. Systems of functional equations. *Random Structures and Algorithms*, 10(1-2):103-124, 1997.

[6] Philippe Duchon, Philippe Flajolet, Guy Louchard, and Gilles Schaeffer. Random sampling from Boltzmann principles. In P. Widmayer et al., editor, *Automata, Languages, and Programming*, number 2380 in Lecture Notes in Computer Science, pages 501-513. Springer Verlag, 2002. Proceedings of the 29th ICALP Conference, Malaga, July 2002.

[7] Philippe Duchon, Philippe Flajolet, Guy Louchard, and Gilles Schaeffer. Boltzmann samplers for the random generation of combinatorial structures. *Combinatorics, Probablity, and Computing*, 2003. A paraitre.

[8] L.Noe et G.Kucherov. Communication personnelle.

[9] Philippe Flajolet, Bruno Salvy, and Paul Zimmermann. Automatic average-case analysis of algorithm. *Theoretical Computer Science*, 79(1):37-109, 1991.

[10] Philippe Flajolet, P. Zimmermann, and B. Van Custom. A calculus for the random generation of combinatorial structures. Technical Report RR-1830, INRIA, 1993.

[11] F.Lefebvre. A grammar-based unification of several alignment and folding algorithms. In *Proceedings of the Fourth International Conference on Intelligent Systems for Molecular Biology*, pages 143-154. AAAI Press, 1996.

[12] Ivo L. Hofacker, Peter Schuster, and Peter F. Stadler. Combinatorics of RNA secondary structures. *Discr. Appl. Math.*, 88:207-237, 1998.

[13] Ivo L. Hofacker, Peter Schuster, and Peter F. Stadler. Combinatorics of rna secondary structures. *Discrete Applied Mathematics*, 88:207-237, 1998.
[14] Cannone J.J., Subramanian S. and Schnare M.N. and Collett J.R. and D'Souza L.M. and Du Y. and Feng B. and Lin N. and Madabusi L.V. and Muller K.M. and Pande N. and Shang Z. and Yu N., and Gutell R.R. The comparative rna web (crw) site: An online database of comparative sequence and structure information for ribosomal, intron, and other rnas. *BioMed Central Bioinformatics*, 3(2), 2002.

[15] Leontis N. and Westhof E. Geometric nomenclature and classification of rna base pairs. *RNA*, 7:499-512, 2001.

[16] M. Nebel. Combinatorial properties of rna secondary structures, 2001. Frankfurter Informatik-Berichte 2/01, Institut für Informatik, Johann Wolfgang Goethe-Universität, Frankfurt a. M., 2001.

[17] M. Nebel. A unified approach to the analysis of horton-strahler parameters of binary tree structures, 2001. Frankfurter Informatik-Berichte 1/01, Institut für Informatik, Johann Wolfgang Goethe-Universität, Frankfurt a. M., 2001.37.

[18] P. Nicodeme, B. Salvy, and P. Flajolet. Motif statistics, 1999.

[19] M. Regnier. Generating functions in computational biology, 1997. Lecture at Algorithms Seminar, INRIA.

[20] D.B. Searls. Formal language theory and biological macromolecules. Series in Discrete Mathematics and Theoretical Computer Science, 47:117-140, 1999.

[21] F. Tahi, S. Engelen, and M. Régnier. A fast algorithm for RNA secondary structure prediction including pseudoknots approach, 2003. to be presented at BIBE'03, Washington DC.

[22] M. Vauchaussade de Chaumont and X.G. Viennot. Enumeration of RNA's secondary structures by complexity. In V. Capasso, E. Grosso, and S.L. Paven-Fontana, editors, Mathematics in Medicine and Biology, volume 57 of Lecture Notes in Biomathematics, pages 360-365, 1985.

[23] J. Waldispühl, B. Behzadi, and J.-M. Steyaert. An approximate matching algorithm for finding (sub-)optimal sequences in s-attributed grammars. In Proceedings of the first European Conference on Computational Biology, ECCB 2002, volume 18 of Bioinformatics, pages 250-259. OXFORD University Press, 2002.

[24] M. S. Waterman. Secondary structure of single stranded nucleic acids. Advances in Mathematics Supplementary Studies, 1(1):167-212, 1978.

[25] J.D. Watson and F. H. C. Crick. Molecular structures of nucleic acids. Nature, 4356:737-738, 1953.

[26] Herbert S. Wilf. A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects. Advances in Mathematics, 24:281-291, 1977.

[27] Herbert S. Wilf. *generatingfunctionology*. Academic Press Inc., Boston, second edition, 1994.

[28] M. Zucker. Rna folding by energy minimization.
Définitions

<table><tr><td>1</td><td>Structure secondaire de l'ARN</td><td>20</td></tr><tr><td>2</td><td>K-Boucles</td><td>27</td></tr><tr><td>3</td><td>fonction paramètre</td><td>33</td></tr><tr><td>4</td><td>Paramètre hérité additivement</td><td>33</td></tr><tr><td>5</td><td>Série génératrice ordinaire</td><td>34</td></tr><tr><td>6</td><td>Coefficient d'un série génératrice</td><td>34</td></tr><tr><td>7</td><td>Série génératrice multivariée</td><td>36</td></tr><tr><td>8</td><td>Série génératrice de langage</td><td>37</td></tr><tr><td>9</td><td>Fraction rationelle</td><td>41</td></tr><tr><td>10</td><td>Fonction Algébrique</td><td>42</td></tr><tr><td>11</td><td>alt. Fonction Algébrique</td><td>42</td></tr><tr><td>12</td><td>Fonction Analytique</td><td>43</td></tr><tr><td>13</td><td>Fonction Méromorphe</td><td>43</td></tr><tr><td>14</td><td>Ordre exponentiel</td><td>44</td></tr><tr><td>15</td><td>Singularité</td><td>44</td></tr><tr><td>16</td><td>Singularité dominante</td><td>45</td></tr><tr><td>17</td><td>Structures secondaires de Waterman</td><td>50</td></tr><tr><td>18</td><td>Appariement</td><td>50</td></tr><tr><td>19</td><td>Sous-structures d'une structure secondaire</td><td>52</td></tr><tr><td>20</td><td>Ordre d'une structure secondaire d'ARN</td><td>53</td></tr><tr><td>21</td><td>Mots de Motzkin</td><td>54</td></tr><tr><td>22</td><td>Pyramide maximale d'un mot de Motzkin</td><td>56</td></tr><tr><td>23</td><td>Grammaire non contextuelle</td><td>78</td></tr><tr><td>24</td><td>Chemin culminant</td><td>99</td></tr><tr><td>25</td><td>Chemin culminant (h,y)-initié</td><td>100</td></tr></table>
ANNEXE
A. GÉNÉRATION ALÉATOIRE DE CHEMINS CULMINANTS
## A.1 Introduction

Le problème de la génération aléatoire de chemins culminants nous a été présenté par G. Kucherov et L.Noe qui, au cours de travaux sur des algorithmes d'alignement global de sequences, ont été amenés à engendrer des alignements culminants aléatoires sans insertions/deletions. Un alignement sans indels peut être vu comme une séquences de bits 0 ou 1, où 0 représente un mismatch et 1 un match. Chaque match crédite l'alignement de a points, et chaque mismatch débite l'alignement de b points. Un alignement est alors dit culminant si son score total est supérieur à ceux de ses sous-parties.

## A.2 Les chemins culminants

On substitue aux couples séquence/score des chemins positifs culminants à pas a-montants et b-descendants.

**Définition 24 (Chemin culminant) :**

Un chemin $C$ positif culminant à pas a-montants et b-descendants est un chemin de $\mathbb{Z}^2$ formé de pas $(1, a)$ et $(1, -b)$ allant de $(0, 0)$ à $(n, h)$ tel que :

* Le chemin $C$ est positif : $\forall (k, y) \in C, y > 0$

* Le chemin $C$ culmine en $n$ : $\forall k < n, (k, y) \in C \Rightarrow y < h$

On notera $C_n$ l'ensemble des chemins positifs culminants.

On remarquera que la condition de positivité traduit l'optimalité de l'alignement. En effet, un chemin ayant un point d'ordonnée négative est susceptible d'être optimisé par son suffixe dé-marrant en son point d'ordonnée la plus faible.

## A.3 Génération uniforme de chemins culminants

Une approche classique pour la génération aléatoire d'objets décomposables consiste à compter les nombres d'objets $n_X$ accessibles après un choix $X$, pour toutes les valeurs possibles de $X$. Si les ensembles d'objets potentiellement construits sont disjoints pour toutes les valeurs de $X$, alors on en déduit les probabilités de choisir les différentes valeurs de $X$ afin de respecter l'uniformité des structures générées.

On préfère une telle approche à une génération par rejet, dont la complexité dépend trop fortement des paramètres $a$ et $b$.

### A.3.1 Technique classique de génération uniforme séquentielle

Soit $L$ un ensemble de mots sur l'alphabet $X = \{x_1, x_2, \dots, x_m\}$. Soit $L_n$ la restriction de cet ensemble aux mots de taille $n$.

Soit $w_p$ le préfixe d'un mot de $L_n$, on appelle $p_x(w_p)$ la probabilité que $w_p$ soit suivi par $x \in X$ dans un mot de $L_n$.

$$p_x(w_p) = \frac{|\{w'|w_p \cdot x \cdot w' \in L_n\}|}{|\{w'|w_p \cdot w' \in L_n\}|}$$

**Proposition 2 :**

Si l'on sait calculer les $p_x(w_p)$, alors on sait engendrer uniformément des mots de $L_n$.
**Preuve:** En effet, partant du préfixe $\epsilon$, on le prolonge par des lettres $c_1, c_2, c_3, \dots, c_n$ choisies selon les probabilités $p_{c_1}(\epsilon), p_{c_2}(c_1), p_{c_3}(c_1.c_2), \dots, p_{c_n}(c_1.c_2. \dots .c_{n-1})$. La probabilité d'émission d'un mot $w = c_1.c_2.c_3. \dots .c_n$ est donc égale à :

$$ 
\begin{aligned}
p(c_1 \dots c_n) &= p_{c_1}(\epsilon) * p_{c_2}(c_1) * p_{c_3}(c_1.c_2) * \dots * p_{c_n}(c_1.c_2. \dots .c_{n-1}) \\
&= \frac{|\{w'|c_1.w' \in L_n\}|}{|L_n|} * \frac{|\{w'|c_1.c_2.w' \in L_n\}|}{|\{w'|c_1.w' \in L_n\}|} * \dots * \frac{|\{w'|c_1, \dots, c_{n-1}.w' \in L_n\}|}{|L_n|} \\
&= \frac{|\{w'|c_1.w' \in L_n\}|}{|\{w'|c_1.c_2.w' \in L_n\}|} * \frac{|\{w'|c_1.c_2.w' \in L_n\}|}{|\{w'|c_1.c_2.w' \in L_n\}|} * \dots * \frac{|\{w'|c_1, \dots, c_n.w' \in L_n\}|}{|L_n|} \\
&= \frac{1}{|L_n|} \operatorname{car}\{w'|c_1, \dots, c_n.w' \in L_n\} = \epsilon
\end{aligned}
$$

Tous les mots de $L_n$ étant choisi par ce processus avec une probabilité $\frac{1}{|L_n|}$, ce procédé de génération aléatoire est donc uniforme.

Touver un algorithme de génération aléatoire uniforme de mots de ce langage revient donc à compter les suffixes des mots du langage étudié.

### A.3.2 Application aux chemins culminants

<figure><img src="image_44.png" /><figcaption>Fig. A.1: Les suffixes B associés à un préfixe A de $C_n$ dépendent uniquement des ordonnées $h$ maximale atteinte et $y$ actuelle</figcaption></figure>

Dans le cas général, on voit bien qu'il est déraisonnable de précalculer les $p_x(w_p)$, $m^n$ valeurs devant être stockées. Cependant, dans le cas des chemins culminants, il n'est pas nécessaire de compter les différents suffixes pour tous les mots sur $X^n$. Au moment de prolonger un préfixe de $C_n$, les seules données d'intérêt sont l'ordonnée maximale $h$ atteinte par le chemin au sein du préfixe et l'ordonnée $y$ à laquelle arrive le préfixe (voir Figure A.1). On introduit donc la notion de chemin culminant $(h,y)$-initié.

**Définition 25 (Chemin culminant $(h,y)$-initié) :**

Un chemin culminant $(h,y)$-initié est un chemin positif culminant formé de pas $(1, a)$ et $(1, -b)$ allant de $(0, y)$ à $(n, y')$, $y' > h$

Soit $C_{y,h,n}$ l'ensemble des chemins culminants $(h,y)$-initiés de taille $n$.

**Proposition 3 :**

$\forall w_p$, chemin de $(0, 0)$ à $(k, y)$ de hauteur $\max$. atteinte $h$ :

$$ \{w'|w_p.w' \in C_n\} = C_{y,h,n} $$
On dénombre alors les chemins culminants $(h,y)$-initiés de taille $n$ pour toutes les valeurs possibles des paramètres $h, y$ et $n$, et on en déduit immédiatement les valeurs des $p_x(w_p)$. Pour cela, on exhibe une décomposition récursive des chemins culminants $(h,y)$-initiés :

**Proposition 4 :**

$$ C_{y,h,n} = \begin{cases} \{1\}.C_{y+a,Max(h,y+a),n-1} \cup \{0\}.C_{y-b,h,n-1} & \text{Si } y > b \\ \{1\}.C_{y+a,Max(h,y+a),n-1} & \text{Sinon} \end{cases} $$ $$ C_{y,h,1} = \begin{cases} \emptyset & \text{Si } (y+a \le h) \text{ ou } (y < 0) \\ \{1\} & \text{Sinon} \end{cases} $$

**Preuve :** Commençons par les chemins de $C_{y,h,1}$ :

- Un chemin de taille 1 ne peut être un pas $(1, -b)$ ($0$) car alors l'ordonnée du point d'absisse 0 est supérieure à celle du point d'absisse 1, ce qui viole la condition de chemin culminant.

- Un chemin constitué d'un unique pas ascendant ne peut être considéré comme un chemin culminant $(h,y)$-initié que si il respecte les contraintes de positivité ($y \ge 0$) et finit en une ordonnée supérieure à $h$ ($y + a > h$).

Prenons ensuite un chemin $\Gamma$ de $C_{y,h,n}$, $n > 1$ :

* $\Gamma$ commence par un pas montant 1 :

<figure><img src="image_45.png" /></figure>

$\Gamma$ est culminant, son ordonnée d'arrivée est donc à la fois supérieure à $h$ et à $y + a$.

⇒ **1.** est un chemin reliant $(1, y + a)$ à $(n, y')$, $y' > h$ et $y' > y + a$.

De plus, $\Gamma$ est positif, donc **1.** l'est aussi. Enfin, **1.** est culminant. En effet, si **1.** n'est pas culminant, alors $\Gamma$ ne l'est pas non plus.

⇒ **1.** est un chemin de $C_{y+a,Max(h,y+a),n-1}$

* $\Gamma$ commence par un pas descendant 0 :
<figure><img src="image_46.png" /></figure>

On remarque que $y > b$. En effet, si $y \le b$, alors le pas descendant viole la contrainte de positivité stricte. $\Gamma$ est culminant, son ordonnée d'arrivée est cette fois supérieure à $h$.

⇒ **2.** est un chemin reliant (1, $y-b$) à (n, $y'$), $y' > h$

De plus, $\Gamma$ est positif, donc **2.** l'est aussi. Enfin, de même que pour **1.**, **2.** est culminant.

⇒ **2.** est un chemin de $C_{y-b,h,n-1}$ si $y > b$.

On remarquera que la décomposition récursive exhibée n'admet aucune ambiguïté, car les objets énumérés commencent par des caractères différents pour chacunes des opérandes de l'union. On peut donc transposer cette relation sur des ensembles sur les cardinaux de ceux ci, ce qui nous permet de proposer l'algorithme suivant.

### A.3.3 Algorithme

A partir de cette récurrence, on calcule les nombres $C(y, h, n)$ de chemins de taille $N$, pour toutes les valeurs des paramètres $y$ et $h$.

**Algorithme (Comptage):**

Pour tout $h \in [0,a*N]$ et $y \in [0,a*N]$:
  Si ($y+a$>h)
    Alors $C(y,h,1) := 1$;
    Sinon $C(y,h,1) := 0$;

Pour $n$ allant de 2 à $N$:
Pour tout $h \in [0,a*N]$ et $y \in [0,a*N]$:
  Si ($y$>b)
    Alors $C(y,h,n) := C(y+a, \text{Max}(h,y+a),n-1) + C(y-b,h,n-1)$;
    Sinon $C(y,h,n) := C(y+a, \text{Max}(h,y+a),n-1)$;

Une fois cette table remplie, on sait selon quelles probabilités prolonger un chemin positif d'un pas $a$-ascendant ou d'un pas $b$-descendant.

**Algorithme (Génération):**

```
y := 0;
h := 0;
S := e;
Pour $n$ allant de $N$ à 2
```
p_{x,S} := C(y+a,Max(h,y+a),n-1)/C(y,Max(h),n);
Si (ran() < p_{x,S})
Alors y := y+a; h := max(h,y); S := S + '1';
Sinon y := y-b; S := S + '0';
S := S + '1';

### A.3.4 Complexités

La phase de comptage a une complexité en temps et en espace de $O(N^3 * a^2)$.

La complexité en temps est ici donnée en opérations arithmétiques. Cependant, les nombres manipulés croissant exponentiellement avec N, on doit intégrer à la complexité de l'algorithme le surcoût engendré par l'emploi d'arithmétique en précision arbitraire. Ce surcoût étant de l'ordre, pour chaque opération, de la somme des logarithmes des opérandes, on peut conjoncturer un comportement en $O(N^4 * a^2)$ de la complexité *machine*.

La phase de génération est quant à elle linéaire en opérations arithmétiques et en espace. De même, on peut conjecturer un comportement en $O(N^2)$ lorsque les nombres manipulés croissent exponentiellement sur N.

Enfin, si l'on ne souhaite engendrer que les chemins culminants de hauteur donnée $h$, on peut alors obtenir un algorithme de complexité $O(N * h)$ en modifiant très légèrement la récurrence permettant le comptage des coefficients.

$$C_{y,n} = \begin{cases} \{1\} \cdot C_{y+a,n-1} & \text{Si } y \le b \\ \{0\} \cdot C_{y-b,n-1} & \text{Si } y + a \ge h \\ \{1\} \cdot C_{y+a,n-1} \cup \{0\} \cdot C_{y-b,n-1} & \text{Sinon} \end{cases}$$

$$C_{y,1} = \begin{cases} \{1\} & \text{Si } (y + a = h) \\ \emptyset & \text{Sinon} \end{cases}$$
B. GENRGENS :
GENERATION OF RANDOM GENOMIC SEQUENCES
## B.1 Contexte

Un des problèmes importants liés à l’analyse in silico des génomes génomiques est l’évaluation du “bruit de fond”. Il s’agit de déterminer dans quelle mesure des structures ou des propriétés observées sur des séquences biologiques déduites ont une réelle signification ou sont là “par hasard”. Le raisonnement qui prévaut est le suivant : si une propriété est réellement signifiante d’un point de vue biologique, alors elle ne doit pas se manifester dans une séquence aléatoire, ou s’y manifester de façon très différente par rapport à une séquence biologique. Dans certains cas, comme l’évaluation de la sur-représentation de motifs, il existe des méthodes purement analytiques pour comparer séquences biologiques et séquences aléatoires. Dans d’autres cas, il est nécessaire de recourir à la simulation, c’est-à-dire la génération aléatoire in silico de séquences. Il s’agit d’engendrer des séquences de longueur *n* fixée, obéissant à un modèle déterminé. Il est donc intéressant pour un biologiste voulant valider une hypothèse de pouvoir engendrer des séquences aléatoires respectant des contraintes. D’autre part, des séquences aléatoires permettent la calibration, voir la validation d’outils d’inférence. Face à cette demande, nous avons conçu un logiciel mettant en oeuvre différentes techniques de générations aléatoires, GenRGenS.

## B.2 GenRGenS

GenRGenS (Generation of Random Genomic Sequences) est une boîte à outils pour la génération aléatoire de séquences selon différents types de modèles. D’un usage simple (Interface Graphique) et développé en Java, ce qui le rend exécutable sur toutes les plateformes, il est destiné à des bioinformaticiens sensibilisés aux formalismes linguistiques et/ou statistiques. GenRGenS est téléchargeable avec ses sources dans sa version 1.0 à l’adresse :

www.lri.fr \ ~denise \ GenRGenS

Les modèles de génération actuellement supportés par GenRGenS sont le modèle markovien et le modèle des grammaires non contextuelles pondérées.

### B.2.1 Modèle markovien

Ce modèle bien connu impose des contraintes statistiques aux occurrences de sous-séquences dans les séquences engendrées. Il est paramétré par un entier, l'orde de la chaîne de Markov, qui détermine la taille des sous-séquences considérées. GenRGenS permet de gérer des chaînes de Markov hétérogènes à plusieurs phases (cas des séquences codant pour l'ARN) et certains modèles de Markov cachés. En ce qui concerne la génération,<fnref n="1" /> on dispose d'un algorithme linéaire sur la taille de la séquence voulue, qui traite aussi les variantes hétérogènes. La figure 1 présente un exemple de fichier de description qui est fourni en entrée à GenRGenS pour engendrer des séquences aléatoires markoviennes. Un tel fichier de description peut être réalisé automatiquement par GenRGenS si on lui fournit une séquence de référence et certains paramètres comme l'ordre de la chaîne et le nombre de phases. De plus, l'approche markovienne présente l'avantage d'être entièrement automatisable quand la linguistiques markovienne est déduite du séquencement d'un matériel génétique réel. Un petit utilitaire fourni avec GenRGenS et piloté par son interface graphique construit alors automatiquement le fichier de description markovien associé.

### B.2.2 Génération avec contraintes syntaxiques

Moins populaire auprès des biologistes que le modèle markovien, ce type de génération est basé sur le formalisme des grammaires non contextuelles (ou algébriques). Il engendre des mots pour

<footnote n="1">¹ W.M. Fitch. Random Sequences. Journal of Molecular Biology, 163:171-176, 1983</footnote>
TYPE = MARKOV

ORDER = 2

START =

ggg 7

cca 3

FREQUENCIES =

aaa 00 aca 50 aga 12 ata 56

aac 00 acc 78 agc 12 atc 23

aag 00 acg 51 agg 51 atg 23

aat 00 act 32 agt 53 att 02

gaa 21 gca 84 gga 51 gta 31

gac 12 gcc 64 ggc 51 gtc 51

gag 51 gcg 61 ggg 35 gtg 18

gat 86 gct 43 ggt 84 gtt 68

caa 23 cca 86 cga 10 cta 10

cac 15 ccc 78 cgc 21 ctc 51

cag 46 ccg 46 cgg 32 ctg 35

cat 91 cct 45 cgt 51 ctt 11

taa 86 tca 84 tga 02 tta 61

tac 86 tcc 43 tgc 23 ttc 31

tag 48 tcg 48 tgg 35 ttg 18

tat 65 tct 56 tgt 81 ttt 81

<caption>Fig. B.1: Un fichier de description GenRGenS pour un modèle markovien d'ordre deux. La clause START permet de déterminer une loi pour le début de la séquence : elle commencera par ggg 7 fois sur 10, par cca 3 fois sur 10. Dans la clause FREQUENCIES, le nombre qui suit chaque trinucléotide est le nombre d'occurrences observées dans une séquence biologique de référence. Les probabilités associées au modèle sont calculées en conséquence par GenRGenS.</caption>

lesquels les contraintes ne sont plus uniquement statistiques, mais aussi structurelles. Les grammaires formelles permettent de décrire des séquences soumises à des contraintes structurelles, comme par exemple la présence ou l'absence de motifs particuliers dans les séquences, ou des interactions à distance dans les séquences d'ARN. Ainsi, le codage classique des structures secondaires par des mots de Motzkin [22, 20], selon lequel un nucléotide non apparié est représenté par une lettre c et les deux nucléotides 5' et 3' d'un appariement sont respectivement codés par un a et un b, définit un langage qui peut être décrit et engendré par une grammaire non contextuelle (figure 2). Le concept de grammaire pondérée, présenté dans [4], permet d'engendrer des séquences ainsi structurées tout en respectant des contraintes statistiques données portant sur les fréquences des lettres. A chaque lettre est attribuée un poids qui influe sur son nombre moyen d'occurrences dans les séquences engendrées. L'algorithme de génération [4] est linéaire en temps sur la taille des mots souhaités après un précalcul de complexité quadratique. Le principe de génération offre aussi la possibilité d'adjoindre aux contraintes syntaxiques des contraintes statistique portant sur la représentation des symboles terminaux, ce au moyen d'un système de poids. La génération avec contraintes grammaticales est donc non seulement paramétrée par une grammaire, mais aussi par un ensemble de couples Symboles Terminaux/Poids.

## B.3 Perspectives

Bientôt, GenRGenS s'enrichira d'autres modes de génération :

1. Un mode "chainé" qui permettra de cumuler différents niveaux d'abstractions. Par exemple, la structure d'une séquence pourra être définie par une grammaire de "haut niveau" quand son détail sera défini par des liguistiques markoviennes.

2. Des modes permettant d'engendrer des séquences aléatoires à partir d'expressions régulières ou PROSITE, de profils HMM et de profils généralisés.

D'autre part, des techniques de génération aléatoires basées sur des formalismes capables de modéliser des pseudo-noeuds sont à l'étude. Les grammar non-contextuelles sont en effet d'expressivités
<figure><img src="image_47.png" /><figcaption>Fig. B.2: Une structure secondaire qui correspond au mot aaaaaaaaaadccccccbbääaaadccccb-baaaaadccccccbbbbbbbbbbbbb, et une grammaire pondérée du langage. Au codage classique on a ajouté la lettre d qui permet, par le biais des pondérations, de faire varier le nombre moyen de boucles dans les structures engendrées aléatoirement. Plus le poids d'une lettre est élevé, plus sa fréquence est élevée dans les mots engendrés. Ici, la forte pondération de a indique que l'on désire favoriser les longueurs des tiges par rapport à celles des boucles.</figcaption></figure>

insuffisante pour modéliser de telles structures. Un des formalismes étudié actuellement est le formalisme de String Variable Grammars de Searl qui feront l'objet d'un ajout à GenRGenS si une procédure de génération aléatoire de complexité raisonnable est trouvée.
C. COMPARAISON GÉNÉRATION UNIFORME, SÉQUENCE RÉELLE

<figure><img src="image_48.png" /><figcaption>Fig. C.1 : Structures secondaires réelle d'ARNr 16s</figcaption></figure>
<figure><img src="image_49.png" /><figcaption>Fig. C.2 : Structures secondaires aléatoires uniformes</figcaption></figure>

<figure><img src="image_50.png" /><figcaption>Fig. C.3 : Structures secondaires aléatoires pondérées</figcaption></figure>
D. STATISTIQUES STRUCTURELLES BRUTES DES ARNR
<table><thead><tr><th>Règne</th><th>CS</th><th>NB</th><th>#B</th><th>#B PK</th><th>5'</th><th>3'</th><th>#E</th><th>#B/E</th><th>#R</th><th>#B/R</th><th>#B</th><th>#B/B</th><th>#BI</th><th>#BI</th><th>#BI/BI</th><th>#Remp</th><th>#Remp/MB</th></tr></thead><tbody><tr><td rowspan="3">Archae</td><td>5s</td><td>1</td><td>123</td><td>O</td><td>3</td><td>3</td><td>8</td><td>76</td><td>3</td><td>4</td><td>2</td><td>17</td><td>2</td><td>13</td><td>1</td><td>6</td><td>3</td><td>3</td></tr><tr><td>16s</td><td>18</td><td>1486,06</td><td>37,56</td><td>3,67</td><td>12,17</td><td>94,5</td><td>892,56</td><td>24,06</td><td>63,06</td><td>30</td><td>176,06</td><td>25,44</td><td>146,28</td><td>21</td><td>191,28</td><td>59</td><td>2,81</td></tr><tr><td>23s</td><td>12</td><td>2946,67</td><td>115,67</td><td>1,67</td><td>9,17</td><td>203,83</td><td>1656</td><td>46,17</td><td>89,17</td><td>69,83</td><td>390,33</td><td>54</td><td>406,17</td><td>33,83</td><td>393,17</td><td>136,5</td><td>4,05</td></tr><tr><td rowspan="3">Bacteria</td><td>5s</td><td>24</td><td>120,67</td><td>O</td><td>0,83</td><td>1,29</td><td>7,13</td><td>77,42</td><td>2,04</td><td>3</td><td>2</td><td>16,83</td><td>2,08</td><td>11,25</td><td>1</td><td>9,04</td><td>3</td><td>3</td></tr><tr><td>16s</td><td>231</td><td>1531,06</td><td>36,2</td><td>8,42</td><td>13,6</td><td>103,73</td><td>902,88</td><td>28,43</td><td>66,55</td><td>31,07</td><td>177,52</td><td>28,16</td><td>166,58</td><td>22,07</td><td>194,51</td><td>62,21</td><td>2,82</td></tr><tr><td>23s</td><td>100</td><td>3325,42</td><td>334,3</td><td>2,14</td><td>5,64</td><td>198,66</td><td>1638,88</td><td>41,76</td><td>82,42</td><td>68,66</td><td>392,48</td><td>55,72</td><td>380,18</td><td>32,52</td><td>822,68</td><td>132,76</td><td>4,09</td></tr><tr><td rowspan="3">Eucaryotes</td><td>5s</td><td>1</td><td>119</td><td>O</td><td>O</td><td>1</td><td>6</td><td>74</td><td>1</td><td>2</td><td>2</td><td>16</td><td>2</td><td>19</td><td>1</td><td>6</td><td>3</td><td>3</td></tr><tr><td>16s</td><td>38</td><td>1648,5</td><td>32,34</td><td>5,61</td><td>9,61</td><td>98,55</td><td>872,53</td><td>27,08</td><td>67,45</td><td>29,18</td><td>202,03</td><td>27,84</td><td>186,5</td><td>20,45</td><td>303,79</td><td>57,08</td><td>2,77</td></tr><tr><td>23s</td><td>56</td><td>2261,61</td><td>31,39</td><td>7,93</td><td>5,39</td><td>135,79</td><td>1143,43</td><td>13,62</td><td>63,86</td><td>51,39</td><td>383,14</td><td>32,18</td><td>250,04</td><td>28,29</td><td>407,36</td><td>92,54</td><td>3,19</td></tr></tbody></table>

## Légende

\#B/X = Nombre de bases comprises dans des sous-structures X

\#X = Nombre total de sous-structures X

\#B = Taille moyenne de la séquence

\#B PK = Nombre moyen de bases impliquées dans des pseudonoeuds

\#Remp/MB = Nombre moyen de remplissages par multiboucles

Où X a pour valeur :

E = Echelle R = Remplissage B = Boucle BI = Boucle Interne MB = MultiBoucle

<caption>Fig. D.1 : Statistique des sous-structures</caption>
E. APPLICATION SIMPLE DU THÉORÈME DE DRMOTA
> restart;

## Drmota "simple"

On utilise la restriction de la grammaire suivante à S, qui est une formulation alternative de la grammaire des structures secondaires d'ARN et on lui applique le résultat de Drmota sur les systèmes d'équations :

$$A ::= S | \varepsilon$$

$$S ::= a S b S \mid a S b \mid c S \mid c$$

> F := (z, S, x) -> z^2*S^2 + z^2*S + pi*x*z*S + pi*x*z;

$$F := (z, S, x) \rightarrow z^2 S^2 + z^2 S + \pi x z S + \pi x z$$

On a bien $F(0, S, x) = 0$ et $F(z, 0, x) \neq 0$.

De plus, la grammaire est fortement connexe, le système d'équations n'est pas linéaire, et la condition des cônes est respectée.

On doit cependant encore vérifier qu'il existe des solutions positives $S_0$ et $z_0$ à :

$$S = F(z, S, 1)$$

$$0 = 1 - \left(\frac{dF}{dS}\right)(z, S, 1)$$

> FS := unapply(diff(F(z,S,x),S),z,S,x);

$$FS := (z, S, x) \rightarrow 2z^2 S + z^2 + \pi x z$$

> eq1 := S = F(z, S, 1);

$$eq1 := S = z^2 S^2 + z^2 S + \pi z S + \pi z$$

> eq2 := 0 = 1 - FS(z, S, 1);

$$eq2 := 0 = 1 - 2z^2 S - z^2 - \pi z$$

> solve(eq1,S);

$$\frac{-z^2 - \pi z + 1 + \sqrt{z^4 - 2 z^3 \pi - 2 z^2 + \pi^2 z^2 - 2 \pi z + 1}}{2 z^2}, \\ \frac{-z^2 - \pi z + 1 - \sqrt{z^4 - 2 z^3 \pi - 2 z^2 + \pi^2 z^2 - 2 \pi z + 1}}{2 z^2}$$

On choisit la solution positive pour $S_0$.

> S[0] := %[2];

$$S_0 := \frac{-z^2 - \pi z + 1 - \sqrt{z^4 - 2 z^3 \pi - 2 z^2 + \pi^2 z^2 - 2 \pi z + 1}}{2 z^2}$$

> sol3 := solve(subs(S = S[0],eq2),z);

$$sol3 := \frac{\pi}{2} - 1 + \frac{\sqrt{\pi^2 - 4 \pi}}{2}, \quad \frac{\pi}{2} - 1 - \frac{\sqrt{\pi^2 - 4 \pi}}{2}, \quad \frac{\pi}{2} + 1 + \frac{\sqrt{\pi^2 + 4 \pi}}{2}, \quad \frac{\pi}{2} + 1 - \frac{\sqrt{\pi^2 + 4 \pi}}{2}$$

> z[0][1] := sol3[1];

$$z_{01} := \frac{\pi}{2} - 1 + \frac{\sqrt{\pi^2 - 4 \pi}}{2}$$
$$> z[0][2] := sol3[2];$$

$$z_{02} := \frac{\pi}{2} - 1 - \frac{\sqrt{\pi^2 - 4\pi}}{2}$$

$$> z[0][3] := sol3[3];$$

$$z_{03} := \frac{\pi}{2} + 1 + \frac{\sqrt{\pi^2 + 4\pi}}{2}$$

$$> z[0][4] := sol3[4];$$

$$z_{04} := \frac{\pi}{2} + 1 - \frac{\sqrt{\pi^2 + 4\pi}}{2}$$

Il existe une solution positive ($z_0, S_0$), $z_0$ restant à choisir ultérieurement entre $z_{03}$ et $z_{04}$ solutions réelles positives.

On a vérifié les conditions d'applications du théorème, on passe maintenant à son application :

$$> eq3:=S=F(z,S,x);$$

$$eq3 := S = z^2 S^2 + z^2 S + \pi x z S + \pi x z$$

$$> eq4:=0=1-FS(z,S,x);$$

$$eq4 := 0 = 1 - 2z^2 S - z^2 - \pi x z$$

$$> solve(eq3,S);$$

$$\frac{-z^2 - \pi x z + 1 + \sqrt{z^4 - 2 z^3 \pi x - 2 z^2 + \pi^2 x^2 z^2 - 2 \pi x z + 1}}{2 z^2},$$ $$\frac{-z^2 - \pi x z + 1 - \sqrt{z^4 - 2 z^3 \pi x - 2 z^2 + \pi^2 x^2 z^2 - 2 \pi x z + 1}}{2 z^2}$$

$$> S[1] := %[2];$$

$$S_1 := \frac{-z^2 - \pi x z + 1 - \sqrt{z^4 - 2 z^3 \pi x - 2 z^2 + \pi^2 x^2 z^2 - 2 \pi x z + 1}}{2 z^2}$$

$$> Sol1 := (solve(subs(S = S[1],eq4),z));$$

$$Sol1 := \frac{\pi x}{2} - 1 + \frac{\sqrt{\pi^2 x^2 - 4 \pi x}}{2}, \quad \frac{\pi x}{2} - 1 - \frac{\sqrt{\pi^2 x^2 - 4 \pi x}}{2}, \quad \frac{\pi x}{2} + 1 + \frac{\sqrt{\pi^2 x^2 + 4 \pi x}}{2},$$ $$\frac{\pi x}{2} + 1 - \frac{\sqrt{\pi^2 x^2 + 4 \pi x}}{2}$$

> k := 1:

evalf(subs(pi=k,x=1,-1*diff(Sol1[1],x)/z[0][1]));

evalf(subs(pi=k,x=1,-1*diff(Sol1[2],x)/z[0][2]));

evalf(subs(pi=k,x=1,-1*diff(Sol1[3],x)/z[0][3]));

evalf(subs(pi=k,x=1,-1*diff(Sol1[4],x)/z[0][4]),30);

$$-0.1533219187 \times 10^{-9} + 0.5773502691 I$$

$$-0.1533219187 \times 10^{-9} - 0.5773502691 I$$

$$-0.4472135955$$

$$0.447213595499957939281834733739$$

La solution 4 est la bonne solution, car elle est la seule qui donne une proportion (réel positif). De plus, on retombe sur un résultat de Nebel, qui arrive à 44 % de bases non appariées dans le cas uniforme (quand $\pi=1$).
> sol4 := simplify(subs(x=1,-1*diff(Sol1[4],x)/z[0][4]));

$$sol4 := \frac{\pi}{\sqrt{\pi(\pi + 4)}}$$

> eqfinale := mu = sol4;

$$eqfinale := \mu = \frac{\pi}{\sqrt{\pi(\pi + 4)}}$$

> sol := solve(eqfinale,pi);

$$sol := -\frac{4 \mu^2}{\mu^2 - 1}$$

> w := (mu)-> -4*mu^2/(mu^2-1);

$$w := \mu \rightarrow -\frac{4 \mu^2}{\mu^2 - 1}$$

Donc, pour avoir 75 % de bases non appariées, on doit pondérer les lettres c avec un poids :

> evalf(w(75/100));
5.142857143

Et pour 5 % de bases non appariées :

> evalf(w(5/100));
0.01002506266