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 (Importation d'un fichier sif et algorithmes de dessin)
(20 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 v8.2. Tout d'abord, '''trouvez''' le site de STRING et '''visualisez''' les partenaires de wbbJ d'''Escherichia coli'' K12-MG1655. Le menu ''View 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. Le menu ''Data Settings'' permet de changer les paramètres de sélection des sommets et arêtes, notamment de récupérer davantage de protéines.
= Visualisation avec Cytoscape =
= Visualisation avec Cytoscape =
Line 8: Line 8:
== 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 :
+
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 :
-
  Description
+
  Gene    Description
-
  AAS = 2-acyl-glycerophospho-ethanolamine acyltransferase; acyl-acyl-carrier protein synthetase
+
  AAS     2-acyl-glycerophospho-ethanolamine acyltransferase; acyl-acyl-carrier protein synthetase
-
  AAT = leucyl, phenylalanyl-tRNA-protein transferase
+
  AAT     leucyl, phenylalanyl-tRNA-protein transferase
-
  ABC = ATP-binding component of a transporter
+
  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]].
+
'''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]].
-
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.
+
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 <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> (dans la section <tt>linkout</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://manual.cytoscape.org/en/stable/Linkout.html documentation de Cytoscape] pour plus de détails.
-
 
+
-
== Rendu à partir des valeurs des attributs : ''VizMapper'' ==
+
-
'''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.
+
 +
== 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.
== 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). Pour élaborer un filtre plus complexe, vous avez à gauche l'onglet ''Select'' 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, 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 (all edges)</tt>. 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.
-
'''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]].
+
'''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 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.
+
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.
== 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 =
+
= Statistiques sur le graphe =
-
 
+
Des informations globales sur le graphe peuvent être obtenues ''via'' le menu <tt>Tools->NetwortkAnalyzer->Network Analysis->Analyse Network...</tt> comme :
-
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.
+
* le nombre de composantes connexes,
-
 
+
* le nombre moyen de voisins,
-
Cette librairie va permettre :
+
-
* 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 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 ==
+
'''Observez''' les attributs supplémentaires des sommets et arêtes.
-
 
+
-
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>
+
-
 
+
-
== Parcours en profondeur et applications ==
+
-
 
+
-
'''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.
+
-
 
+
-
Autres fichiers :
+
-
* [[Image:directed.graph.with.cycle.slide29.png|thumb|100px|directed.graph.with.cycle.slide29]] [[File:directed.graph.with.cycle.slide29.sif]]
+
-
 
+
-
 
+
-
 
+
-
== Parcours en largeur ==
+
-
Algorithme :
+
-
BFS(G, s)
+
-
  '''for each''' vertex u <math>\in</math> V(G)
+
-
    '''do''' color[u] <math>\leftarrow</math> WHITE
+
-
        d[u] <math>\leftarrow</math> <math>\infty</math>
+
-
        <math>\pi</math>[u] <math>\leftarrow</math> NIL
+
-
  color[s] <math>\leftarrow</math> GRAY
+
-
  d[s] <math>\leftarrow</math> 0
+
-
  Q <math>\leftarrow</math> <math>\empty</math>
+
-
  enqueue(Q, s)
+
-
  '''while''' Q <math>\ne</math> <math>\empty</math>
+
-
    '''do''' u <math>\leftarrow</math> dequeue(Q)
+
-
      '''for each''' vertex v <math>\in</math> Adj[u]
+
-
        '''do if''' color[v] = WHITE
+
-
          '''then''' color[v] <math>\leftarrow</math> GRAY
+
-
                d[v] <math>\leftarrow</math> d[u] + 1
+
-
                <math>\pi</math>[v] <math>\leftarrow</math> u
+
-
                enqueue(Q, v)
+
-
      color[u] <math>\leftarrow</math> BLACK
+
-
 
+
-
'''Charger''' le graphe utilisé précédemment ([[Media:M1BBS Graphe dressing.sif]]), et effectuer un parcours en largeur depuis sous-vetements.
+
-
 
+
-
== Plus court chemin - Bellman-Ford ==
+
-
Rappel de l'algorithme:
+
-
  INITIALIZE-SINGLE-SOURCE(G, s)
+
-
    '''for each''' vertex v <math>\in</math> V(G)
+
-
      '''do''' d[v] <math>\leftarrow</math> <math>\infty</math>
+
-
        <math>\pi</math>[v] <math>\leftarrow</math> NIL
+
-
    d[s] <math>\leftarrow</math> 0
+
-
  RELAX(u, v, w)
+
-
    '''if''' d[v] > d[u] + w(u, v)
+
-
      '''then''' d[v] = d[u] + w(u,v)
+
-
          <math>\pi</math>[v] <math>\leftarrow</math> u
+
-
  BELLMAN-FORD(G, s, w)
+
-
    INITIALIZE-SINGLE-SOURCE(G, s)
+
-
    '''for''' i <math>\leftarrow</math> 1 '''to''' |V(G)| - 1
+
-
      '''do for each''' edge (u,v) <math>\in</math> E(G)
+
-
        '''do''' RELAX(u, v, w)
+
-
 
+
-
'''Ajoutez''' la méthode à votre librairie et testez la sur le graphe [[File:M1BBS Graphe Bellman-Ford.tab]] à partir du sommet A.
+
-
 
+
-
Afin de gagner du temps, la méthode <tt>loadTAB</tt> vous est fournie :
+
-
<source lang='python'>
+
-
def loadTAB(self, filename):
+
-
"""
+
-
Loads a graph in Cytoscape tab format
+
-
Assumed input:
+
-
  id1 id2 weight color ...
+
-
  A B 6 blue ...
+
-
"""
+
-
with open(filename) as f:
+
-
# GET COLUMNS NAMES
+
-
tmp = f.readline().rstrip()
+
-
attNames= tmp.split('\t')
+
-
# REMOVES FIRST TWO COLUMNS WHICH CORRESPONDS TO THE LABELS OF THE CONNECTED VERTICES
+
-
attNames.pop(0)
+
-
attNames.pop(0)
+
-
# PROCESS THE REMAINING LINES
+
-
row = f.readline().rstrip()
+
-
while row:
+
-
vals = row.split('\t')
+
-
v1 = vals.pop(0)
+
-
v2 = vals.pop(0)
+
-
att = {}
+
-
for i in xrange(len(attNames)):
+
-
att[ attNames[i] ] = vals[i]
+
-
self.addEdge(v1, v2, att)
+
-
row = f.readline().rstrip() # NEXT LINE
+
-
</source>
+
-
 
+
-
== Plus courts chemins - Floyd-Warshall ==
+
-
Pour l'agorithme suivant,
+
-
* D[x,y] est la distance du plus court chemin entre les sommets x et y
+
-
* N[x,y] est le successeur de x dans le plus court chemin allant de x à y
+
-
* W[x,y] est la valuation de l'arc (x,y)
+
-
 
+
-
Algorithme :
+
-
initialiser D = W, et N à partir des arcs/arêtes du graphe
+
-
pour k de 1 à n
+
-
    pour i de 1 à n
+
-
      pour j de 1 à n
+
-
          si D[i,k] + D[k,j] < D[i,j] alors
+
-
            D[i,j] = D[i,k] + D[k,j]
+
-
            N[i,j] = N[i,k]
+
-
 
+
-
Récupération du plus court chemin à partir de la matrice N :
+
-
plusCourtChemin(D,N, i,j)
+
-
    si D[i,j] est infinie alors
+
-
      il n'y a pas de chemin entre i et j
+
-
    chemin = initialiserChemin(i)
+
-
    k = N[i,j]
+
-
    tant que k est défini faire
+
-
      ajouter(chemin, k)
+
-
      k = N[k,j]
+
-
    ajouter(chemin, j)
+
-
 
+
-
'''Implémentez''' les méthodes FloydWarshall(W) et FloydWarshallPath(source, destination) dans votre librairie. Pour cela, vous êtes forcement incité(e) à ajouter une méthode ''adjacencyMatrix'' qui renvoie le graphe source forme de matrice d'adjacence.
+
-
 
+
-
 
+
-
'''Testez''' ces méthodes sur le graphe [[File:M1BBS Graphe Floyd-Warshall.tab]] et '''affichez''' les plus courts chemins de A à C et de A à B (avec leur longueur).
+
-
Quel est le diamètre du graphe ? '''Affichez''' le chemin correspondant.
+
'''Modifiez''' l'apparence du graphe pour colorer les arêtes en fonction de leur centralité (bouton <tt>Visualize Parameters</tt> de la fenêtre de résultats).

Revision as of 09:58, 18 November 2019

Contents

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. Le menu View 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. Le menu Data Settings permet de changer les paramètres de sélection des sommets et arêtes, notamment de récupérer davantage de protéines.

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.

Importation d'un fichier sif et algorithmes de dessin

Vous allez dans un premier temps utiliser un graphe au format SIF (simple interaction format). Il s'agit d'un format de stockage très simple de la forme :

ABC     stringdb    YAEE
ABC     stringdb    METK
ABC     stringdb    META
ACCA    stringdb    FABD
ACCA    stringdb    PPA
ACCB    stringdb    HPT
...

stringdb est le type de l'arête.

Récupérez le fichier 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 File->Import->Network).

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 layout). Attention, certains ne sont pas adaptés et d'autres plutôt gourmands en temps de calcul.

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 : du texte de type CSV. Pour les attributs portant sur les sommets, il prend la forme suivante :

Gene    Description
AAS     2-acyl-glycerophospho-ethanolamine acyltransferase; acyl-acyl-carrier protein synthetase
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 documentation de Cytoscape.

Pour les arêtes, le format est très similaire :

coexpression
ABC (stringdb) YAEE = 831
ABC (stringdb) METK = 590
ABC (stringdb) META = 663
ACCA (stringdb) FABD = 537
ACCA (stringdb) PPA = 543
ACCB (stringdb) HPT = 566
...

Récupérez le fichier contenant les annotations des gènes - EcolA_Genes_Description.tab - et chargez-le (Menu File->Import->Table) dans Cytoscape. De même, pour les niveaux de confiance sur les liens de coexpression avec le fichier String_EcolA_coexpression_scores.attrs.

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.CGDB. 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% : http://www-abcdb.biotoul.fr/#/entry/findbestmatch/ID/EcolA.%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.

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 l'onglet Select 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, 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 (all edges). 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 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 String_EcolA_experimental_scores.attrs.

Vous pouvez fusionner les 2 graphes en utilisant Tools->Merge->Networks... 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.

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 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
AAS	SECA	546		0		546
AAS	ACPP	653		0		653
ABC	YAEE	900		831		999
ABC	METK	0		590		591
ABC	META	0		663		663
ACCA	FABD	0		537		997
...

Statistiques sur le graphe

Des informations globales sur le graphe peuvent être obtenues via le menu Tools->NetwortkAnalyzer->Network Analysis->Analyse Network... comme :

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

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

Modifiez l'apparence du graphe pour colorer les arêtes en fonction de leur centralité (bouton Visualize Parameters de la fenêtre de résultats).