<!-- Slide number: 1 -->
U.R.P.A.H
Développement d’un système d'extraction de motifs spatiaux à partir des structures protéiques
Présenté par : Manel ZOGHLAMI
Soutenu le 15/01/2010 devant le jury composé de
Riadh ROBBANA Président
Mohamed DAASS Examinateur
Mondher MADDOURI Encadrant INSAT
Rabie SAIDI Encadrant Entreprise
1
Notes:
Mr. le président, M. membres du jury, chers parents et chers amis j’ai l’honneur de vous présenter mon projet de fin d’études encadré
<!-- Slide number: 2 -->
Plan
2
Notes:
Nous allons entamer cette présentation par l’énonciatio
<!-- Slide number: 3 -->
Introduction
Emergence de la bioinformatique comme une jeune science multidisciplinaire
Emergence des méthodes en biologie
volume de données biologiques très important
données difficiles à traiter manuellement ou par des calculs simples.
Exploitation par les moyens biochimiques et les analyses in vitro très coûteuse en temps et en argent.
Le défi n’est désormais la collecte des données biologiques mais plutôt leur exploration d’une manière rapide et efficace.
La fouille des données biologiques
3
Notes:
La bioinformatique est une jeune science multidisciplinaire au carrefour de la biologie et de la technologie de l’information.
Elle a été rendue indispensable avec l’émergence de méthodes en biologie capables de générer de très importants volumes de données difficiles à traiter manuellement ou par des calculs simples. L’exploitation de ses données par les moyens biochimiques et les analyses in vitro s’avère très coûteuse en temps et en argent.
Le défi n’est désormais la collecte des données biologiques mais plutôt leur exploration d’une manière assez rapide et efficace permettant de dévoiler les secrets de la cellule.
<!-- Slide number: 4 -->
Problématique
4
Notes:
Notre pbmatique se pose ds le cadre de la bioionfo
<!-- Slide number: 5 -->
Problématique
| Acide aminé | Lettre |
| --- | --- |
| alanine | A |
| cystéine | C |
| acide aspartique | D |
| acide glutamique | E |
| phénylalanine | F |
| glycine | G |
| histidine | H |
| isoleucine | I |
| lysine | K |
| leucine | L |
| méthionine | m |
| asparagine | n |
| proline | P |
| glutamine | Q |
| arginine | R |
| sérine | S |
| thréonine | T |
| valine | V |
| tryptophane | W |
| tyrosine | Y |
Ensemble d’atomes dans l’espace
Les acides aminés
- Constituants des protéines
Composés d’atomes
Représentés par des lettres
5
Notes:
Les données biologiques traitées dans le domaine de la bioinformatique sont diverses.
Nous allons nous intéresser dans notre projet aux protéines
Cette figure est une représentation d’une protéine.
- qui sont des polymères (substances constituées de macromolécules ayant la même nature chimique)
------------Il s’agit des centaines ou des milliers d’atomes dans l’espace.
------------Ces atomes là sont regroupés dans des molécules appelés acides aminés.
<!-- Slide number: 6 -->
Problématique
A G E T G A C T A
Structure primaire
-définie par la connaissance de la nature des acides aminés et par l'ordre de leur enchaînement
- Peut être présentée par une chaine de caractères
6
Notes:
---------Les protéines présentent 4 niveaux de structures. Nous allons nous intéressés à 2 d’entre elles :
Structure primaire et structure secondaire
--------commençons par le premier type.
Structure primaire : elle est définie par la connaissance de la nature des acides aminés et par l'ordre de leur enchaînement, donc ne prend pas en considération la forme que prend une protéine dans l’espace
- Peut être présentée par une chaine de caractères
<!-- Slide number: 7 -->
Publicité
Problématique
Structure secondaire et tertiaire
-définie par la forme géométrique de la chaîne d'acides aminés
- Peut être présentée par un graphe dans l’espace
7
Notes:
Un neods represente un acide aminé
Les arc continus representent les liens qui sont presents ds les structures primaires
Les autres arcs représentent les liaisons apportés par les structure secondaire
--------
En fait, la plus part des outils en bio-info utuilisent las structrures primaires, qui sont plus facile à traiter. Mais , notre système s’interssera plutôt à l’analyse des str sec .
<!-- Slide number: 8 -->
Problématique
Les protéines contiennent des patterns ou motifs qui ont été préservés tout au long de l'évolution.
Extraction des motifs aide à
-regrouper les séquences biologiques dans des familles structurelles ou fonctionnelles
-Classifier une protéine nouvellement séquencée
-mieux comprendre les règles qui contrôlent l’évolution des protéines
savoir leurs fonctions biologiques
8
Notes:
Les séquences protéiques contiennent des patterns ou motifs qui ont été préservés tout au long de l'évolution.
Notre nous interessons à l’exraction de ces motifs partir des graphes en 3 D .
Classifier une protéine nouvellement séquencée : identifier la famille à la quelle elle appartient
<!-- Slide number: 9 -->
Problématique
Taches à réaliser :
Extraction des motifs à partir des graphes des acides aminés
Visualisation des protéines des différentes familles
Génération de fichier servant comme entrée au système Wéka
9
Notes:
Qui est la tache principale du système à developper
Le sysreme contiendra également un module de
<!-- Slide number: 10 -->
Méthode d’extraction des motifs
10
<!-- Slide number: 11 -->
Méthode d’extraction des motifs
L’algorithme KMR
permet d’identifier les mots répétés dans des chaînes de caractères, des arbres ou des tableaux.
repose sur la notion de classes d’équivalence
deux positions i et j dans une chaîne de caractères sont k-équivalentes si et seulement si les deux sous-chaînes de longueur k commençant à partir de i et j sont identiques
11
Notes:
Notre methode repose sur
<!-- Slide number: 12 -->
Méthode d’extraction des motifs
Génération des graphes des acides aminés
Description séquentielle prenant en compte les relations n’existant pas des les structures primaires
12
Notes:
Notre méthode est une extension de KMR
Il prend en entrée des fichier comportant les coordonnées des atpmes ds l’espace
<!-- Slide number: 13 -->
Méthode d’extraction des motifs
13
Notes:
La deuxieme partie étant l’esxtractiopn des motifs
<!-- Slide number: 14 -->
Méthode d’extraction des motifs
Extension de l’algorithme pour les graphes
Une relation d’équivalence Ek, 1≤k≤m, peut être représentée par un vecteur Vk[1.. m-k+1], où chaque composante Vk[i], 1≤i≤m-k+1, de ce vecteur représente le numéro de la classe d’équivalence à laquelle appartient la position i .
fusionner les nœuds ayant un voisin commun présent dans la séquence primaire.
Les positions i dans la description séquentielle sont placées dans les ensembles de piles P et Q de la façon suivante :
Les positions i qui appartiennent à la même classe de E sont mises dans la même pile P (V[i]).
On empile seulement les positions qui sont présents dans la séquence primaire.
Chaque élément de P est dépilé et les numéros i ainsi obtenus sont placés dans toutes les piles Q correspondantes aux classes de tous les successeurs du nœud causant l’empilement de i vers la pile Q considérée.
Si la classe Va de chaque position déjà retirée est égale à la classe de la position précédemment retirée. Sinon on a une nouvelle classe
Une classe est déclarée comme motif si elle n’est plus utilisée pour construire de nouvelles classes d’ordre supérieur, autrement dit si les piles P et Q correspondantes n’interviennent plus à la construction de nouvelles classes.
14
Notes:
On commence par fusionner ……………………;
Ensuite, on passe à extraire les classes d’equivalence en tenant compte de la distingtion entre noeuds
<!-- Slide number: 15 -->
Méthode d’extraction des motifs
Elaguer les sous motifs redondants
Présentation des motifs sous forme de graphes
15
Notes:
C’est une étape supplementaire , permettant
<!-- Slide number: 16 -->
Publicité
Algorithme d’extraction des motifs
Exemple
Structure primaire : GATGVCA
Nouveau format séquentiel:
GACVTGAVCA
Structure primaire : GAFCGVTA
Nouveau format séquentiel:
GACTFCGAVTA
16
Notes:
Le graphe suivant a comme structure primaire …………………………
Le Nouveau format séquentiel itrouduit tt les voisin pour un nœud , pas seulement ceux de la structure primaire
De meme , en genere la description sequentielle du deuxime graphe
<!-- Slide number: 17 -->
Algorithme d’extraction des motifs
Exemple
Description séquentielle globale
Initialisation
Classe1: Noeuds {G } - Arêtes {}
Classe2: Noeuds {A } - Arêtes {}
Classe3: Noeuds {C } - Arêtes {}
Classe4: Noeuds {V } - Arêtes {}
Classe5: Noeuds {T } - Arêtes {}
Classe6: Noeuds {F } - Arêtes {}
17
Notes:
<!-- Slide number: 18 -->
Algorithme d’extraction des motifs
Première itération
Empilement dans des piles Pi
Dépilement de P2 vers les piles Qi
Nouvelles classes
Noeuds {A, C } - Arêtes {0-1 }- positions: 2 , 12
Noeuds {A, T } - Arêtes {0-1 }- positions: 2 , 12
Fusion
Nœuds {A, C, T } - Arêtes {0-1 ,0-2 }- positions: 2 , 12
18
Notes:
On continue en suite le reste des piles
<!-- Slide number: 19 -->
Algorithme d’extraction des motifs
Exemple
19
Notes:
<!-- Slide number: 20 -->
Algorithme d’extraction des motifs
Exemple
20
Notes:
La prise en concideration de la sruicture primaire seulement, ne donne que ces deux motifs, plus petit , généralement moins discriùonant
<!-- Slide number: 21 -->
Algorithme d’extraction des motifs
Prise en considération des familles de protéines
Seuil de fréquence intra-famille minimale
Seuil de fréquence extra-famille maximale
21
Notes:
Introduit la notion de seuil …………..
A chaque itération, une classe ayant toutes les freq intrafamille inferieure à ce suils sont élégués
intervient lors du test permettant de prendre la décision si une classe est considérée comme un motif ou non.
<!-- Slide number: 22 -->
Conception
22
Notes:
<!-- Slide number: 23 -->
Conception
Liste des cas d’utilisation
Ajouter les protéines à traiter
Visualiser une protéine en 3D
Extraire les plus longs motifs communs
23
Notes:
<!-- Slide number: 24 -->
Conception
Cas d’utilisation « Ajouter les protéines à traiter »
24
Notes:
<!-- Slide number: 25 -->
Publicité
Conception
Cas d’utilisation «Visualiser une protéine en 3D»
25
Notes:
<!-- Slide number: 26 -->
Conception
Cas d’utilisation «Extraire les plus longs motifs communs»
26
Notes:
<!-- Slide number: 27 -->
Conception
27
Notes:
kmr3D: la classe principale implementant l’algo. Elle permet ainsi d’extraire les motifs les plus
FamilySet: Les infio sur la famille
Les motifs sontdans la classe Motif graph:
<!-- Slide number: 28 -->
Réalisation et tests
28
<!-- Slide number: 29 -->
Réalisation et Tests
Environnement logiciel
L’IDE NetBeans
Librairie JMol
Librairie PGG : Proteine Graph Generator
29
Notes:
<!-- Slide number: 30 -->
Réalisation et Tests
30
Notes:
<!-- Slide number: 31 -->
Réalisation et Tests
Données Réelles
101 protéines de la famille Actinobacteria
70 protéines de la famille Viridiplantae
Comparaison entre graphe et séquence primaire
31
Notes:
-Données relleles téléchargées à partir du site web de la banque de données sur les protéines sous forme de fichiers pdb.
Un seuil= zero designe qu’on utilisera des structures perimaires
Le deux premiers tests permettent d’extraire des motifs rares, à discrimination stricte(car extra =0)
<!-- Slide number: 32 -->
Réalisation et Tests
| Classifieur | Rep. de la protéine | Taux de bonne classification |
| --- | --- | --- |
| C 4.5 | Graphe | 88.88 |
| | Séquence (1D) | 85.38 |
| SVM | Graphe | 92.98 |
| | Séquence (1D) | 82.45 |
| NN | Graphe | 88.30 |
| | Séquence (1D) | 78.36 |
32
Notes:
Support vector machines (SVMs)
<!-- Slide number: 33 -->
Conclusion
Découvrir le domaine bioinformatique
Visualiser les protéines en 3D.
Extraire les motifs selon les seuils définis par l’utilisateur.
Enregistrer les motifs extraits sous forme de graphes.
Générer le fichier de classification correspondant à ces motifs.
33
Notes:
Ce projet m’a permis de s’introduire ds le domaine de la bio info- fouiille , domaine assez vaste
de donnes bviologique
<!-- Slide number: 34 -->
Perspectives
Nous proposons
D’intégrer un module pour proposer les meilleurs seuils
D’intégrer un module pour visualiser les motifs extraits en trois dimensions et les situer graphiquement dans les protéines.
D’intégrer un module pour la classification des protéines en se basant sur les motifs
34
Notes:
<!-- Slide number: 35 -->
Merci de votre temps
35