Traitement de d'Information

Détection de séquences particulièresdans la structure ADN

Vincent Garin et Nicolas D'Alessandro – Décembre 2003

Plan de la présentation

● Biologie: de l'Homme à l'Information

● Statistique: modèles de Markov

● Informatique: applications sur Matlab 6.5

● Conclusion

De l'Homme à l'Information ...

Corps humain

Organes

Tissus

Cellules

BiologieStatistiqueInformatiqueConclusion

De l'Homme à l'Information ...

La cellule

● Grande diversité mais caractéristiques principales identiques:

– Noyau

– Mitochondries

– Système de Golgi

– ...● Remarque: sauf globules rouges (noyau diffus)

BiologieStatistiqueInformatiqueConclusion

De l'Homme à l'Information ...

Le noyau

● Chromosomes: 

– 23 paires (sauf gamètes)

– 1 chromosome = 1 macromolécule d'ADN 

    (état particulier de regroupement)

Remarque: compacité impressionante

1 chromosome «déroulé» = 1,8 m

BiologieStatistiqueInformatiqueConclusion

De l'Homme à l'Information ...

L'ADN (acide désoxyribonucléique)

● James Watson, Francis Crick – 25 avril 1953

● Support biochimique de l'information génétique chez tous les êtres vivants

● Deux longs filaments torsadés l'un dans l'autre pour former une structure en double hélice

● Assemblage de 4 bases (A, C, T et G)

BiologieStatistiqueInformatiqueConclusion

De l'Homme à l'Information ... BiologieStatistiqueInformatiqueConclusion

De l'Homme à l'Information ...

L'information génétique

Structure ADN               Non­codant               Répété

                                                                          Non­répété

                                       Codant              Gênes (3%)

● Codant: séquence de bases (codons) lues lors de la création des acides­aminés (protéines)

● Non­codant: codon stop, îlots CpG, ...

BiologieStatistiqueInformatiqueConclusion

De l'Homme à l'Information ...

Vous avez dit information !!!

● Les couples de bases sont appariés: C­G, A­T

● Code à 4 symboles                2 bits

● Être humain: 3 milliards de paires de bases dans chaque cellule

Pour une cellule: 2 bits x 3.109 = 6.109 bits = 1,5 Go

Pour le corps entier: 1,5 Go x 1012 cellules = 1,5 Zo

BiologieStatistiqueInformatiqueConclusion

Les modèles de Markov

Information

● La succession des zones = un message

– Notion de langage ADN (cf. parole)

● Notre projet: détection du «phonème» Îlot CpG

Parole <­­­> ADNX1, ..., Xn <­­­> A, T, ..., G, T 

B o~ Z u R <­­­> Îlot – Gêne – Stop

BiologieStatistiqueInformatiqueConclusion

Les modèles de Markov

Îlot CpG

● CpG: paire de nucléotides C et G (rare dans la plupart des séquences d'ADN)

● Îlot: zone où l'occurrence de ces paires est élevée

● Intéressant: coïncide avec les zones les plus significatives du génome

● Problèmes: reconnaissance et détection

BiologieStatistiqueInformatiqueConclusion

Les modèles de Markov

Chaînes de Markov

A

GT

C

Début Fin

BiologieStatistiqueInformatiqueConclusion

Les modèles de Markov

Chaînes de Markov

● 2 matrices A (aij):

– A+ : probabilités de transition dans un îlot

– A­ : probabilités de transition hors de l'îlot

● Critère de décision: score X =P X∣îlot

P X∣pas îlot

BiologieStatistiqueInformatiqueConclusion

Les modèles de Markov

Réseau de Markov caché

Chaîne de MarkovÎlot (A+)

Chaîne de MarkovPas îlot (A­)

1 ­ q

1 ­ p

p q

BiologieStatistiqueInformatiqueConclusion

Les modèles de Markov

Réseau de Markov caché

● M: matrice des probabilités de transition (états cachés)

8 états: A+, C+, T+, G+, A­, C­, T­, G­

● Bj: matrice d'émission de l'état j

4 symboles émis: A, C, T, G● But: ...A C C C T T C C C G G C G G G C C A...

...A­C­C­C­T­T­C+C+C+G+G+C+G+G­G­C­C­A­...

...[   pas îlot   ] [           îlot          ] [   pas îlot   ]

BiologieStatistiqueInformatiqueConclusion

Les modèles de Markov

Viterbi

● Meilleur algorithme pour la résolution des problèmes

– D'estimation: P(X | M) avec X: {x1, ..., xp}, M: {A,B,λ}

– De décodage: P(Q | X) avec Q: {q1, ..., qp}

● Pour l'entraînement: Baum­Welch

BiologieStatistiqueInformatiqueConclusion

Les modèles de Markov

Viterbi

BiologieStatistiqueInformatiqueConclusion

Applications sur Matlab 6.5

Démonstration

● Le génome est disponible sur Internet

● Matlab permet:

– L'utilisation de données en ligne

– La recherche d'expressions régulières

BiologieStatistiqueInformatiqueConclusion

Conclusion

● Possibilités d'étendre le «vocabulaire ADN» à d'autres îlots             règles, grammaires

● Outils de Traitement de l'Information: domaines d'applications très variés voire inattendus

● But: produire des logiciels de génétique, rendre la recherche dans ce domaine plus accessible

BiologieStatistiqueInformatiqueConclusion

Merci de votre attention

Questions ? Suggestions ?

Cette présentation est disponible à l'adresse:http://users.magellan.fpms.ac.be/twokouks/TI/projet.pdf

Le fichier Matlab est disponible à l'adresse:http://users.magellan.fpms.ac.be/twokouks/TI/adn_matlab.htm