Modèles probabilistes pour les séquences biologiques

Plan

§  Prédiction de gènes •  Modèle de Bernoulli

•  Rapport de vraisemblance

§  Chaînes de Markov •  îlots CpG

Gène

§  Gène: une séquence de nucléotides codant pour une protéine

§  Problème de la prédiction des gènes: Déterminer le début et la fin des gènes dans un génome

Les différences entre procaryotes et eucaryotes

§  Dans les génomes procaryotes la plupart de la séquence est codante pour des protéines.

•  Par exemple le 70% du génome de H.influenzae est codant.

•  Dans les procaryotes chaque gène est une séquence de bases où il n’y a pas d’introns.

Un gène procaryotes

§  Comment trouver les séquences codantes ? •  Chercher les ORFs

•  Comment choisir les gènes parmi tous les ORFS ?

H. Richard - UPMC 5

3

A.Carbone - UPMC 9

Dans les génomes procaryotes la plupart de la séquence est codante pour des protéines.

Par exemple le 70% du génome de H.influenzae est codant.

Les procaryotes se répliquent assez rapidement, donc moins de temps est dépensé pour

la mise en route de mécanismes d’organisation moléculaire et de processus biologiques

sophistiqués.

Dans les procaryotes chaque gène est une séquence de bases où il n’y a pas d’introns.

Quelques différences entre procaryotes et eucaryotes

qui jouent un rôle dans la transcription

A.Carbone - UPMC 10

A.Carbone - UPMC 11

5’ untraslatedregion (UTR)

A.Carbone - UPMC 12

Epissage chez les eucaryotes

exon1 exon2 exon3intron1 intron2

transcription

traduction

epissage

exon = codant

intron = non-codant

Batzoglou

Un gène eucaryotes

§  Comment trouver les séquences codantes ? •  Chercher les ORFs

•  Comment choisir les gènes parmi tous les ORFS ?

H. Richard - UPMC 6

Prediction de genes, objectifs

Localiser les genes presents sur une sequence d’ADN

Retrouver la structure complete des genes :

JS Varre (IUP GenPro) Introduction a la bioinformatique annee 2007-2008 31 / 41

Un gène eucaryotes : Epissage

H. Richard - UPMC 7

3

A.Carbone - UPMC 9

Dans les génomes procaryotes la plupart de la séquence est codante pour des protéines.

Par exemple le 70% du génome de H.influenzae est codant.

Les procaryotes se répliquent assez rapidement, donc moins de temps est dépensé pour

la mise en route de mécanismes d’organisation moléculaire et de processus biologiques

sophistiqués.

Dans les procaryotes chaque gène est une séquence de bases où il n’y a pas d’introns.

Quelques différences entre procaryotes et eucaryotes

qui jouent un rôle dans la transcription

A.Carbone - UPMC 10

A.Carbone - UPMC 11

5’ untraslatedregion (UTR)

A.Carbone - UPMC 12

Epissage chez les eucaryotes

exon1 exon2 exon3intron1 intron2

transcription

traduction

epissage

exon = codant

intron = non-codant

Batzoglou

Modèles de Bernoulli

§  Modèle de background (composition en nucléotides) (%A, %C, %G, %T)

§  Modèle pour les codons (code génétique dégénéré)

(%AUU, %AUC, %AUG, %AUA,! %GUU, %GUC,……! %GGA, %GGC, %GGG, %GGT)

Probabilité d’une séquence

§  Avec le modèle de Bernoulli background

§  Avec le modèle de codons

§  Nb nucléotides avant le codons stop TAA (bg) ?

P (S = c0 c1 . . . c`�1 | codons) =`/3Y

i=0

pc3i c3i+1 c3i+2

P (S = c0 c1 . . . c`�1 | background) =`�1Y

i=0

pci

Rapport de vraisemblance

§  Ratio des probabilités pour les deux modèles dans une fenêtre (100 bp)

§  Pour chaque phase, score: X

i2fenetre mod3

log

pci ci+1 ci+2

pci · pci+1 · pci+2

Phase 1

Phase 2

Phase 3

gènes E. Coli

Annotation de sites promoteurs

Matrices poids position

Sites promoteurs

H. Richard - UPMC 12

•  Les promoteurs sont des segments d’ADN qui précèdent les zones qui régulent le début de la transcription

5

A.Carbone - UPMC 17

Détection d’un site d’épissage

5’ 3’Donor site

Position

% -8 … -2 -1 0 1 2 … 17A 26 … 60 9 0 1 54 … 21C 26 … 15 5 0 1 2 … 27G 25 … 12 78 99 0 41 … 27T 23 … 13 8 1 98 3 … 25

Extrait d’une présentation de Serafim Batzoglou (Stanford)

Intron 1 Intron 2

A.Carbone - UPMC 18

Sites d’épissage consensus

Donateur: 7.9 bitsAccepteur: 9.4 bits

A.Carbone - UPMC 19

Promoteurs

• Les promoteurs sont des segments d’ADN qui précèdent les zones qui régulent le début de la transcription

• Promoteur attire l’ARN-polymerase vers le site de départ de la transcription

5’Promoteur 3’

A.Carbone - UPMC 20

Mécanisme d’épissage

(http://genes.mit.edu/chris/)

•  Promoteur attire l’ARN-polymerase vers le site de départ de la transcription

Région régulatrice

H. Richard - UPMC 13

Région régulatrice

§  Généralement 100-500 bp en amont du début de la transcription (procaryotes)

•  peut aller jusqu’à 5kbp chez les eucaryotes.

§  Motifs de séquence responsable de la fixation

H. Richard - UPMC 14

group of genes activated by PHO4p (from J. Van Helden course)

Interface between the yeast Pho4p protein and one of its binding sites

10

Pho4p (yeast)

Pho4p DNA binding site (oligonucleotide)

Sites promoteur

§  Un site promoteur peut être localisé n’importe où dans la région de régulation

§  Il y a des variations dans la composition de la séquence du site promoteur (en général des substitutions).

H. Richard - UPMC 15

Motifs et débuts de transcription

H. Richard - UPMC 16

gene ATCCCG

gene TTCCGG

gene ATCCCG

gene ATGCCG

gene ATGCCC

Comment modéliser les séquences promoteurs ?

Comment annoter une région en amont d’un gène ?

Matrice des fréquences

§  Chaque colonne : loi de Bernoulli •  Résume les préférences de séquence du motif

A 1 0 8 0 0 0 0 0 0

C 0 8 0 8 0 0 0 1 1

G 7 0 0 0 8 0 8 4 4

T 0 0 0 0 0 8 0 3 3

Matrice de comptages

Matrice des fréquences

A 0.125 0 1 0 0 0 0 0 0C 0 1 0 1 0 0 0 0.125 0.125G 0.875 0 0 0 1 0 1 0.5 0.5T 0 0 0 0 0 1 0 0.375 0.375

Matrice des fréquences

§  En pratique on ajoute des pseudo-comptages •  +1 partout ou en proportion des fréquences de chaque

nucléotide A 1+1 0+1 8+1 0+1 0+1 0+1 0+1 0+1 0+1

C 0+1 8+1 0+1 8+1 0+1 0+1 0+1 1+1 1+1

G 7+1 0+1 0+1 0+1 8+1 0+1 8+1 4+1 4+1

T 0+1 0+1 0+1 0+1 0+1 8+1 0+1 3+1 3+1

A 0.17 0.08 0.75 0.08 0.08 0.08 0.08 0.08 0.08C 0.08 0.75 0.08 0.75 0.08 0.08 0.08 0.17 0.17G 0.67 0.08 0.08 0.08 0.75 0.08 0.75 0.42 0.42T 0.08 0.08 0.08 0.08 0.08 0.75 0.08 0.33 0.33

fi,j =ni,j + cPj ni,j + c

Matrice de score poids position

§  log-rapport de vraisemblance

§  pj : fréquences des nt dans le modèle de Bernoulli background

§  Score à une position : •  somme des poids des nucléotides pour chaque position

wi,j = log2fi,jpj

A -0.96 -1.96 1.21 -1.96 -1.96 -1.96 -1.96 -1.96 -1.96C -1.07 2.10 -1.07 2.10 -1.07 -1.07 -1.07 -0.07 -0.07G 1.93 -1.07 -1.07 -1.07 2.10 -1.07 2.10 1.25 1.25T -1.96 -1.96 -1.96 -1.96 -1.96 1.21 -1.96 0.04 0.04

GGACGTGGT! ||||||||! GACGTGGTT!

1.93 – 1.07 + 1.21 + 2.1 + 2.1 + 1.21 + 2.1 + 1.25 + 0.04 à 10.87

1.93 – 1.96 – 1.07 – 1.07 - 1.96 – 1.07 + 2.1 + 0.04 + 0.04 à -3.02

Scanner une séquence

§  Comment décider la valeur seuil du score ?

Distribution du score

§  Distribution du score pour un ensemble de séquences aléatoire avec le modèle background

§  Seuil d’annotation fixé pour avoir un taux de fausse prédiction attendu de x%

•  on décide de la proportion de fausses alertes

x%

A simple HMM for gene detection

Bioinformatics Algorithms

A simple HMM M for gene detection

• States are ‘in exon’ and ‘in intron’

• p probability that the process stays ‘in exon’; 1–p probability that the

process switches into ‘in intron’

• q probability that the process stays ‘in intron’; 1–q probability that the

process switches into ‘in exon’

• The probability that an exon has length k is

P(exon of length k | M) = pk (1–p)

exon intron0.4 0.6

0.6

0.4P(A)=0.2

P(C)=0.3

P(G)=0.3

P(T)=0.2

P(A)=0.25

P(C)=0.25

P(G)=0.25

P(T)=0.25

21

A.Carbone - UPMC 81

Distribution des longueurs

Un HMM simple pour identifier un gène eucaryote :

exon intron

1-p

1-q

p q

P(exon de longueur k) = pk(1-p) (distribution géométrique)

Mais la distribution des longueurs des exons ne peut pas être géométrique: la longueur

semble jouer un rôle fonctionnel dans l’epissage. Exons qui sont trop courts (<50pb)

ne sont pas détectées par le spliceosome et exons qui sont trop longues (>300pb) sont

difficiles à détecter. D’autres modèles de la longueurs des exons ont été proposés.

A.Carbone - UPMC 82

HMM généralisés (GHMM)

Dans un GHMM la sortie d’un état peut être une chaîne de symboles de longueur finie.

Pour un état donné, la longueur et la chaîne de symboles peut être choisi aléatoirement

selon une distribution de probabilité. La distribution de probabilité peut être différente

pour des états différents.

- Q ensemble fini d’états

- S distribution de probabilité associée à l’état initiale

- Tij probabilité de transition pour chaque paires d’états i,j �Q

- f distribution des longueurs par état (fq est la distribution des longueurs de l’état q)

- Modèles de probabilités pour chaque état selon les chaînes de sorties issues après la

visite d’un état

A.Carbone - UPMC 83

Modèle GENSCANLe modèle probabiliste de la structure des gènes (Berge et Karlin, 1997) est basé sur un GHMM

États = unités fonctionnelles d’un gène

Transitions entre états = le modèle assure

que l’ordre de visite des états est

biologiquement cohérent

Division des états selon les 3 reading frames

Modélisation du gène dans le brin de lecture

Modélisation du gène dans le brin opposé

A.Carbone - UPMC 84

Prédiction de la structure d’un gène

Une lecture ) d’une séquence S de longueur L est une séquence ordonnée d’états (q1,…, qt)

de durée di associée à chaque etat (L = ¦ti=1 di).

) est une annotation possible d’une séquence.

Supposons de connaître une lecture ) et une séquence S. Soit Si le segment de S produit

par qi et soit P(Si|di) la probabilité de générer Si à l’ état qi et avec durée di. La probabilité que

le modèle est passé par l’état qi pour générer la séquence selon ) est:

P() ,S) =Sq1fq1(d1)P(S1|d1) �tk=2Tqk-1qkfqk(dk)P(Sk|dk)

Supposons de connaître S ainsi que une lecture ), les deux de longueur L. La probabilité

conditionnée de ) étant donné que la séquence génératrice est S, peut être calculée

comme suit:

P(),S) P(),S)

P()|S) = ------------ = -----------------------------------------

P(S) ¦ P()i,S))i est une lecture de longueur L

Outils statistiques de prédiction des gènes

• GENSCAN/Genome Scan • TwinScan • Glimmer • GenMark

28

A.Carbone - UPMC 109 A.Carbone - UPMC 110

A.Carbone - UPMC 111 A.Carbone - UPMC 112