silico.biotoul.fr
 

M1 BBS Graphes TP Visualisation

From silico.biotoul.fr

(Difference between revisions)
Jump to: navigation, search
m (Structures de données et représentation d'un graphe)
m (Statistiques sur le graphe)
 
(36 intermediate revisions not shown)
Line 1: Line 1:
= Données =
= Données =
-
Les données sur lesquelles vous allez travailler provienne de la base de données STRING v8.2. Tout d'abord, '''trouvez''' le site de STRING et '''visualisez''' les partenaires de wbbJ d'''Escherichia coli'' K12-MG1655. Les "boutons" ''confidence'', ''evidence'' et ''actions'' permettent de modifier le rendu du graphe d'interaction en affichant soit des arêtes de tailles reflétant le niveau de confiance du lien, soit des multi-arêtes indiquant les sources de données intervenant dans un lien, soit le type d'interaction. Le bouton ''more'' permet de récupérer davantage de protéines.
+
Les données sur lesquelles vous allez travailler provienne de la base de données STRING v11.0. Tout d'abord, '''trouvez''' le site de STRING et '''visualisez''' les partenaires de ''dnaJ'' d'''Escherichia coli'' K12-MG1655. Le menu ''Settings'' permet de choisir le rendu du graphe avec des des liens ''confidence'' ou ''evidence'' en affichant soit des arêtes de tailles reflétant le niveau de confiance du lien, soit des multi-arêtes indiquant les sources de données intervenant dans un lien, soit le type d'interaction. Dans le même menu, on peut sélectionner le type de sources de données affichées (textmining, experiments, ...). On peut aussi afficher davantage de sommetsavec le bouton ''More''.
 +
 
 +
Dans la partie ''Download'' du site, vous allez récupérer des fichiers pour ''Escherichia coli''. Il faut d'abord restreindre les données à l'organisme considéré. Vous utiliserez la souche K-12 substr. MG1655. Ensuite récupérez :
 +
* le fichier contenant les liens avec les scores détaillés pour chaque type de données : <tt>511145.protein.links.detailed.v11.0.txt.gz</tt>
 +
* le fichier contenant la description des sommets : <tt>511145.protein.info.v11.0.txt.gz</tt>
 +
 
 +
Décompressez-les ensuite pour répondre aux questions suivantes :
 +
* combien de protéines ?
 +
* combien d'arêtes ?
 +
 
 +
Le graphe étant un peu gros pour les exercices qui suivent vous allez filtrez les liens pour ne garder que ceux qui ont un score supérieur ou égal à 700 parmi les types ''neighborhood'', ''coexpression'' et ''experimental''.
 +
 
 +
<!--
 +
cat 511145.protein.links.detailed.v11.0.txt  | awk '{if ($3>=700 ||$6>=700 || $7>=700) {print}}' > 511145.protein.links.filtered.txt
 +
cat 511145.protein.links.detailed.v11.0.txt  | awk '{if ($1<$2 && ($3>=700 ||$6>=700 || $7>=700)) {print}}' > 511145.protein.links.filtered.undirected.txt
 +
-->
= Visualisation avec Cytoscape =
= Visualisation avec Cytoscape =
[http://www.cytoscape.org Cytoscape] est un logiciel de visualisation et d'exploration de graphes. Il a été développé dans le cadre de graphes et réseaux biologiques. Un certain nombre de ''plugins'' ou greffons sont disponibles par exemple pour récupérer/télécharger des voies métaboliques (BioCyc) directement depuis Cytoscape.
[http://www.cytoscape.org Cytoscape] est un logiciel de visualisation et d'exploration de graphes. Il a été développé dans le cadre de graphes et réseaux biologiques. Un certain nombre de ''plugins'' ou greffons sont disponibles par exemple pour récupérer/télécharger des voies métaboliques (BioCyc) directement depuis Cytoscape.
 +
== Import d'un graphe à partir d'un fichier ==
 +
 +
Importez le graphe à partir du menu ''File → import → Network from file...''. Il faut alors dans les paramètres avancés changer le délimiteur de colonnes et ensuite spécifier quels sont les attributs correspondant aux extrémités des arêtes.
 +
 +
<!--
== Importation d'un fichier ''sif'' et algorithmes de dessin==
== Importation d'un fichier ''sif'' et algorithmes de dessin==
-
Vous allez dans un premier temps utiliser un graphe au format [http://cytoscape.org/manual/Cytoscape2_8Manual.html#SIF%20Format sif] (simple interaction format). Il s'agit d'un format de stockage très simple de la forme :
+
Vous allez dans un premier temps utiliser un graphe au format [http://manual.cytoscape.org/en/stable/Supported_Network_File_Formats.html#sif-format SIF] (simple interaction format). Il s'agit d'un format de stockage très simple de la forme :
-
  ABC    coexpression   YAEE
+
  ABC    stringdb   YAEE
-
  ABC    coexpression   METK
+
  ABC    stringdb   METK
-
  ABC    coexpression   META
+
  ABC    stringdb   META
-
  ACCA    coexpression   FABD
+
  ACCA    stringdb   FABD
-
  ACCA    coexpression   PPA
+
  ACCA    stringdb   PPA
-
  ACCB    coexpression   HPT
+
  ACCB    stringdb   HPT
  ...
  ...
-
où ''coexpression'' est le type de l'arête.
+
où ''stringdb'' est le type de l'arête.
'''Récupérez''' le fichier [[Media:String_EcolA_coexpression.sif|String_EcolA_coexpression.sif]] contenant une partie du réseau d'interaction basé sur la co-expression chez ''Escherichia coli'' K12 avec un seuil de 0.5 pour la confiance dans une arête et '''ouvrez'''-le dans Cytoscape (menu <tt>File->Import->Network</tt>).
'''Récupérez''' le fichier [[Media:String_EcolA_coexpression.sif|String_EcolA_coexpression.sif]] contenant une partie du réseau d'interaction basé sur la co-expression chez ''Escherichia coli'' K12 avec un seuil de 0.5 pour la confiance dans une arête et '''ouvrez'''-le dans Cytoscape (menu <tt>File->Import->Network</tt>).
-
Par défaut, les sommets du graphes sont disposés sur une grille. '''Expérimentez''' différents algorithmes de dessin (layout in english donc dans le menu <tt>layout</tt>). Attention, certains ne sont pas adaptés et d'autres plutôt gourmands en temps de calcul.
+
Si le graphe est "gros", les sommets du graphes sont disposés sur une grille. Pour celui-ci, un algorithme de dessin est utilisé pour disposer les sommets. '''Expérimentez''' différents algorithmes de dessin (''layout'' in english donc dans le menu <tt>layout</tt>). Attention, certains ne sont pas adaptés et d'autres plutôt gourmands en temps de calcul.
 +
-->
== Attributs sur les sommets et arêtes ==
== Attributs sur les sommets et arêtes ==
-
Il est possible de charger des attributs associés aux sommets et/ou aux arêtes. Il s'agit là encore d'un format très simple. Pour les attributs portant sur les sommets, il prend la forme suivante :
+
<!--
-
  Description
+
Il est possible de charger des attributs associés aux sommets et/ou aux arêtes. Il s'agit là encore d'un format très simple : du texte de type CSV. Pour les attributs portant sur les sommets, il prend la forme suivante :
-
  AAS = 2-acyl-glycerophospho-ethanolamine acyltransferase; acyl-acyl-carrier protein synthetase
+
  Gene    Description
-
  AAT = leucyl, phenylalanyl-tRNA-protein transferase
+
  AAS     2-acyl-glycerophospho-ethanolamine acyltransferase; acyl-acyl-carrier protein synthetase
-
  ABC = ATP-binding component of a transporter
+
  AAT     leucyl, phenylalanyl-tRNA-protein transferase
 +
  ABC     ATP-binding component of a transporter
  ...
  ...
-
où la première ligne contient le nom de l'attribut. Vous trouverez plus d'information dans la [http://cytoscape.org/manual/Cytoscape2_8Manual.html#Node%20and%20Edge%20Attributes documentation de Cytoscape].
+
où la première ligne contient le nom de l'attribut. Vous trouverez plus d'information dans la [http://manual.cytoscape.org/en/stable/Node_and_Edge_Column_Data.html documentation de Cytoscape].
Pour les arêtes, le format est très similaire :
Pour les arêtes, le format est très similaire :
  coexpression
  coexpression
-
  ABC (coexpression) YAEE = 831
+
  ABC (stringdb) YAEE = 831
-
  ABC (coexpression) METK = 590
+
  ABC (stringdb) METK = 590
-
  ABC (coexpression) META = 663
+
  ABC (stringdb) META = 663
-
  ACCA (coexpression) FABD = 537
+
  ACCA (stringdb) FABD = 537
-
  ACCA (coexpression) PPA = 543
+
  ACCA (stringdb) PPA = 543
-
  ACCB (coexpression) HPT = 566
+
  ACCB (stringdb) HPT = 566
  ...
  ...
 +
-->
-
'''Récupérez''' le fichier contenant les annotations des gènes - [[Media:EcolA_Genes_Description.noa|EcolA_Genes_Description.noa]] - et '''chargez'''-le (Menu <tt>File->Import->Node Attributes</tt>) dans Cytoscape. De même, pour les niveaux de confiance sur les liens de coexpression avec le fichier [[Media:String_EcolA_coexpression.eda|String_EcolA_coexpression.eda]].
 
-
Comme dans la plupart des logiciels et systèmes d'exploitation, un clic droit sur un objet fait apparaître un menu contextuel dans Cytoscape. Un clic droit sur une arête ou un sommet fait apparaître un tel menu. '''Remarquez''' la dernière entrée du menu : ''LinkOut'' qui permet d'ouvrir une URL, typiquement à partir de l'identifiant du sommet ou de l'arête, ce qui permet par exemple d'atteindre la page de description d'une protéine dans UniProt. Il est possible d'ajouter ses propres "liens externes" à partir du menu <tt>Edit->Preferences->Properties...</tt> : pour un lien externe à partir d'un noeud, il faut ajouter une propriété <tt>nodelinkouturl.NOM_DU_LIEN</tt>, par exemple et c'est ce que vous devrez faire <tt>nodelinkouturl.CGDB</tt>. Dans le champ valeur, il s'agit de spécifier l'URL avec une ou plusieurs variables, ici nous utiliserons simple l'identifiant du noeud noté %ID% : <tt><nowiki>http://www-abcdb.biotoul.fr/#/entry/findbestmatch/ID/EcolA.%ID%</nowiki></tt>. Pour les liens sur les arêtes, il s'agit de la propriété <tt>edglelinkouturl.NOM_DU_LIEN</tt> avec %ID1% et %ID2% les extrémités de l'arête, cf. la [http://cytoscape.org/manual/Cytoscape2_8Manual.html#Linkout documentation de Cytoscape] pour plus de détails.
+
Importez le fichier précédemment récupéré <tt>511145.protein.info.v11.0.txt</tt> à partir du menu ''File → import → Table from file...'' en modifiant le délimiteur de colonnes si besoin, '''en précisant bien''' s'il s'agit de données sur les sommets ou les arêtes, et en indiquant quelle colonne permet d'identifier les sommets.
 +
<!--
 +
'''Récupérez''' le fichier contenant les annotations des gènes - [[Media:EcolA_Genes_Description.tab|EcolA_Genes_Description.tab]] - et '''chargez'''-le (Menu <tt>File->Import->Table</tt>) dans Cytoscape. De même, pour les niveaux de confiance sur les liens de coexpression avec le fichier [[Media:String_EcolA_coexpression_scores.attrs|String_EcolA_coexpression_scores.attrs]].
 +
-->
-
== Rendu à partir des valeurs des attributs : ''VizMapper'' ==
+
Comme dans la plupart des logiciels et systèmes d'exploitation, un clic droit sur un objet fait apparaître un menu contextuel dans Cytoscape. Un clic droit sur une arête ou un sommet fait apparaître un tel menu. '''Remarquez''' l'avant-dernière entrée du menu : ''Extrenal Links'' qui permet d'ouvrir une URL, typiquement à partir de l'identifiant du sommet ou de l'arête, ce qui permet par exemple d'atteindre la page de description d'une protéine dans UniProt. Il est possible d'ajouter ses propres "liens externes" à partir du menu ''Edit → Preferences → Properties...'' : pour un lien externe à partir d'un noeud, il faut ajouter une propriété <tt>nodelinkouturl.NOM_DU_LIEN</tt> (dans la section <tt>linkout</tt>), par exemple et c'est ce que vous devrez faire <tt>nodelinkouturl.STRING</tt>. Dans le champ valeur, il s'agit de spécifier l'URL avec une ou plusieurs variables, ici nous utiliserons simple l'identifiant du noeud noté %ID% : <tt><nowiki>https://string-db.org/network/%ID%</nowiki></tt>.  
-
'''Explorez''' à présent les possibilités offertes par l'outil ''VizMapper''. '''Essayez''' notamment de faire afficher des épaisseurs d'arêtes proportionnelles à la confiance du lien de coexpression.
+
 +
Pour les liens sur les arêtes, il s'agit de la propriété <tt>edglelinkouturl.NOM_DU_LIEN</tt> avec %ID1% et %ID2% les extrémités de l'arête, cf. la [http://manual.cytoscape.org/en/stable/Linkout.html documentation de Cytoscape] pour plus de détails.
 +
 +
== Rendu à partir des valeurs des attributs ==
 +
'''Explorez''' à présent les possibilités offertes par l'onglet ''Style'' (à gauche). '''Essayez''' notamment de faire afficher des épaisseurs d'arêtes proportionnelles à la confiance du lien de coexpression ainsi qu'un dégradé reflétant le score de l'attribut ''experimental'' (bleu → jaune par exemple).
== Sélection, filtres et opérations sur les graphes ==
== Sélection, filtres et opérations sur les graphes ==
-
Une boite de recherche est disponible au niveau de la barre d'outil. '''Essayez'''-la pour par exemple sélectionner le gène wbbJ. Il s'agit en fait d'un filtrage sur la sélection de tous les sommets (ou toutes les arêtes). Pour élaborer un filtre plus complexe, vous avez à gauche de la boite de recherche un bouton vous permettant d'éditer les paramètres du filtre. '''Sélectionnez''' toutes les arêtes ayant une valeur de coexpression supérieure à 800. Une fois la sélection réalisée, les boutons encore plus à gauche vous permettent d'extraire un sous graphe à partir de la sélection. Par défaut, il s'agit d'un sous graphe induit par les sommets sélectionnés. Après avoir réalisé la sélection des arêtes >800, le menu <tt>Select->Nodes->Nodes connected by selected edges</tt> vous permet de sélectionner les extrémités des arêtes sélectionnées.
+
Une boite de recherche est disponible au niveau de la barre d'outil. '''Essayez'''-la pour, par exemple, sélectionner le gène wbbJ. Il s'agit en fait d'un filtrage sur la sélection de tous les sommets (ou toutes les arêtes).
-
'''Importez''' à présent le graphe contenu dans le fichier [[Media:String_EcolA_experimental.sif|String_EcolA_experimental.sif]] correspondant aux données STRING portant sur les interactions protéine-protéine. '''Importez''' également la confiance de ces relations à partir du fichier [[Media:String_EcolA_experimental.eda|String_EcolA_experimental.eda]].
+
Pour élaborer un filtre plus complexe, vous avez àsur la gauche l'onglet ''Filter'' vous permettant d'éditer les paramètres du filtre. '''Sélectionnez''' toutes les arêtes ayant une valeur de coexpression ET une valeur experimental supérieures ou égales à 800.
 +
 
 +
Une fois la sélection réalisée, un bouton à gauche de la boite de recherche vous permettent d'extraire un sous graphe à partir de la sélection. Par défaut, il s'agit du sous graphe induit par les sommets sélectionnés : <tt>New Network From Selection (From selected nodes, selected edges)</tt>. Ou alors, après avoir réalisé la sélection des arêtes >=800, le menu ''Select → Nodes → Nodes connected by selected edges'' vous permet de sélectionner les extrémités des arêtes sélectionnées.
 +
 
 +
<!--
 +
'''Importez''' à présent le graphe contenu dans le fichier [[Media:String_EcolA_experimental.sif|String_EcolA_experimental.sif]] correspondant aux données STRING portant sur les interactions protéine-protéine. '''Importez''' également la confiance de ces relations à partir du fichier [[Media:String_EcolA_experimental_scores.attrs|String_EcolA_experimental_scores.attrs]].
 +
 
 +
Vous pouvez fusionner les 2 graphes en utilisant <tt>Tools->Merge->Networks...</tt> en les sélectionnant tous les deux. Une fois cette opération réalisée, '''modifiez''' le rendu pour avoir des épaisseurs d'arêtes proportionnelles à la coexpression et un dégradé de couleur d'arête reflétant la confiance dans le lien d'interaction protéine-protéine.
-
Vous pouvez fusionner les 2 graphes en les sélectionnant tous les deux (maintenir la touche ''Control'' enfoncée) puis en allant dans le menu <tt>Plugins->Advanced Network Merge</tt>. Une fois cette opération réalisée, '''modifiez''' le rendu pour avoir des épaisseurs d'arêtes proportionnelles à la coexpression et un dégradé de couleur d'arête reflétant la confiance dans le lien d'interaction protéine-protéine.
 
== Importation d'un graphe au format ''table''==
== Importation d'un graphe au format ''table''==
Il est également possible d'importer un graphe dans un format tabulé, ce qui permet de charger plusieurs attributs en même temps sur les arêtes. '''Récupérez''' le fichier [[Media:String_EcolA_selection.tab|String_EcolA_selection.tab]] qui contient les deux fichiers précédents ainsi que le score combiné des différentes sources disponibles dans STRING. Le fichier est de la forme :
Il est également possible d'importer un graphe dans un format tabulé, ce qui permet de charger plusieurs attributs en même temps sur les arêtes. '''Récupérez''' le fichier [[Media:String_EcolA_selection.tab|String_EcolA_selection.tab]] qui contient les deux fichiers précédents ainsi que le score combiné des différentes sources disponibles dans STRING. Le fichier est de la forme :
  id1 id2 experimental coexpression combined
  id1 id2 experimental coexpression combined
-
  AAS SECA 546 0 546
+
  AAS SECA 546 0 546
-
  AAS ACPP 653 0 653
+
  AAS ACPP 653 0 653
-
  ABC YAEE 900 831 999
+
  ABC YAEE 900 831 999
-
  ABC METK 0 590 591
+
  ABC METK 0 590 591
-
  ABC META 0 663 663
+
  ABC META 0 663 663
-
  ACCA FABD 0 537 997
+
  ACCA FABD 0 537 997
  ...
  ...
-
= Librairie python pour le traitement de graphes =
+
-->
-
Vous allez réaliser une pseudo-bibliothèque pour les graphes (orientés ou non) que vous allez construire au fur et à mesure de ce TP, du suivant, et du projet pour cette UE.
+
= Statistiques sur le graphe =
-
 
+
Des informations globales sur le graphe peuvent être obtenues ''via'' le menu ''Tools → Analyze network'' comme :
-
Cette librairie va permettre :
+
* le nombre de composantes connexes,
-
* le chargement d'un graphe sous différents formats (SIF et TAB vus précédemment, OBO pour la ''Gene Ontology'' et produits de gènes pour les annotations des gènes en ''GOTerm''),
+
* le nombre moyen de voisins,
-
* le parcours en profondeur (DFS),
+
-
* la détection de cycle/circuit,
+
-
* le tri topologique,
+
-
* le parcours en largeur (BFS),
+
-
* l'identification des plus courts chemin à partir d'un sommet (Bellman-Ford), ou entre toutes les paires de sommets (Floyd-Warshall),
+
* ...
* ...
-
== Structures de données et représentation d'un graphe ==
+
Le résumé apparaît dans une autre sous-fenêtre à droite onglet ''Analyzer''.
-
 
+
-
Pour commencer, il vous faut définir les structures de données que vous allez utiliser pour représenter et traiter des graphes. Un graphe
+
-
* peut avoir différents '''attributs''' (nom, ordre, diamètre, ...),
+
-
* peut être '''orienté''' ou non,
+
-
* peut être '''pondéré''' ou non,
+
-
* possède un '''ensemble de sommets''',
+
-
* possède un '''ensemble d'arcs ou d'arêtes'''.
+
-
 
+
-
De plus, un sommet peut avoir différentes étiquettes ou attributs : identifiant, nom, index, date de passage, couleur, coordonnées (x,y), ''etc.''. De même, un arc ou une arête peut avoir différents attributs : poids, longueur, couleur, type, ''etc.''.
+
-
 
+
-
Un des choix cruciaux va être de choisir le stockage pour les arcs ou arêtes (notés arcs par la suite) : il est possible, par exemple, d'opter pour une '''matrice d'adjacence''' ou des '''listes d'adjacence'''. Si l'on manipule des graphes peu denses, la représentation par listes d'adjacence est préférable.
+
-
 
+
-
Toutes ces informations peuvent être stockées dans un dictionnaire à l'allure suivante (avec la syntaxe python) :
+
-
graph = {
+
-
      'directed':    True/False,
+
-
      'weighted':    True/False,
+
-
      'attributes':  {},
+
-
      'nodes':      {},
+
-
      'edges':      {}
+
-
}
+
-
 
+
-
Les clés ''attributes'', ''nodes'' et ''edges'' pointent elles-mêmes vers des dictionnaires imbriqués.
+
-
 
+
-
Considérons le graphe G très simple suivant constitué de 2 sommets et d'un arc (A,B) ayant un poids de 5 :
+
-
      5
+
-
A ------> B
+
-
 
+
-
Le plus compliqué est le stockage des arcs qui peuvent avoir différents attributs. Le choix proposé est d'utiliser un dictionnaire de dictionnaires de dictionnaires de dictionnaires ... : pour l'arc de A à B de poids 5 :
+
-
<tt>graph['edges']['A']['B']['weight'] = 5</tt>
+
-
 
+
-
En d'autres termes :
+
-
* <tt>graph['edges']</tt> est un dictionnaire dont les clés sont les sommets source des arcs et dont les valeurs sont des dictionnaires,
+
-
* <tt>graph['edges']['A']</tt> est un dictionnaire pour les arcs dont l'extrémité initiale est le sommet A. Ce sommet peut avoir un degré sortant supérieur à 1, donc il faut stocker les extrémités terminales sous forme de dictionnaire. Les clés de ce dictionnaire seront donc les sommets correspondants aux extrémités terminales des sommets dont l'extrémité initiale est A,
+
-
* <tt>graph['edges']['A']['B']</tt> est un dictionnaire permettant de stocker les attributs de l'arc (A,B),
+
-
* <tt>graph['edges']['A']['B']['weight']</tt> est ainsi le poids de l'arc A --> B.
+
-
 
+
-
Ainsi, si un graphe pondéré est chargé, on pourra choisir de stocker le poids des arcs dans les attributs des arcs (accessibles à partir de la clé ''edges'') avec la clé ''weight''.
+
-
Pour G, le dictionnaire pour son stockage aura l'allure suivante :
+
-
<source lang='python'>
+
-
G = {
+
-
  'directed': True,
+
-
  'weighted': True,
+
-
  'attributes':  {
+
-
      'weight_attribute': 'weight' 
+
-
      },
+
-
  'nodes': {
+
-
      'A': {
+
-
        'attributes': {}
+
-
        },
+
-
      'B': {
+
-
        'attributes': {}
+
-
        },
+
-
  'edges': {
+
-
      'A': {
+
-
        'B':
+
-
          'weight': 5
+
-
          }
+
-
        }
+
-
  }
+
-
</source>
+
-
 
+
-
Pour créer un graphe, la librairie python que vous allez développer devrait donc commencer par le code python suivant :
+
-
<source lang='python'>
+
-
#!/usr/bin/python3
+
-
# -*- coding: latin-1 -*-
+
-
 
+
-
from pprint import pprint
+
-
import numpy as np # for Floyd-Warshall matrices
+
-
 
+
-
# TP1 functions
+
-
###############
+
-
 
+
-
 
+
-
def createGraph(directed = True, weighted = False): # TP1
+
-
g = { 'attributes': { 'nb_nodes': 0, 'nb_edges': 0, 'weight_attribute': None }, 'nodes': {}, 'edges': {}, 'directed': directed, 'weighted': weighted }
+
-
return g
+
-
 
+
-
 
+
-
#############
+
-
# TP1 Tests
+
-
 
+
-
def TP1():
+
-
#~ from Graph import createGraph
+
-
pprint('#### createGraph ####')
+
-
G = createGraph()
+
-
pprint(G)
+
-
 
+
-
#############
+
-
# TP2 Tests
+
-
def TP2():
+
-
return
+
-
 
+
-
#############
+
-
 
+
-
# Perform tests if not imported by another script
+
-
if __name__ == "__main__":
+
-
TP1()
+
-
TP2()
+
-
 
+
-
</source>
+
-
 
+
-
Créez le fichier correspondant à votre librairie (par exemple <tt>Graph.py</tt>) et testez-le.
+
-
 
+
-
Il s'agit maintenant de pouvoir ajouter des sommets et des arcs.
+
-
 
+
-
Avant d'ajouter un sommet, il faut s'assurer qu'il n'existe pas déjà :
+
-
<source lang='python'>
+
-
def addNode(g, n, attributes = None): # TP1
+
-
if n not in g['nodes']: # ensure node does not already exist
+
-
if attributes is None: # create empty attributes if not provided
+
-
attributes = {}
+
-
g['nodes'][n] = { 'attributes': attributes } # init attributes
+
-
g['edges'][n] = {} # init edges
+
-
return n
+
-
</source>
+
-
 
+
-
De même, pour ajouter un arc, il faut
+
-
* s'assurer que l'extrémité initiale existe
+
-
* s'assurer que l'extrémité terminale existe
+
-
* s'assurer que l'arc n'existe pas
+
-
* si le graphe n'est PAS orienté, il faut ajouter A --> B et B --> A
+
-
 
+
-
<source lang='python'>
+
-
def addEdge(g, n1, n2, attributes = None): # TP1
+
-
# create nodes if they do not exist
+
-
if n1 not in g['nodes']: addNode(g, n1) # ensure n1 exists
+
-
if n2 not in g['nodes']: addNode(g, n2) # ensure n2 exists
+
-
# add edges ONLY if they do not exist
+
-
if n2 not in g['edges'][n1]:
+
-
if attributes is None: # create empy attributes if not provided
+
-
attributes = {}
+
-
g['edges'][n1][n2] = attributes # set attributes
+
-
if not g['directed']: # add reverse edge if undirected graph
+
-
g['edges'][n2][n1] = g['edges'][n1][n2]
+
-
g['attributes']['nb_edges'] += 1
+
-
return g['edges'][n1][n2]
+
-
</source>
+
-
 
+
-
Chargement d'un fichier au format SIF : il s'agit de
+
-
* créer un graphe (orienté ou non, mais pas pondéré)
+
-
* lire le fichier ligne par ligne, et pour chacune ligne : ajout des sommets et des arcs
+
-
 
+
-
<source lang='python'>
+
-
def loadSIF(filename, directed=True, header=True): # TP1
+
-
# line syntax: nodeD <relationship type> nodeE nodeF nodeB
+
-
g = createGraph(directed)
+
-
with open(filename) as f: # OPEN FILE
+
-
if header: # SKIP COLUMNS NAMES IF header
+
-
trash = f.readline()
+
-
# PROCESS THE REMAINING LINES
+
-
row = f.readline().rstrip()
+
-
while row:
+
-
vals = row.split('\t')
+
-
att = { 'type': vals[1] } # set edge type
+
-
for i in range(2, len(vals)):
+
-
addEdge(g, vals[0], vals[i], att)
+
-
row = f.readline().rstrip()
+
-
return g
+
-
</source>
+
-
 
+
-
Vous pourrez tester ces fonction sue le fichier [[Media:M1MBBS Graphe dressing.sif|dressing.sif]] avec la fonction TP1() suivante :
+
-
<source lang='python'>
+
-
def TP1():
+
-
print('#### createGraph ####')
+
-
G = createGraph()
+
-
pprint(G)
+
-
 
+
-
print('## Adding node A')
+
-
addNode(G,'A')
+
-
pprint(G)
+
-
 
+
-
print('## Adding edge A -> B')
+
-
addEdge(G, 'A', 'B')
+
-
pprint(G)
+
-
 
+
-
print('## #Loading SIF file dressing.sif')
+
-
G = loadSIF('dressing.sif')
+
-
pprint(G)
+
-
</source>
+
-
 
+
-
 
+
-
'''Implémentez et testez''' ensuite le parcours en profondeur dont on vous rappelle l'algorithme :
+
-
 
+
-
  DFS(G)
+
-
    '''for each''' vertex u <math>\in</math> V(G)
+
-
      '''do''' color[u] <math>\leftarrow</math> WHITE
+
-
        pred[u]  <math>\leftarrow</math> NIL
+
-
    time <math>\leftarrow</math> 0
+
-
    '''for each''' vertex u <math>\in</math> V(G)
+
-
      '''do if''' color[u] = WHITE
+
-
        '''then''' DFS-VISIT(u)
+
-
  DFS-VISIT(u)
+
-
    color[u] <math>\leftarrow</math> GRAY
+
-
    time <math>\leftarrow</math> time + 1
+
-
    d[u] <math>\leftarrow</math> time
+
-
    '''for each''' vertex v <math>\in</math> Adj[u]
+
-
      '''do if''' color[v] = WHITE
+
-
        '''then''' pred[v] <math>\leftarrow</math> u
+
-
            DFS-VISIT(v)
+
-
            class[ (u,v) ] <math>\leftarrow</math> TREE EDGE
+
-
        '''else if''' color[v] = GRAY
+
-
            '''then''' class[ (u,v) ] <math>\leftarrow</math> BACK EDGE
+
-
            '''else if''' d[u] > d[v]
+
-
                  '''then''' class[ (u,v) ] <math>\leftarrow</math> CROSS EDGE
+
-
                  '''else''' class[ (u,v) ] <math>\leftarrow</math> FORWARD EDGE
+
-
    color[u] <math>\leftarrow</math> BLACK
+
-
    time <math>\leftarrow</math> time + 1
+
-
    f[u] <math>\leftarrow</math> time
+
-
 
+
-
 
+
-
'''Implémentez et testez''' la méthode <tt>isAcyclic()</tt> qui renvoie vrai ou faux selon que le graphe est sans circuit ou non.
+
-
'''Implémentez et testez''' la méthode <tt>topologicalSort()</tt> qui renvoie les sommets du graphes en ayant effectué un tri topologique.
+
'''Observez''' les attributs supplémentaires des sommets et arêtes.
-
Autres fichiers :
+
'''Modifiez''' l'apparence du graphe pour colorer les sommets en fonction de leur coefficient d'agglomération.
-
* [[Image:directed.graph.with.cycle.slide29.png|thumb|100px|directed.graph.with.cycle.slide29]] [[File:directed.graph.with.cycle.slide29.sif]]
+

Current revision as of 16:53, 16 November 2020

Contents

Données

Les données sur lesquelles vous allez travailler provienne de la base de données STRING v11.0. Tout d'abord, trouvez le site de STRING et visualisez les partenaires de dnaJ d'Escherichia coli K12-MG1655. Le menu Settings permet de choisir le rendu du graphe avec des des liens confidence ou evidence en affichant soit des arêtes de tailles reflétant le niveau de confiance du lien, soit des multi-arêtes indiquant les sources de données intervenant dans un lien, soit le type d'interaction. Dans le même menu, on peut sélectionner le type de sources de données affichées (textmining, experiments, ...). On peut aussi afficher davantage de sommetsavec le bouton More.

Dans la partie Download du site, vous allez récupérer des fichiers pour Escherichia coli. Il faut d'abord restreindre les données à l'organisme considéré. Vous utiliserez la souche K-12 substr. MG1655. Ensuite récupérez :

  • le fichier contenant les liens avec les scores détaillés pour chaque type de données : 511145.protein.links.detailed.v11.0.txt.gz
  • le fichier contenant la description des sommets : 511145.protein.info.v11.0.txt.gz

Décompressez-les ensuite pour répondre aux questions suivantes :

  • combien de protéines ?
  • combien d'arêtes ?

Le graphe étant un peu gros pour les exercices qui suivent vous allez filtrez les liens pour ne garder que ceux qui ont un score supérieur ou égal à 700 parmi les types neighborhood, coexpression et experimental.


Visualisation avec Cytoscape

Cytoscape est un logiciel de visualisation et d'exploration de graphes. Il a été développé dans le cadre de graphes et réseaux biologiques. Un certain nombre de plugins ou greffons sont disponibles par exemple pour récupérer/télécharger des voies métaboliques (BioCyc) directement depuis Cytoscape.

Import d'un graphe à partir d'un fichier

Importez le graphe à partir du menu File → import → Network from file.... Il faut alors dans les paramètres avancés changer le délimiteur de colonnes et ensuite spécifier quels sont les attributs correspondant aux extrémités des arêtes.


Attributs sur les sommets et arêtes

Importez le fichier précédemment récupéré 511145.protein.info.v11.0.txt à partir du menu File → import → Table from file... en modifiant le délimiteur de colonnes si besoin, en précisant bien s'il s'agit de données sur les sommets ou les arêtes, et en indiquant quelle colonne permet d'identifier les sommets.

Comme dans la plupart des logiciels et systèmes d'exploitation, un clic droit sur un objet fait apparaître un menu contextuel dans Cytoscape. Un clic droit sur une arête ou un sommet fait apparaître un tel menu. Remarquez l'avant-dernière entrée du menu : Extrenal Links qui permet d'ouvrir une URL, typiquement à partir de l'identifiant du sommet ou de l'arête, ce qui permet par exemple d'atteindre la page de description d'une protéine dans UniProt. Il est possible d'ajouter ses propres "liens externes" à partir du menu Edit → Preferences → Properties... : pour un lien externe à partir d'un noeud, il faut ajouter une propriété nodelinkouturl.NOM_DU_LIEN (dans la section linkout), par exemple et c'est ce que vous devrez faire nodelinkouturl.STRING. Dans le champ valeur, il s'agit de spécifier l'URL avec une ou plusieurs variables, ici nous utiliserons simple l'identifiant du noeud noté %ID% : https://string-db.org/network/%ID%.

Pour les liens sur les arêtes, il s'agit de la propriété edglelinkouturl.NOM_DU_LIEN avec %ID1% et %ID2% les extrémités de l'arête, cf. la documentation de Cytoscape pour plus de détails.

Rendu à partir des valeurs des attributs

Explorez à présent les possibilités offertes par l'onglet Style (à gauche). Essayez notamment de faire afficher des épaisseurs d'arêtes proportionnelles à la confiance du lien de coexpression ainsi qu'un dégradé reflétant le score de l'attribut experimental (bleu → jaune par exemple).

Sélection, filtres et opérations sur les graphes

Une boite de recherche est disponible au niveau de la barre d'outil. Essayez-la pour, par exemple, sélectionner le gène wbbJ. Il s'agit en fait d'un filtrage sur la sélection de tous les sommets (ou toutes les arêtes).

Pour élaborer un filtre plus complexe, vous avez àsur la gauche l'onglet Filter vous permettant d'éditer les paramètres du filtre. Sélectionnez toutes les arêtes ayant une valeur de coexpression ET une valeur experimental supérieures ou égales à 800.

Une fois la sélection réalisée, un bouton à gauche de la boite de recherche vous permettent d'extraire un sous graphe à partir de la sélection. Par défaut, il s'agit du sous graphe induit par les sommets sélectionnés : New Network From Selection (From selected nodes, selected edges). Ou alors, après avoir réalisé la sélection des arêtes >=800, le menu Select → Nodes → Nodes connected by selected edges vous permet de sélectionner les extrémités des arêtes sélectionnées.


Statistiques sur le graphe

Des informations globales sur le graphe peuvent être obtenues via le menu Tools → Analyze network comme :

  • le nombre de composantes connexes,
  • le nombre moyen de voisins,
  • ...

Le résumé apparaît dans une autre sous-fenêtre à droite onglet Analyzer.

Observez les attributs supplémentaires des sommets et arêtes.

Modifiez l'apparence du graphe pour colorer les sommets en fonction de leur coefficient d'agglomération.