Centrale Informatique MP-PC-PSI 2019

Thème de l'épreuve Élasticité d'un brin d'ADN
Principaux outils utilisés librairie numpy, listes, probabilités
Mots clefs brin d'ADN, modèle du ver, chaine, Monte Carlo

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                             

Rapport du jury

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


Informatique
MP, PC, PSI, TSI

3 heures Calculatrice autorisée

Élasticité d'un brin d'ADN

La capacité des molécules d'ADN à participer à des mécanismes de réplication et 
de transcription ainsi qu'à
s'organiser en chromosomes doit beaucoup à leur élasticité. Ainsi, l'étude de 
la réaction d'une molécule d'ADN
aux contraintes mécaniques permet d'éclairer les processus biologiques mis en 
oeuvre dans une cellule vivante.

2019

À l'aide d'une expérience et de deux modèles mécaniques d'un brin d'ADN, ce 
sujet propose de caractériser
l'élasticité de l'ADN. Pour cela, on suppose qu'on exerce une traction sur un 
brin d'ADN et on cherche à établir
une relation entre la force utilisée et l'allongement de la molécule.

Le seul langage de programmation autorisé dans cette épreuve est Python. Pour 
répondre à une question, il est
possible de faire appel aux fonctions définies dans les questions précédentes. 
Dans tout le sujet on suppose que
les bibliothèques math, numpy et random ont été importées grâce aux instructions

import math
import numpy as np
import random

Si les candidats font appel à des fonctions d'autres bibliothèques, ils doivent 
préciser les instructions d'importa-
tion correspondantes.
Ce sujet utilise la syntaxe des annotations pour préciser le type des arguments 
et du résultat des fonctions à
écrire. Ainsi

def maFonction(n:int, X:[float]l, c:str, u) -> (int, np.ndarray):
signifie que la fonction maFonction prend quatre arguments, le premier (n) est 
un entier, le deuxième (X) une
liste de nombres à virgule flottante, le troisième (c) une chaine de caractères 
et le type du dernier (u) n'est
pas précisé. Cette fonction renvoie un couple dont le premier élément est un 
entier et le deuxième un tableau
numpy. Il n'est pas demandé aux candidats de recopier les entêtes avec 
annotations telles qu'elles sont fournies
dans ce sujet, ils peuvent utiliser des entêtes classiques. Ils veilleront 
cependant à décrire précisément le rôle des
fonctions qu'ils définiraient eux-mêmes.
Dans ce sujet, le terme « liste » appliqué à un objet Python signifie qu'il 
s'agit d'une variable de type list.
Les termes « vecteur » et « tableau » désignent des objets numpy de type 
np.ndarray, respectivement à une
dimension ou de dimension quelconque. Enfin le terme « séquence » représente 
une suite itérable et indiçable,
indépendamment de son type Python, ainsi un tuple d'entiers, une liste 
d'entiers et un vecteur d'entiers sont
tous trois des « séquences d'entiers ».
Une attention particulière sera portée à la lisibilité, la simplicité et 
l'efficacité du code proposé. En particulier,
l'utilisation d'identifiants significatifs, l'emploi judicieux de commentaires 
et la description du principe de chaque
programme seront appréciés.

Une liste de fonctions utiles est fournie à la fin du sujet.

I Fonctions utilitaires

Cette partie définit quelques fonctions qui pourront avantageusement être 
utilisées dans la suite du sujet.
Q 1. Écrire une fonction d'entête
def moyenne(X) -> float:

qui prend en paramètre une séquence de nombres et qui calcule la moyenne de ces 
nombres. Cette fonction ne
doit pas modifier le paramètre X.

Par exemple : moyenne([1, 2, 3, 4]) -> 2.5

2019-03-21 14:31:49 Page 1/10 CHEXTELS
Q 2. Écrire une fonction d'entête
def variance(X) -> float:

qui calcule la variance d'une séquence de nombres, sans la modifier. Pour 
rappel, la variance des n nombres
T1, ...., æ, est la moyenne des carrés des écarts à la moyenne, c'est-à-dire
1: nm Y Y ;

Tè T Tè
_S (x 22 x° -- T° avec 5225 x
ri " I

i=1
Par exemple : variance([1, 2, 3, 4]) -> 1.25
Q 3. Écrire une fonction d'entête

def somme (M):

qui prend en paramètre une séquence imbriquée, de profondeur et de structure 
quelconques, dont tous les
composants élémentaires sont des nombres, et calcule la somme de tous ces 
éléments.

Par exemple : somme([[[1, 21, [3, 4, 51], 6, [7, 8], 91) -> 45

Indication -- L'expression booléenne isinstance(x, numbers.Real) permet de 
tester si x est un scalaire
numérique. Par exemple

isinstance(1, numbers.Real) -> True
isinstance(2.3e4, numbers.Real) -> True
isinstance([1, 2, 3], numbers.Real) -> False

IT Mesures expérimentales

Depuis quelques décennies, des équipes de recherche réussissent à isoler un 
brin d'ADN et à mesurer ses propriétés
mécaniques. Cette partie s'appuie sur une série d'expériences réalisées dans 
les années 1990, en particulier au
laboratoire de physique statistique de l'Ecole Normale Supérieure.

Une molécule d'ADN est attachée à une de ses extrémités sur un support 
transparent, une microbille magnétique
de diamètre 2,5 um est greffée à son autre extrémité. À l'aide d'aimants, la 
molécule d'ADN est soumise à une
force de traction notée F. Afin de caractériser l'élasticité du brin d'ADN, on 
cherche à mesurer son allongement
pour différentes intensités de la force de traction.

L'intensité de la force de traction n'est pas accessible directement, nous 
allons l'évaluer indirectement. Une fois
le brin d'ADN mis en tension, son extrémité matérialisée par la bille ne reste 
pas immobile, elle est animée d'un
mouvement aléatoire, dit mouvement brownien, dû à l'agitation des molécules du 
liquide qui l'entourent. En assi-
milant la molécule à un ressort, on montre que l'intensité de la force de 
traction est inversement proportionnelle
aux fluctuations quadratiques moyennes de la position de la bille.

Une caméra CCD reliée à un ordinateur permet de photographier l'image de la 
bille (figure 1). Compte tenu de
la taille de cette bille, on obtient une image de diffraction que nous allons 
analyser pour déterminer la position

de la bille.

LUN TS jaimant

£ EEE +4
y bille magnétique récipient
brin d'ADN transparent
objectif
x IOÙ

caméra CCD

Figure 1 Schéma du dispositif expérimental (échelle non respectée)

IT. À --- Position de la bille

La figure 2 donne, à gauche, un exemple d'image obtenue par la caméra CCD. 
Cette caméra est pilotée par
un programme Python qui récupère chaque image sous la forme d'un tableau 
d'entiers à deux dimensions. Les
images obtenues sont en niveau de gris, chaque pixel est codé sur 8 bits, soit 
une valeur comprise entre 0 (noir)
et 255 (blanc).

2019-03-21 14:31:49 Page 2/10 (C)EATETSS
Afin de repérer le centre de la figure de diffraction, l'image est convertie en 
noir et blanc inversé suivant une
valeur seuil du niveau de gris : les pixels au-dessus du seuil deviennent 
noirs, ceux en dessous deviennent blancs.
Une fois ce seuillage effectué, on calcule le barycentre des pixels blancs de 
l'image seuillée pour obtenir la position

de la bille.

On rappelle que l'abscisse (respectivement ordonnée) du barycentre d'un 
ensemble de points de même poids est
la moyenne des abscisses (respectivement ordonnées) des points considérés.

? À Fran
ä me

seuillage

Figure 2 Figure de diffraction d'une bille et opération de seuillage

Q 4. Écrire une fonction d'entête
def seuillage(A:np.ndarray, seuil:int) -> np.ndarray:

qui prend en paramètre un tableau d'entiers à deux dimensions représentant un 
cliché de la caméra CCD et
construit un tableau de même forme contenant la valeur 1 là où la valeur des 
pixels de l'image originale est
strictement inférieure au seuil et la valeur 0 ailleurs (pixels supérieurs ou 
égaux au seuil).

Q 5. Écrire une fonction d'entête
def pixel centre bille(A:np.ndarray) -> (int, int):

qui prend en paramètre l'image seuillée telle que produite par la fonction 
seuillage et renvoie les indices (ligne
et colonne) du pixel le plus proche du centre de la bille (barycentre des 
pixels à 1).

On dispose de la fonction d'entête
def prendre_photo() -> np.ndarray:

qui déclenche la prise d'un cliché par la caméra CCD et renvoie l'image prise 
sous la forme d'un tableau à deux
dimensions tel que décrit plus haut.

Q 6. Écrire une fonction d'entête

def positions(n:int, seuil:int) -> [(int, int)l:
qui prend n photographies de la bille et renvoie la liste de ses positions dans 
chaque photographie en seuillant
les images à la valeur seuil. Le résultat de cette fonction est donc une liste 
de n couples de deux entiers

correspondants à l'indice de ligne et de colonne des positions successives du 
centre de la bille au cours de son
mouvement brownien.

Le capteur CCD est positionné parallèlement au plan (xOy) et ses pixels sont 
carrés. La caméra a été calibrée
dans les conditions de l'expérience : un pixel correspond à un carré du plan 
(xOy) de côté t.

Q 7. Définir une fonction d'entête
def fluctuations(P:[(int, int)], t:float) -> float:

qui prend en paramètre une liste de positions successives de la bille (telle 
que produite par la fonction positions)
et la longueur correspondant à un pixel et calcule la valeur moyenne des 
déplacements quadratiques de la bille :
moyenne des carrés des écarts entre chaque position mesurée et la position 
d'équilibre de la bille (correspondant
au barycentre des différentes positions observées).

2019-03-21 14:31:49 Page 3/10 (C)EATETSS
II.B -- Allongement du brin d'ADN

La position de la bille étant déterminée dans le plan (xOy), nous allons 
maïntenant nous intéresser à sa cote,
c'est-à-dire sa position dans la direction perpendiculaire à la caméra.

Pour déterminer la position de la bille suivant 2, nous utilisons une méthode 
basée sur la répartition des cercles
de la figure de diffraction. Pour cela, nous construisons un profil de cette 
figure en découpant l'image seuillée
en anneaux concentriques centrés sur la position de la bille. Le décompte de la 
proportion de pixels blancs dans
chaque anneau fournit un profil de la figure de diffraction qui permet de 
calculer la cote z de la bille en tenant
compte des paramètres de calibration de la caméra.

De 4 |
Position de la bille

NE /

Figure 3 Exemple de découpage d'une image en cinq an-
neaux concentriques

Q 8. Écrire une fonction d'entête

def profil(A:np.ndarray, n'int):
qui construit le profil d'une figure de diffraction seuillée À en la découpant 
en n anneaux concentriques. Cette
fonction renvoie, au choix du candidat, un vecteur ou une liste de n nombres, 
compris entre 0 et 1, qui donne
la proportion de pixels blancs compris dans chaque anneau. Un pixel sera 
considéré comme contenu dans un
anneau si son centre s'y trouve. L'élément d'indice 0 du résultat correspond à 
la bande la plus proche du centre
de la figure (position de la bille).

Afin de clarifier l'écriture du code, il peut être pertinent de définir des 
fonctions intermédiaires pour programmer
la fonction profil. Les candidats veilleront à expliquer précisément le rôle de 
chaque fonction intermédiaire
qu'ils définiraient.

Q 9. Si on travaille sur une image carrée de dimension p x p pixels, quelle est 
la complexité de la fonction
profil en fonction de p et de n (nombre d'anneaux) ?

II.C -- Synthèse

Pour une configuration expérimentale donnée, il est ainsi possible en prenant 
une série de clichés de déterminer
l'amplitude du mouvement brownien de l'extrémité du brin d'ADN ainsi que sa 
position en trois dimensions.
Ces éléments permettent alors de déterminer l'intensité de la force de traction 
appliquée au brin d'ADN ainsi
que son allongement.

En modifiant les aimants, on peut faire varier l'intensité du champ magnétique 
et donc la force appliquée au
brin d'ADN. En renouvelant l'expérience, on obtient ainsi une série de points 
expérimentaux correspondant à
diverses valeurs de force et d'allongement.

III Modèle du ver

Le « modèle du ver » est un modèle souvent utilisé pour décrire le comportement 
mécanique de certains poly-
mères. Dans ce modèle, la molécule étudiée est représentée par une succession 
de segments semi-rigides orientés
grossièrement dans la même direction. Il permet d'obtenir une expression 
simplifiée de F, l'intensité de la force
de traction F en fonction de z, l'allongement de la molécule :

ke2T 1 1 Z
F(z) = Ts or LYS + =) (IIL.1)

où k est la constante de Boltzman et T° la température. Ce modèle est paramétré 
par deux longueurs :

-- L,, longueur de persistance représentant la longueur typique sur laquelle le 
polymère maintient sa forme
malgré les déformations dues à l'agitation thermique ;

-- L,, extension maximale du polymère.

2019-03-21 14:31:49 Page 4/10 (C)EATETSS
ITT. A -- Calcul des paramètres

Ces deux grandeurs ne sont pas accessibles directement pour une molécule d'ADN. 
L'objectif de cette partie
est de déterminer les valeurs de L, et L, correspondant au brin d'ADN objet des 
mesures développées dans la
partie précédente.

Pour cela nous utilisons la fonction curve_fit du package scipy.optimize qui 
permet d'ajuster les paramètres
d'une courbe afin qu'elle passe au plus proche d'un certain nombre de points. 
La fonction curve_fit utilise
pour cela une méthode de moindres carrés non linéaire. Une adaptation de la 
documentation de cette fonction
est fournie par la figure 4.

popt, pcov = scipy.optimize.curve_ fit(f, xdata, ydata)

Paramètres

-- f: callable
La fonction modèle, f(x, ...). Elle doit prendre la variable indépendante comme 
premier argument
et chaque paramètre à ajuster comme argument suivant.

-- xdata : séquence de longueur M
La liste des valeurs de la variable indépendante correspondant aux différentes 
mesures.

-- ydata : séquence de longueur M
Les mesures, typiquement f(xdata, ...).

Résultat

-- popt : tableau
Valeurs optimales des paramètres telles que la somme des carrés des écarts 
f(xdata, *popt) - ydata
soit minimale.

-- pcov : tableau à deux dimensions
Une estimation de la covariance de popt. Les termes diagonaux donnent la 
variance de l'estimateur du
paramètre correspondant.
Pour estimer l'écart-type de l'erreur sur les paramètres, on peut utiliser perr 
= np.sqrt(np.diag(pcov))

Figure 4 Extrait adapté de la documentatin de curve_fit

Q 10. Écrire une fonction d'entête
def force(z:np.ndarray, Lp:float, LO:float, T:float) -> np.ndarray:

qui calcule la force donnée par la formule (IIL.1) pour chaque élément du 
vecteur z. Cette fonction renvoie un
vecteur de même taille que z contenant le résultat du calcul pour chaque 
composante de z. La variable globale
K_B fournit la valeur de la constante de Boltzman.

On dispose d'une série de points expérimentaux issus d'essais réalisés suivant 
les modalités décrites dans le IL.C.
Ces valeurs expérimentales sont stockées dans un tableau à deux dimensions. 
Chaque ligne (première dimension)
contient le résultat d'une mesure, la première colonne donne la valeur obtenue 
pour la force et la deuxième celle
de l'allongement.

Q 11. Écrire une fonction d'entête
def ajusteWLC(Fz:np.ndarray, T:float) -> (float, float):

qui ajuste les paramètres de la formule (IIL.1) pour qu'ils correspondent au 
micux aux valeurs expérimentales
du tableau Fz obtenues par une série d'essais effectués à la température T. 
Cette fonction renvoie un couple de
nombres donnant les valeurs optimales de L,, et de L,;,.

ITI.B -- Algorithme de minimum local

La fonction curve_fit permet d'utiliser différents algorithmes d'optimisation. 
Nous allons jeter les bases d'un
algorithme permettant d'obtenir les valeurs optimales L, et L,,.

III.B.1) Implantation d'un algorithme de minimisation 1D

Soit @ une fonction de classe C°? sur R présentant un minimum local.

On rappelle que

b(x(1+h)) --o(x(1--h))
24h

(IIL.2)

est une expression approchée d'ordre 2 de la dérivée de @ en x (notée d'(x)).

2019-03-21 14:31:49 Page 5/10 (C)EATETSS
On suppose que l'ordinateur utilisé représente les nombres flottants sur 64 
bits avec un bit de signe, 11 bits
d'exposant et 52 bits de mantisse.

Q 12. Calculer le nombre de chiffres significatifs décimaux donnés par ce 
codage.

Q 13.  Justifier que les valeurs À = 1 et h = 107$ ne permettent pas obtenir 
une bonne approximation du
nombre dérivé D'(x). Proposer alors une valeur adaptée de }.

Q 14. Écrire une fonction d'entête
def derive(phi, x:float, h:float) -> float:

qui calcule une valeur approchée de la dérivée au point x de phi, fonction 
réelle d'une variable réelle, où h
correspond au À de la formule (IIL.2).

Q 15. Écrire une fonction d'entête

def derive_seconde(phi, x:float, h:float) -> float:
permettant d'obtenir une approximation de la dérivée seconde de la fonction phi 
au point x.
Q 16. Écrire une fonction d'entête

def min _local(phi, x0:float, h:float) -> float:

basée sur la méthode de Newton permettant de trouver l'abscisse d'un minimum 
local de la fonction phi. La
valeur approchée de cette abscisse vérifiera [D'(x)| < 1077. III.B.2) Implantation d'un algorithme de minimisation 2D L'écart quadratique entre les valeurs expérimentales de la force F; correspondant à l'élongation z, et les valeurs de la fonction force est défini par E(L,, L;) -- DE EE force(z;, L,, Lo, T)) D Les valeurs optimales de L, et L, correspondent au minimum de la fonction £, c'est-à-dire à un point où son gradient est nul. Pour déterminer le point (%,,,y,,) correspondant au minimum de la fonction Æ, nous allons adapter la méthode de Newton unidimensionnelle pour rechercher un zéro d'une fonction de deux variables puis appliquer cette méthode au gradient de FE. On considère G une fonction réelle de deux variables réelles x, y de classe C? sur R?, présentant un minimum 0G 0G local. On note g, = ---- et g, -- Du les composantes du gradient de la fonction G. On rappelle que y OX 0g. 0g, a(T:Y) = (Lo: Yo) + D (Po Yo)(x -- Lo) + D (0 Yo) -- Yo) + O(X -- Lo, Y -- Yo) 0g, 0g, 9x; Y) = (Lo: Yo) + D Co Yo)(E -- Xo) + 24 Yo)(Y -- Yo) + O(X -- Lo, y -- Yo) L'objectif est d'approcher les valeurs %,,, y,, qui annulent les fonctions g, et g, et correspondent donc à un extremum de la fonction G, en partant d'un point arbitraire (x, Yo). Q 17. Montrer que les coordonnées (x,,y,,0) du point situé à l'intersection des plans -- tangent à la surface z = g,(x, y) au point (x, Yo: 9: (T0: Vo)). -- tangent à la surface z = CAE y) au point (to: Yo: 9 (Lo: Yo)): -- d'équation z = 0, vérifient la relation suivante où on explicitera l'expression de J(x9, Yo) : en) Je) Si la matrice J est inversible, en s'inspirant de la méthode de Newton, on construit une relation de récurrence sous la forme : ju] _ (ir) _ J | T (ren) -- : U | Un+1 Un " n) 9(Ln Un) Nous allons utiliser cette relation pour recherche le minimum local d'une fonction réelle de deux variables réelles implantée en Python sous la forme d'une fonction prenant en paramètre une séquence de deux nombres. Par exemple def fct_dont_je_veux_le minimum(X:np.ndarray) -> float:

2019-03-21 14:31:49 Page 6/10 (C)EATETSS
Q 18. Écrire une fonction d'entête
def grad(G, X:np.ndarray, h:float) -> np.ndarray:

qui fournit une approximation de la valeur du gradient de la fonction réelle de 
deux variables réelles G au point
X (= (x,y)) en utilisant h comme paramètre pour le calcul approché des 
dérivées, voir formule (IIL.2).

Q 19. Écrire une fonction d'entête
def min_local_2D(G, XO0:np.ndarray, h:float) -> np.ndarray:

permettant d'obtenir une approximation numérique des valeurs de x,, et y,, 
correspondant à un minimum local
de la fonction G en partant du point XO (= (x9,Yo)) et en utilisant h comme 
paramètre pour le calcul approché
des dérivées. La valeur approchée du minimum local vérifiera |g, (x, y)| < 1077 et [g, (x, y)| < 1077. IV Modèle de la chaine librement jointe La molécule d'ADN peut également être représentée par le modèle de la « chaïne librement jointe » dans la- quelle des segments rigides (appelés monomères) sont liés à leurs extrémités et librement orientables aux points de jointure. On appelle conformation de la molécule sa configuration géométrique. En l'absence d'action exté- ricure, l'orientation de chaque segment par rapport à ses voisins est aléatoire et toutes les conformations sont équiprobables. Ce modèle supposant une part d'aléa, il n'est plus possible, comme dans le modèle du ver, d'obtenir une formule liant directement la force et l'allongement. Nous allons donc utiliser un programme informatique pour simuler le comportement de ce modèle de molécule et obtenir l'allongement en fonction de la force utilisée. La simulation proposée est basée sur la méthode dite de « Monte Carlo » faisant participer nombres aléatoires, statistiques et probabilités. Dans le sens plus spécifique des simulations moléculaires, un modèle de la molécule est développé pour calculer une énergie, puis des changements aléatoires sont effectués pour converger vers l'état naturel de la molécule. Une fois la convergence atteinte, des calculs statistiques permettent d'approximer les paramètres cherchés. Par souci de simplicité, nous travaillons dans un espace à deux dimensions. IV.A - Modélisation plane La molécule comporte n monomères de longueur {. On note 0; EUR [--r,7| (à EUR [0,n -- 1]) l'angle formé par le segment à avec la direction de la force F°! Les angles 6, définissent la conformation de la molécule (figure 5). Z Figure 5 Représentation d'un brin d'ADN sous forme de chaïne librement jointe Pour un brin d'ADN soumis à une force F imposée, l'énergie mécanique Æ développée pour étendre la molécule Ann: s'écrit E=-2F (IV.1) où Fest l'intensité de la force et z l'allongement de la molécule suivant la direction de la force (figure 5). La simulation démarre à partir d'une conformation aléatoire du brin d'ADN. Q 20. Écrire une fonction d'entête def conformation(n:int): qui génère une conformation aléatoire d'un brin d'ADN composé de n segments. Cette fonction renvoie une liste où un vecteur de longueur n correspondant à l'orientation (angle 0;) de chaque segment. Q 21. Écrire une fonction d'entête def allongement(theta, l:float) -> float:

qui calcule l'allongement z de la chaine dans la conformation theta pour une 
longueur de segment 1.

2019-03-21 14:31:49 Page 7/10 (C)EATETSS
La modification de la conformation se fait en modifiant de facon aléatoire k 
angles successifs, £ étant un
paramètre de simulation ajustable.

Q 22. Écrire une fonction d'entête
def nouvelle conformation(theta, k:int):

qui crée une nouvelle conformation, à partir de la conformation theta en 
modifiant k valeurs successives à partir
d'un indice aléatoire.

IV.B - Critère de Metropolis Monte Carlo (MMC)

La méthode spécifique utilisée dans la plupart des études génétiques a été 
développée par Metropolis et al.
en 1953. Une probabilité P simule l'agitation thermique de la molécule. Cette 
agitation tend à désordonner la
molécule (maximum d'entropie), alors que la force extérieure tend à aligner les 
brins (diminution de l'entropic).
Les deux phénomènes convergent vers une situation d'équilibre statistique, où 
force et allongement moyen sont
liés. L'algorithme vise à déterminer cet équilibre statistique.

À partir d'une conformation de départ, d'énergie calculée Æ,, une nouvelle 
conformation est crée et son énergie
E, est calculée. Si cette nouvelle conformation possède une énergie inférieure 
à celle de son précurseur (E, < E;), elle est conservée. Si E, > E., la nouvelle conformation est conservée, avec la 
probabilité

EE, --E
B

où k est la constante de Boltzman et 7'la température. Si la nouvelle 
conformation est rejetée, c'est la confor-
mation de départ, d'énergie E,, qui est conservée pour la suite de la 
simulation.

Q 23. Écrire une fonction d'entête
def selection conformation(thetaA, thetaB, F:float, l:float, T:float):
qui prend en paramètre deux conformations successives thetaA et thetaB (thetaA 
étant le précurseur de

thetaB) et renvoie la conformation conservée connaissant F, l'intensité de la 
force de traction, 1 la longueur
d'un monomère et T la température.

IV.C --- Implantation de la simulation

L'algorithme est supposé avoir convergé lorsque la variance de l'allongement du 
brin d'ADN sur les 500 dernières
itérations est inférieure à une valeur EUR, paramètre de la simulation.

Q 24. Écrire une fonction d'entête
def monte_carlo(F:float, n:integer, l:float, T:float, k:integer, epsilon:float) 
-> float:

qui simule l'application d'une force de traction d'intensité F sur un brin 
d'ADN de n monomères de longueur 1,
à la température T. Les arguments k et epsilon correspondent aux paramètres de 
la simulation présentés plus
haut. Le résultat de la fonction est l'allongement moyen des 500 dernières 
conformations, une fois la convergence
atteinte.

Les candidats ont la liberté de concevoir et d'utiliser les structures de 
données qui leur semblent les mieux
adaptées à la programmation de la fonction monte_carlo. Ils veilleront à 
préciser le rôle et l'organisation des
données manipulées qui ne seraient pas déjà décrites dans le sujet.

Indication -- Compte tenu du nombre d'itérations envisagées, il est prudent de 
ne pas enregistrer toutes les
étapes intermédiaires de la simulation. On pourra considérer l'utilisation 
d'une file pour stocker les données
utiles à la simulation. À contrario d'une pile, une file est une structure de 
données où les premiers éléments
ajoutés à la file sont les premiers à en être retirés (« First In First Out »). 
En Python, une liste peut être utilisée
pour représenter une file grâce aux opérations append et pop(0).

Une fois la fonction monte_carlo développée, il est trivial de l'utiliser pour 
simuler différentes intensités de la
force et obtenir l'allongement correspondant du brin d'ADN simulé.

2019-03-21 14:31:49 Page 8/10 (C)EATETSS
Opérations et fonctions Python disponibles

Fonctions

range (n) renvoie la séquence des n premiers entiers (0 -- n --1)

list(range(5)) -- [0, 1, 2, 3, 4]

random.randrange(a, b) renvoie un entier aléatoire compris entre a et b-1 
inclus (a et b entiers)
random.random() renvoie un nombre flottant tiré aléatoirement dans |0, 1| 
suivant une distribution uniforme
random.shuffle(u) permute aléatoirement les éléments de la liste u (modifie u)

random.sample(u, n) renvoie une liste de n éléments distincts de la liste u 
choisis aléatoirement, si n >
len(u), déclenche l'exception ValueError

math.sqrt(x) calcule la racine carrée du nombre x
round(n) arrondit le nombre n à l'entier le plus proche
math.ceil(x) renvoie le plus petit entier supérieur ou égal à x

math.floor(x) renvoie le plus grand entier inférieur ou égal à x

Opérations sur les listes

len(u) donne le nombre d'éléments de la liste u :

len([1, 2, 3]) -- 3: len([[1,2]1, [3,4]]) -- 2

u + v construit une liste constituée de la concaténation des listes u et v :

[1, 2] + [3, 4, 5] -- [1, 2, 3, 4, 5]

n * u construit une liste constituée de la liste u concaténée n fois avec 
elle-même :

3 * [1, 2] -- [1, 2, 1, 2, 1, 2]

e in u et e not in u déterminent si l'objet e figure dans la liste u, cette 
opération a une complexité
temporelle en O(len(u))

2 in [1, 2, 3] -- True: 2 not in [1, 2, 3] -- False

u.append(e) ajoute l'élément e à la fin de la liste u (similaire à u = u + [e])

u.pop(i) : renvoie l'élément à l'indice i de la liste u et le supprime

del uli] supprime de la liste u son élément d'indice i

del uli:j] supprime de la liste u tous ses éléments dont les indices sont 
compris dans l'intervalle |i, j|

u.remove(e) supprime de la liste u le premier élément qui a pour valeur e, 
déclenche l'exception ValueError
si e ne figure pas dans u, cette opération a une complexité temporelle en 
O(Len(u))

u.insert(i, e) insère l'élément e à la position d'indice i dans la liste u (en 
décalant les éléments suivants) :
si i >= len(u),e est ajouté en fin de liste

uli]l, uljl = ulj]l, uli] permute les éléments d'indice i et j dans la liste u

Opérations sur les tableaux (np .ndarray)

np.array(u) crée un nouveau tableau contenant les éléments de la séquence u. La 
taille et le type des
éléments de ce tableau sont déduits du contenu de u

np.empty(n, dtype), np.empty((n, m), dtype) crée respectivement un vecteur à n 
éléments ou un ta-
bleau à n lignes et m colonnes dont les éléments, de valeurs indéterminées, 
sont de type dtype qui peut être
un type standard (bool, int, float, ...) ou un type spécifique numpy (np.int16, 
np.float32, ..). Si le
paramètre dtype n'est pas précisé, il prend la valeur float par défaut

np.zeros(n, dtype), np.zeros((n, m), dtype) fonctionne comme np.empty en 
initialisant chaque élé-
ment à la valeur zéro pour les types numériques ou False pour les types booléens

a.ndim nombre de dimensions du tableau a

a.shape tuple donnant la taille du tableau a pour chacune de ses dimensions

len(a) taille du tableau a dans sa première dimension, équivalent à a.shape [0]

a.size nombre total d'éléments du tableau a

a.flat itérateur sur tous les éléments du tableau a

np.ndenumerate(a) itérateur sur tous les couples (index, élément) du tableau a 
où « index » est un tuple
de a.ndim entiers donnant les indices de l'élément

a.min(), a.max() renvoie la valeur du plus petit (respectivement plus grand) 
élément du tableau a ; ces
opérations ont une complexité temporelle en O(a.size)

b in a détermine si b est un élément du tableau a ; si b est un scalaire, 
vérifie si b est un élément de a : si
b est un vecteur ou une liste et a un tableau à deux dimensions, détermine si b 
est une ligne de a

2019-03-21 14:31:49 Page 9/10 (C)EATETSS
-- np.concatenate((al, a2)) construit un nouveau tableau en concaténant deux 
tableaux selon leur première
dimension ; ai et a2 doivent avoir le même nombre de dimensions et la même 
taille à l'exception de leur taille
dans la première dimension (deux tableaux à deux dimensions doivent avoir le 
même nombre de colonnes
pour pouvoir être concaténés)

-- np.transpose(a) renvoie le transposé du tableau a

-- np.dot(a, b) calcule le produit matriciel des tableaux a et b

-- np.linalg.inv(a) renvoie l'inverse du tableau a, lève l'exception ValueError 
si a n'est pas un tableau
carré à deux dimensions et LinAlgError si a n'est pas inversible

eeerINeee

2019-03-21 14:31:49 Page 10/10 CHENE

Extrait du corrigé obtenu par reconnaissance optique des caractères



Centrale Informatique MP-PC-PSI 2019 -- Corrigé
Ce corrigé est proposé par William Aufort (professeur en CPGE) ; il a été relu
par Cyril Ravat (professeur en CPGE) et Benjamin Monmege (enseignant-chercheur
à l'université).

Ce sujet s'intéresse à l'élasticité de l'ADN, plus particulièrement à la 
relation
qui existe entre une force exercée sur un brin d'ADN et l'allongement de ce 
brin.
Cette relation permettrait d'avancer dans la compréhension de processus 
biologiques,
comme la réplication de l'ADN.
· La première partie comporte seulement trois questions d'implémentation de
fonctions utilitaires, dont deux sont explicitement au programme d'informatique 
pour tous.
· La deuxième partie introduit le protocole expérimental permettant d'évaluer
l'intensité de la force de traction exercée artificiellement sur un brin d'ADN
auquel on a accroché une bille aimantée, ainsi que l'allongement du brin. Cette
partie est principalement consacrée à des algorithmes de traitement d'images
(représentées par des tableaux Numpy à deux dimensions).
· Une fois les mesures effectuées, on souhaite maintenant les faire 
correspondre à
un modèle mathématique. La troisième partie étudie le « modèle du ver », qui
donne la relation entre force de traction et allongement sous la forme d'une 
formule mathématique faisant intervenir des caractéristiques du brin. Cette 
partie
propose de déterminer ces caractéristiques à partir des observations effectuées
et d'une fonction prédéfinie en Python, puis explore les bases de l'algorithme
de minimisation sous-jacent pour des problèmes à une ou deux dimensions.
· Enfin, la dernière partie propose un second modèle, probabiliste cette fois, 
permettant de simuler l'allongement d'un brin d'ADN soumis à une force donnée
en paramètre.
Les parties 2, 3 et 4 sont indépendantes, et le sujet couvre une grande 
proportion
du programme d'informatique pour tous (listes et tableaux Numpy, représentation
des nombres, ingénierie numérique et récursivité). La plupart des questions 
sont abordables dès la première année. Enfin, dans chaque partie la dernière 
question est plus
délicate, sans être vraiment difficile.

Indications
Partie I
2 Attention à ne pas utiliser la fonction moyenne n fois.
3 L'utilisation d'une fonction récursive semble adaptée.
Partie II
5 Pour arrondir à l'entier le plus proche, on pourra utiliser la fonction round.
7 Commencer par calculer le barycentre des positions de la liste, puis dans un
deuxième temps la moyenne des déplacements quadratiques. Ne pas oublier 
d'utiliser correctement le paramètre t.
8 L'énoncé suggère d'utiliser des fonctions intermédiaires. On peut commencer 
par
déterminer le rayon extérieur du plus grand anneau en fonction de la position du
centre de la bille. Puis pour chaque pixel de l'image, on cherchera à exprimer 
le
numéro de l'anneau dans lequel il se trouve.
Partie III
11 Dans la fonction curve_fit, la fonction f ne doit pas avoir la température T
comme argument. Il faut également extraire xdata et ydata à partir du tableau
à deux colonnes Fz. Attention à l'ordre.
12 Le nombre de chiffres significatifs dépend uniquement de la mantisse.
13 Pour h = 10-16 , utiliser la question 12 pour savoir comment seront 
représentés
les nombres 1 + h et 1 - h dans ce codage.
15 Le premier argument de derive est une fonction, il faut donc être 
précautionneux
si on veut utiliser derive deux fois de suite.
16 Il faut appliquer la méthode de Newton à  et non à .
17 Le système se déduira directement des équations des plans tangents 
considérés.
18 Deux stratégies sont possibles : utiliser les applications partielles, ou 
effectuer le
calcul à la main, avec des formules semblables à celle utilisée à la question 
14.
19 On pourra séparer de la fonction min_local_2D le calcul de la matrice J(x, 
y).
Pour ce calcul, commencer par définir les fonctions gx et gy , puis réutiliser 
la
fonction grad.
Partie IV
20 Générer des nombres aléatoires dans [ 0 ; 1 [, puis utiliser une 
transformation affine
pour obtenir des angles dans l'intervalle [ - ;  [.
22 La question demande de créer une nouvelle conformation. Attention également
aux indices manipulés.
24 Utiliser une liste comme une file pour conserver uniquement les 500 derniers
allongements. On pourra commencer par initialiser les 500 premiers allongements,
puis utiliser une boucle while pour la phase de convergence.

I. Fonctions utilitaires
1 Il suffit d'additionner tous les éléments de la séquence à l'aide d'une 
boucle, sans
oublier de diviser par la longueur de la séquence pour obtenir la moyenne.
def moyenne(X):
somme = 0
for i in range(len(X)):
somme += X[i]
return somme/len(X)
On peut aussi parcourir la séquence sans utiliser d'indice avec un itérateur :
def moyenne(X):
somme = 0
for x in X:
somme += x
return somme/len(X)
2 On utilise la formule de König-Huygens rappelée dans l'énoncé : on calcule 
d'abord
la moyenne des carrés comme précédemment, à laquelle on soustrait le carré de
la moyenne.
def variance(X):
s = 0
for x in X:
s += x**2
return s/len(X) - moyenne(X)**2
Une autre stratégie consiste à utiliser la définition de la variance. Attention
dans ce cas à utiliser la fonction moyenne une seule fois avant la boucle, afin
d'éviter une complexité en O(n2 ).
def variance(X):
s = 0
m = moyenne(X)
for x in X:
s += (x - m)**2
return s/len(X)
3 Pour pouvoir explorer l'ensemble des éléments de la séquence imbriquée, le 
plus
simple est d'écrire une fonction somme récursive. Si l'argument M de la 
fonction somme
est un composant élémentaire, c'est-à-dire un nombre réel (que l'on peut 
détecter
avec isinstance(M, numbers.Real)), on peut le renvoyer directement. Dans le cas
contraire, M est une séquence imbriquée : on calcule alors la somme des 
éléments qui
la compose à l'aide d'une boucle et de la fonction somme appliquée à chacun de 
ces
éléments.
L'énoncé ne suppose pas que le module numbers a été importé, ce qui est
pourtant nécessaire pour pouvoir utiliser numbers.Real.
def somme(M):
if isinstance(M, numbers.Real):
return M

else:
s = 0
for x in M:
s += somme(x)
return s
Dans le code précédent, le else est facultatif, du fait de la présence du return
dans le cas où M est un nombre réel. On pourrait donc l'enlever, ainsi que
le niveau d'indentation induit dans tout le bloc suivant, ce qui peut rendre
le code plus agréable à lire.

II. Mesures expérimentales
4 On commence par initialiser le tableau demandé à l'aide de la fonction 
np.zeros.
Puis on parcourt le tableau initial à l'aide d'une double boucle pour mettre à 
jour les
pixels dont la valeur est strictement inférieure au seuil, les autres étant 
déjà associés
à la valeur 0 dans l'image seuillée.
def seuillage(A, seuil):
S = np.zeros(A.shape, int)
for i in range(A.shape[0]):
for j in range(A.shape[1]):
if A[i, j] < seuil: S[i, j] = 1 return S Pour récupérer les dimensions du tableau en argument, on a utilisé ici l'attribut A.shape, qui était donné en annexe. Dans ce type d'épreuve, il est primordial de bien lire l'annexe avant de commencer le sujet, pour identifier notamment des fonctions pouvant être utiles. Une autre possibilité pour extraire les dimensions consiste à utiliser la fonction len. En effet, len(A) renvoie le nombre de lignes du tableau A (identique donc à A.shape[0]), et len(A[0]) renvoie le nombre de colonnes de A (identique à A.shape[1]). Enfin, une dernière solution consiste à utiliser le fait que la plupart des opérations usuelles (arithmétiques et logiques) sur les tableaux Numpy agissent élément par élément. On pourrait par exemple écrire : def seuillage(A, seuil): return 1 * (A < seuil) En effet, A < seuil renvoie un tableau Numpy de mêmes dimensions que A, contenant les booléens résultats des comparaisons des éléments de A avec seuil. Puis, le produit 1 * (A < seuil) permet de renvoyer un tableau dans lequel chacun des booléens précédents a été multiplié par 1, ce qui a pour effet de transformer les True en 1 et les False en 0. La fonction répond donc bien à la question posée. 5 On commence par extraire dans deux listes les abscisses et les ordonnées des pixels blancs de l'image, ce qui permettra de calculer les moyennes correspondantes avec la fonction moyenne de la question 1. Enfin on utilise la fonction round, rappelée dans l'annexe, pour arrondir chacune des deux valeurs obtenues à l'entier le plus proche.