```{r include=FALSE, echo=FALSE, eval=TRUE}
library(knitr)
options(width = 300)
knitr::opts_chunk$set(
  fig.width = 7, fig.height = 5, 
  fig.path = 'figures/02_combinatoire_',
  fig.align = "center", 
  size = "tiny", 
  echo = FALSE, eval = TRUE, 
  warning = FALSE, message = FALSE, 
  results = TRUE, comment = "")
# knitr::asis_output("\\footnotesize")

## Library used to draw flow charts
library(DiagrammeR)

```

# Dénombrements d'oligonucléotides et oligopeptides

## Problème: dénombrement d'oligomères

L'ADN est composé de 4 nucléotides distincts dénotés par les lettres A, C, G, T, et les protéines de 20 acides aminés. 

a. Pour chacun de ces deux types de polymères, combien d'oligomères distincts peut-on former en polymérisant 20 résidus ("20-mères") ?

    **Approche suggérée**: simplifiez le problème au maximum, en commençant par des polymères beaucoup plus courts (1 résidu, 2 résidus). 

b. Généralisez la formule pour les oligomères d'une longueur arbitraire $k$ (**"k-mères"**), en symbolisant par $n$ le nombre de résidus. 
c. Quel est le nom de la fonction donnant le résultat ?
d. Dans ce processus, quel est le mode de sélection des résidus: **avec ou sans remise** ?

## Solution: dénombrement d'oligomères

- Il s'agit d'un tirage avec remise: à chaque position de la séquence on a le choix entre $n$ résidus (4 pour les acides nucléiques, 20 pour les protéines).

- Approche progressive de la solution

    - Cas trivial: séquence d'un seul résidu $\rightarrow$ le nombre de possibilités est $n$. 
    - Pour chacune des $n$ possibilités de premier résidu, il y a $n$ possibilités pour choisir le second résidu $\rightarrow$ il existe $n \cdot n = n^2$ séquences de taille 2. 
    - Pour chacune d'entre elles, $n$ résidus possibles en $3^{ème}$ position $\rightarrow$ il existe $n^2 \cdot n = n^3$ séquences distinctes de taille 3.
    
- Généralisation: il existe $n^k$ séquences distinctes de taille $k$.

- Dans notre cas, la taille des séquences $k=20$. On a donc 

    - $N = n^k = 4^{20} = `r signif(digits=3, 4^20)`$ oligonucléotides distincts 
    - $N = n^k = 20^{20} = `r signif(digits=3, 20^20)`$ oligopeptides distincts 

- Il s'agit d'une **suite géométrique**.

## La suite géométrique

Une **suite géométrique** est une succession de nombres dont chaque terme est obtenu en multipliant le terme précédent par un facteur constant. 

$$x_i = x_{i-1} \cdot n$$

Pour $k$ suffisamment grand on peut développer la formule.

$$\begin{aligned}
x_k &=  x_{k-1} \cdot n \\
&=  (x_{k-2} \cdot n) \cdot n = x_{k-2} \cdot n^2 \\
&=  x_{k-3} \cdot n^3 = \ldots = x_0 \cdot n^k 
\end{aligned}$$

Dans notre cas, la valeur initiale $x_0=1$;  $k$ est la taille de l'oligomère;  et $n$ est le nombre de résidus ($n=4$ pour les acides nucléiques, $n=20$ pour les séquences peptidiques).


## Nonmbre d'oligomères



```{r number_distinct_oligos, out.width = "60%", fig.width=8, fig.height=6, echo=FALSE, fig.cap="Nombre d'oligonucléotides (dessus) ou d'oligopeptides (dessous), en utilisant une échelle soit linéaire (gauche) soit logarithmique (droite) pour l'ordonnée."}
x <- 1:20 ## Oligomer size

par.ori <- par(no.readonly = TRUE)
par(mfrow = c(2,2))
n <- 4 ## Number of distinct residues
N <- n^x
plot(x, N, 
     main = "Number of distinct oligonucleotides",
     xlab = "Oligomer size",
     ylab = "N",
     las = 1, cex.axis = 0.8,
     type = "h", lwd = 3, col = "blue"
)
plot(x, N, 
     main = "Number of distinct oligonucleotides",
     xlab = "Oligomer size",
     ylab = "N (log scale)",
     las = 1, cex.axis = 0.8,
     log = "y",
     type = "p", pch = 19, col = "blue"
     )

## Oliopeptides
n <- 20 ## Number of distinct residues
N <- n^x
plot(x, N, 
     main = "Number of distinct oligopeptides",
     xlab = "Oligomer size",
     ylab = "N",
     las = 1, cex.axis = 0.8,
     type = "h", lwd = 3, col = "blue"
)
plot(x, N, 
     main = "Number of distinct oligopeptides",
     xlab = "Oligomer size",
     ylab = "N (log scale)",
     las = 1, cex.axis = 0.8,
     log = "y",
     type = "p", pch = 19, col = "blue"
)

par(par.ori) ## restore default parameters
```



## Exercice 02.1: oligomères sans résidus répétés

Combien d'oligomères peut-on former (ADN ou peptides) en utilisant chaque résidu une et une seule fois ?

**Approche suggérée**: agrégez progressivement les résidus, en vous demandant à chaque étape combien d'entre eux n'ont pas encore été incorporés. 

**Questions subsidiaires**:

- Généralisez la formule pour des séquences d'objets tirés dans un ensemble de taille arbitraire ($n$). 
- Quel est le nom de la fonction donnant le résultat ?
- Dans ce processus, quel est le mode de sélection des résidus: **avec ou sans remise** ?

## Solution: oligomères sans résidus répétés

- Premier résidu: $n$ possibilités. 
- Dès le moment où on a choisi ce premier résidu, il ne reste plus que $n-1$ possibilités pour le second. On a donc $n \cdot (n-1)$ possibilités pour les deux premiers résidus. 
- Pour la troisième position, il ne reste que $n-2$ résidus. On a donc $n \cdot (n-1) \cdot (n-2)$ possibilités pour les 3 premières positions de la séquence.
- Par extension, le nombre total de possibilités est donc (en supposant $n$ suffisamment grand) 

$$n! = n \cdot (n-1) \cdot \ldots \cdot 2 \cdot 1$$

- Dans notre cas:

    - $n! = 4! = `r signif(digits=3, factorial(4))`$ oligonucléotides comportant exactement 1 fois chaque nucléotide (taille 4).
    - $n! = 20! = `r signif(digits=3, factorial(20))`$ oligopeptides (taille 20).
    
## La factorielle

- S'applique pour dénombrer les permutations d'un ensemble.
- Il s'agit de tirages sans remise.
- Définie par une formule récursive.

$$N = n! = \left\{
                \begin{array}{ll}
                  1 & \text{if } n=0 \\
                  n \cdot (n-1)! &\text{otherwise}
                \end{array}
              \right.$$

Note: $0! = 1$, par définition, ce qui permet de calculer $1!$ et les factorielles des nombres subséquents avec la formule récursive. 

Pour $n$ suffisamment grand cela donne en clair.

$$N = n \cdot (n-1) \cdot (n-2) \ldots 2 \cdot 1$$

## Factorielle

```{r factorial, out.width = "95%", echo=FALSE, fig.width=10, fig.height=4}
n <- 1:20
N <- factorial(n)
# plot(n,N, log = "y")

par.ori <- par(no.readonly = TRUE)
par(mfrow = c(1,2))
plot(n, N, 
     main = "Factorielle",
     xlab = "n",
     ylab = "N",
     las = 2, cex.axis = 0.8,
     type = "h", lwd = 3, col = "blue"
)
plot(n, N, 
     main = "Factorielle\n(échelle Y logarithmique)",
     xlab = "n",
     ylab = "N (log scale)",
     las = 2, cex.axis = 0.8,
     log = "y",
     type = "p", pch = 19, col = "blue"
     )
par(par.ori)
```



## Exercice 02.2 : listes (ordonnées) de gènes

On a mené une expérience de transcriptome pour mesurer le niveau d'expression de tous les gènes de la levure. Sachant que le génome comporte 6000 gènes, combien de possibilité existe-t-il pour sélectionner les 15 gènes les plus fortement exprimés (**en tenant compte** de l'ordre relatif de ces 15 gènes) ?

**Approche suggérée**: comme précédemment, simplifiez le problème en partant de la sélection minimale, et augmentez progressivement le nombre de gènes sélectionnés (1 gène, 2 gènes, ...). 

**Questions subsidiaires**: 

- Trouvez un exemple familier de jeu de pari apparenté à ce problème. 
- Généralisez la formule pour la sélection d'une liste de $x$ gènes dans un génome qui en comporte $n$. 

## Solution 02.2 : listes (ordonnées) de gènes

Il s'agit d'une sélection **sans remise** (chaque gène apparaît à une et une seule position dans la liste de tous les gènes), et **ordonnée** (les  mêmes gènes pris dans un ordre différent sont considérés comme un résultat différent).

- Pour le premier gène, il y a $n=6000$ possibiité.
- Dès le moment où on connaît le premier gène, il n'existe plus que 5999 possibilités pour le second, et donc $n \cdot (n-1) = 6000 \cdot 5999$ possibilités pour la suite des deux premiers gènes; 
- Par extension, il existe $6000 \cdot 5999 \cdot 5998 \cdot \ldots \cdot 5986 = `r signif(digits=3, prod(6000 - (0:14)))`$ possibilités pour les 15 premiers gènes. 
- En généralisant à la liste des $x$ premiers gènes dans un ensemble de $n$, on obtient $N = n \cdot (n-1)  \cdot (n-2) \cdot ... \cdot (n-x+1)$. 


## Exercice 02.3 : ensembles (non-ordonnés) de gènes

Ona a réalisé une expérience de transcriptome indiquant le niveau d'expression de tous les gènes de la levure. Sachant que le génome comporte 6000 gènes, combien de possibilité existe-t-il pour sélectionner les 15 gènes les plus fortement exprimés (**sans tenir compte** de l'ordre relatif de ces 15 gènes) ?

**Approche suggérée**: comme précédemment, simplifiez le problème en partant de sélections minimales (1 gène, 2 gènes, ...) et généralisez la formule. 

**Questions subsidiaires**: 

- Trouvez un exemple familier de jeu de pari apparenté à ce problème. 
- Généralisez la formule pour la sélection d'un ensemble de $x$ gènes dans un génome qui en comporte $n$. 
- Connaissez-vous le nom de la formule ainsi trouvée ?


## Solution 02.3 : ensembles (non-ordonnés) de gènes

- Pour une sélection d'un seul gène, il existe $n=6000$ possibilité. 
- Pour 2 gènes, il existe $n \cdot (n-1) = 6000 \cdot 5999$ arrangements, mais ceci inclut deux fois chaque paire de gènes ($(a, b)$ et $(b, a)$). Le nombre d'ensembles non ordonnés est donc $N = n \dot (n-1)/2$.
- De même, pour 3 gènes, il faut diviser le nombre d'arrangements ($A^x_n = \frac{n!}{(n-x)!} = 6000 \cdot 5999 \cdot 5998$) par le nombre de permutations parmi tous les triplets de gènes ($(a, b, c), (a, c, b), (b, a, c) \ldots$), ce qui donne $\frac{6000!}{(6000-3)! 3!} = \frac{6000 \cdot 5999 \cdot 5888}{6} = `r signif(digits=3, choose(6000,3))`$.
- Pour 15 gènes, on obtient $\frac{n!}{(n-x)!x!} = \frac{6000!}{5985! \cdot 15!} = `r signif(digits=3, choose(6000, 15))`$ *combinaisons* possibles.


## Eléments de combinatoire

Nous résumons ici les formules les plus utilisées en analyse combinatoire. 

- Arrangements (tirages ordonnés sans remise)
- Combinaisons (tirages non-ordonnés sans remise)

## Arrangements

On appelle **arrangements** les tirages *ordonnés* effectués *sans remise* au sein d'un ensemble. 

Nombre d'arrangements de $x$ éléments tirés parmi $n$. 

$$\begin{array}{ccl}
A^x_n & = & \frac{n!}{(n - x)!} \\
 & = & \frac{n(n-1) \ldots (n-x +1) (n - x) (n-x-1) \ldots 2 \cdot 1}{(n - x) (n-x-1) \ldots 2 \cdot 1} \\
& = & n \cdot (n-1) \cdot \ldots \cdot (n-x+1)
\end{array}
$$

## Arrangements: typical application

- [**tiercé dans l'ordre**](https://fr.wikipedia.org/wiki/Tierc%C3%A9_(jeu))**. 

- Les joueurs parient sur les trois chevaux gagnants d'une course ($x=3$). Pour $n=15$ chevaux partants, il existe $n \cdot (n-1) \cdot (n-2) = 15 \cdot 14 \cdot 13 = `r 15*14*13`$ possibilités. 

## Combinaisons

On appelle **combinaisons** le nombre de sous-ensembles de $x$ qu'on peut  tirer *sans remise* dans un ensemble de taille $n$,  si l'on ne tient pas de l'ordre des éléments tirés. 

Ce nombre est fourni par le **coefficient binomial**.

$$\binom{n}{x} = C^x_n = \frac{n!}{x! (n-x)!}$$


**Attention: ** les paramètres sont placés différemment dans la première  ($binom{n}{x}$, "x parmi n") et la seconde notation ($C^x_n$, "choose").

## Combinaisons -- Applications typiques

- **[tiercé](https://fr.wikipedia.org/wiki/Tierc%C3%A9_(jeu))** dans le désordre.

    $$\binom{n}{x} = \binom{15}{3} = C^3_{15} = \frac{15!}{3! 12!} = `r choose(n=15, k=3)`$$

- jeu de **[loto](https://fr.wikipedia.org/wiki/Loto)** (ou lotto): chaque joueur dispose d'une grille avec 90 numéros, et doit en cocher 6. Nombre de possibilités: 
    $$\binom{n}{x} = \binom{90}{6} = C^6_{90} = \frac{90!}{6! 84!} = `r choose(n=90, k=6)`$$



# Résumé des concepts et formules

## Tirages avec / sans remise

Il existe deux types classiques de tirage d'éléments au sein d'un ensemble: avec ou sans remise. 

1. **Tirage sans remise**: chaque élément peut être tiré au plus une fois. Exemples: 

    - Jeu de [loto](https://fr.wikipedia.org/wiki/Loto) (ou lotto). 
    - Sélection aléatoire d'un ensemble de gènes dans un génome. 

2. Tirage **avec remise**: chaque élément peut être tiré zéro, une ou plusieurs fois. Exemples: 

    - Jeu de dés. A chaque lancer on dispose des mêmes possibilités (6 faces).
    - Génération d'une séquence aléatoire, par sélection itérative d'un élément dans l'ensemble des résidus (4 nucléotides pour l'ADN, 20 acides aminés pour les protéines). 
    
## Choix de la formule

```{r combinatorics_flowchart, out.width = "90%", fig.width = 8, fig.height = 5}

grViz("
digraph combinatorics_flowchart {
  node [shape = diamond, fontname = Helvetica ]
  node [fontcolor = 'orange']
  A [label = 'remise ?']; 
  B [label = 'ordonné ?'];
  D [label = 'ordonné ?']  
  G [label = 'sélection\nexhaustive ?']

  node [shape = 'rectangle', fontcolor = 'black']
  C [label = 'suite\ngéométrique'];
  E [label = 'arrangement']
  F [label = 'combinaison']
  H [label = 'factorielle']

  edge [arrowhead  = 'normal', color = '#00BB00', fontcolor = '#00BB00', label = 'oui']
  A -> B
  B -> C
  D -> G
  G -> H

  edge [arrowhead  = 'normal', color = '#BB0000', fontcolor = '#BB0000', label = 'non']
  A -> D
  D -> F
  G -> E

}
")

```


## Formules

| Remise | Ordre | Formule | Description |
|--------|-------|------------|---------------------------------|
| Oui | Oui | $n^x$ | **Suite géométrique**: tirages ordonnés (séquences), avec remise, de $x$ éléments dans un ensemble de taille $n$. |
| Non | Oui | $n!$ | **Factorielle**: permutations d'un ensemble de taille $n$ |
| Non | Oui | $A^x_n = \frac{n!}{(n-x)!}$ | **Arrangements** : tirages ordonnés, sans remise, de $x$ éléments dans un ensemble de taille $n$ |
| Non | Non | $C^x_n = \binom{n}{x} = \frac{n!}{x! (n - x) !}$ | **Combinaisons** : tirages non ordonnés, sans remise, de $x$ éléments dans un ensemble de taille $n$ |


# Exercices supplémentaires



## Exercice 02.5: oligopeptides $3 \times 20$

*Combien d'oligopeptides de taille 60 peut-on former en utilisant exactement 3 fois chaque acide aminé ?*


## Solution 02.5 : oligopeptides $3 \times 20$

*Combien d'oligopeptides de taille 60 peut-on former en utilisant exactement 3 fois chaque acide aminé ?*

Commençons par générer une séquence particulière qui remplit ces conditions, en concaténant 3 copies de chaque acide aminé, dans l'ordre alphabétique. 

```{r echo=FALSE}
aa.table <- read.delim("amino_acid_table.tsv", sep = "\t")
# kable(aa.table, caption = "Symboles des acides aminés et codons")

aa <- sort(as.vector(aa.table$Symbol))
aa <- aa[aa %in% LETTERS]

cat(sort(rep(aa, times=3)), sep = "")
```

Toutes les permutations de ces 60 lettres sont des solutions valides. En voici trois exemples. 

```{r echo=FALSE}
cat(sample(rep(aa, times = 3)), sep = "")
cat(sample(rep(aa, times = 3)), sep = "")
cat(sample(rep(aa, times = 3)), sep = "")
```


Cependant, il faut prendre en compte le fait que certaines permutations sont identiques (toutes celles où l'on permute deux acides aminés identiques). La difficulté de l'exercice sera donc de dénombrer le nombre de permutations *distinctes*. 

