ARN késako ?

ARN késako ?

Julie BERNAUER Adrien GUILHOT-GAUDEFFROYYann PONTY Mireille REGNIER

EQUIPE PROJETAMIBInria Saclay 28 Septembre 2012

Les ARN et leur repliement

Nuit des chercheurs - LIX/Inria AMIB 28/09/2012 - 2

1

Principe central de la biologie moléculaire

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 3

ADNA

T

G

C

T

A

C

G

A

T

G

C

G

C

T

A

C

GARN Poly.

A G U C AG G U CARNm

Ribosome

Protéine Ala LeuCyt

Mais il existe de très nombreuses exceptions,

et de très nombreux autres rôles pour l’ARN !

Règle : ADN (A,C,G,T) → ARN (A,C,G,U) → Protéine

Nuit des chercheurs - LIX/Inria AMIB 4

Repliement des ARN

• ARN = un seul brin• Structure très variable …• … plus conservée au cours de

l’évolution que la séquence• Diversité de fonction

Fonction (partiellement) codée dans la structure

Prédire le repliement de l’ARN

28/09/2012

Nuit des chercheurs - LIX/Inria AMIB 5

Les paires de bases (Canoniques)

28/09/2012

  Canonical base-pairs  

G/C Paires Watson/Crick

U/A

U/G

Paire Wobble

Nuit des chercheurs - LIX/Inria AMIB 6

La structure secondaire : Une simplification raisonnable

28/09/2012

Modèle 3D ARN ribosomal (5s)

Structure secondaire

• Uniquement Watson/Crick (A/U et G/C) et Wobble (G/U)

• Pseudonoeuds interdits

G G A G …A

G C

U

G

G

U

C

Contraintes/Règles du jeu

Repliement par minimisation de l’énergie libre

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 7

…CAGUAGCCGAUCGCAGCUAGCGUA…Séquence d’ARN

Nombreuses structures secondaires

Paradigme historique :

= Structure d’énergie libre minimale

Structure fonctionnelle = Structure compatible la plus stable

Nombre maximal de paires de bases

Au boulot …

Nuit des chercheurs - LIX/Inria AMIB 28/09/2012 - 8

2

A vous de jouer !

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 9

Saurez vous trouver, pour l’ARN ci-dessus, le repliement

ayant un nombre maximal de paires de bases ?

Règles :

1. Seules les paires de bases

canoniques sont autorisées.

2. Les croisements et liaisons extérieures sont interdites.

GAGAAGUACUUGAAAUUGGCCUCCUC

A U

U AG C

C G

G U

U G

Solution

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 10

• Ce repliement est le seul à apparier toutes les bases.

• Il existait 8 553 597 repliements (partiels) valides.

Comment retrouver ce repliement sans les énumérer tous ? Algorithme de programmation dynamique

(Diviser pour régner + Mémorisation des résultats)

Le design d’ARNUn problème inverse

Nuit des chercheurs - LIX/Inria AMIB 28/09/2012 - 11

3

Design d’ARN structurés

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 12

• On sait (à peu près) prédire le repliement des ARN• Pourrait on s’en servir pour créer de nouvelles molécules ?Design d’ARN : Créer une séquence se repliant en une structure secondaire prédéterminée (ex. : rôle thérapeutique).

…CAGUAGCCGAUCGCAGCUAGCGUA…

Prédiction du repliement

Design d’ARN

A vous de jouer…

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 13

Aucun algorithme exact et efficace n’est actuellement connu.Saurez vous résoudre le problème à la main ?

But du jeu : Créer une séquence ARN1. se repliant optimalement en la structure cible

#maximal de paires de bases = #paires dans structure cible.

2. de façon unique pas de repliement alternatif ayant autant de paires de bases.

A vous de jouer…

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 14

Séquence courante

Repliement visé

Nombre de repliements co-optimaux

(7 paires de base)Navigation parmis

les co-optimaux

Positions correctes

A vous de jouer…

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 15

La séquence est modifiée en cliquant sur

une position

A vous de jouer…

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 16

Le repliement de la nouvelle séquence est

calculé et affiché

Le nombre de repliements co-optimaux

est mis à jour

La séquence est modifiée en cliquant sur

une position

A vous de jouer…

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 17

Le repliement de la nouvelle séquence est

calculé et affiché

Le nombre de repliements co-optimaux

est mis à jour

La séquence est modifiée en cliquant sur

une position

La partie se termine quand le repliement

est correct et unique.

Merci !Questions ?

AMIB Saclay

www.inria.fr

Algorithmique du repliement

Nuit des chercheurs - LIX/Inria AMIB - 1928/09/2012

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 20

?

Quel cas choisir ???

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 21

…

?

?

?

Quel cas choisir ???

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 22

…<22

20

1820

Quel cas choisir ???

20 1719 1620

22

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 23

…

…

Quel cas choisir ???Faut il tout essayer ?

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 24

Quel cas choisir ???Faut il tout essayer ?

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 25

3𝑛𝑜𝑚𝑏𝑟𝑒𝑑𝑒𝑑𝑎𝑛𝑠𝑒𝑢𝑟𝑠

Quel cas choisir ???Faut il tout essayer ?

Nombre exponentiel de solutions→ Impossible de tout essayer !!

1 2 3 4 5 6 7 8 9 100

10000200003000040000500006000070000

Migraine

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 26

3𝑛𝑜𝑚𝑏𝑟𝑒𝑑𝑒𝑑𝑎𝑛𝑠𝑒𝑢𝑟𝑠

Quel cas choisir ???Faut il tout essayer ?

Nombre exponentiel de solutions→ Impossible de tout essayer !!

1 3 5 7 9 11 13 15 17 190

5000000001000000000150000000020000000002500000000300000000035000000004000000000

Migraine

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 27

3𝑛𝑜𝑚𝑏𝑟𝑒𝑑𝑒𝑑𝑎𝑛𝑠𝑒𝑢𝑟𝑠

Quel cas choisir ???Faut il tout essayer ?

Nombre exponentiel de solutions→ Impossible de tout essayer !!

1 17 33 49 65 81 97 1131291451610

2E+0794E+0796E+0798E+0791E+080

1.2E+0801.4E+0801.6E+080

Migraine

#Atomes dans l’univers (1080)

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 28

…

…

Mais calcul redondant …

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 29

Mais calcul redondant …

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 30

…

Solution : Diviser pour régner(Déléguer pour résoudre)

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 31

…

?

20 !

Solution : Diviser pour régner(Déléguer pour résoudre)

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 32

…?

19 !

Solution : Diviser pour régner(Déléguer pour résoudre)

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 33

…?

?

18 !

0 !

Solution : Diviser pour régner(Déléguer pour résoudre)

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 34

…?

?

16 !

2 !

Solution : Diviser pour régner(Déléguer pour résoudre)

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 35

…?19 !

Solution : Diviser pour régner(Déléguer pour résoudre)

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 36

…?

18 !

Solution : Diviser pour régner(Déléguer pour résoudre)

28/09/2012Nuit des chercheurs - LIX/Inria AMIB - 37

Nuit des chercheurs - LIX/Inria AMIB 38

Combien ça coûte ? (Programmation dynamique)

?

Max( + + )

?

?? ?

= Max

Nombre de danseurs → n• Un assistant par région dans la ronde → (n*(n-1)) / 2 ≈ n2

• Chaque assistant fait, au pire, n calculsNombre total de calculs : A peu près n3 …

Attention à l’ordre des calculs (Commencer par les petites régions …)!

28/09/2012

Nuit des chercheurs - LIX/Inria AMIB 39

Combien ça coûte

?

Max( + + )

?

?? ?

= Max

Nombre de danseurs → n• Un assistant par région dans la ronde → (n*(n-1)) / 2 ≈ n2

• Chaque assistant fait, au pire, n+1 calculsNombre total de calculs : A peu près n3 …

Attention à l’ordre des calculs (Commencer par les petites régions …)!

1 2 3 4 5 6 7 8 9 100

10000200003000040000500006000070000

Migraine

Stratégie Tout essayer Diviser pour régner

Nombre de calculs Exponentiel Polynomial O(n3)

1 2 3 4 5 6 7 8 9 10

28/09/2012

Nuit des chercheurs - LIX/Inria AMIB 40

Combien ça coûte

?

Max( + + )

?

?? ?

= Max

Nombre de danseurs → n• Un assistant par région dans la ronde → (n*(n-1)) / 2 ≈ n2

• Chaque assistant fait, au pire, n+1 calculsNombre total de calculs : A peu près n3 …

Attention à l’ordre des calculs (Commencer par les petites régions …)!

1 6 11 16 21 26 31 360

10000200003000040000500006000070000

Stratégie Tout essayer Diviser pour régner

Nombre de calculs Exponentiel Polynomial O(n3)

1 6 11 16 21 26 31 36

Migraine

40 40

28/09/2012

Quelques applications

Nuit des chercheurs - LIX/Inria AMIB 28/09/2012 - 41

Nuit des chercheurs - LIX/Inria AMIB 42

Performances

28/09/2012

Nuit des chercheurs - LIX/Inria AMIB 43

Evaluer la qualité d’une prédiction

28/09/2012

Intron du groupe II (D1-D4)RFAM ID: RF02001

RNAFold [Gruber AR et al. NAR 2008]

Nuit des chercheurs - LIX/Inria AMIB 44

Evaluer la qualité d’une prédiction

28/09/2012

RNAFold [Gruber AR et al. NAR 2008]

Intron du groupe II (D1-D4)RFAM ID: RF02001

Nuit des chercheurs - LIX/Inria AMIB 45

Evaluer la qualité d’une prédiction

28/09/2012

• De faibles probabilités indiquent des régions incertaines

• BP>99% → Avg. PPV>90% • BP>90% → PPV>83%

RNAFold [Gruber AR et al. NAR 2008]

Intron du groupe II (D1-D4)RFAM ID: RF02001

Nuit des chercheurs - LIX/Inria AMIB 46

Sensibilité des ARN aux mutations

28/09/2012

• Echantillonage → Clustering → PCA

[Halvorsen M et al, PLOS Gen 2010]

Nuit des chercheurs - LIX/Inria AMIB 47

Sensibilité des ARN aux mutations

28/09/2012

• Echantillonage → Clustering → PCA

[Halvorsen M et al, PLOS Gen 2010]

?