silico.biotoul.fr
 

M1 BBS Graphes TP Visualisation

From silico.biotoul.fr

Revision as of 18:18, 21 November 2016 by Barriot (Talk | contribs)
Jump to: navigation, search

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. 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.

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     coexpression    YAEE
ABC     coexpression    METK
ABC     coexpression    META
ACCA    coexpression    FABD
ACCA    coexpression    PPA
ACCB    coexpression    HPT
...

coexpression 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).

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

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 (coexpression) YAEE = 831
ABC (coexpression) METK = 590
ABC (coexpression) META = 663
ACCA (coexpression) FABD = 537
ACCA (coexpression) PPA = 543
ACCB (coexpression) HPT = 566
...

Récupérez le fichier contenant les annotations des gènes - EcolA_Genes_Description.noa - et chargez-le (Menu File->Import->Node Attributes) dans Cytoscape. De même, pour les niveaux de confiance sur les liens de coexpression avec le fichier 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 Edit->Preferences->Properties... : pour un lien externe à partir d'un noeud, il faut ajouter une propriété nodelinkouturl.NOM_DU_LIEN, 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 : 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.


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 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.eda.

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 Plugins->Advanced Network Merge. 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
...

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.

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

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, ...). De même, un arc ou une arête peut avoir différents attributs (poids, longueur, couleur, type, ...).

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 :

     weight: 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 ... : pour l'arc de A à B de weight 5 : graph['edges']['A']['B']['weight'] = 5

En d'autres termes :

  • graph['edges'] est un dictionnaire dont les clés sont les sommets source des arcs et dont les valeurs sont des dictionnaires,
  • graph['edges']['A'] 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,
  • graph['edges']['A']['B'] est un dictionnaire permettant de stocker les attributs de l'arc (A,B),
  • graph['edges']['A']['B']['weight'] 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 :

 G = {
   'directed': True,
   'weighted': True,
   'attributes':  { 
       'weight_attribute': 'weight'   
       },
   'nodes': {
      'A': {
         'attributes': {}
         },
      'B': {
         'attributes': {}
         },
   'edges': {
      'A': { 
        'B': 
           'weight': 5
           }
        }
   }

Pour créer un graphe, la librairie python que vous allez développer devrait donc commencer par le code python suivant :

#!/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
 
#############
 
# Percorm tests if not imported by another script
if __name__ == "__main__":
	TP1()
	TP2()