From silico.biotoul.fr

Revision as of 13:52, 3 February 2015

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

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

Parcours en profondeur d'un graphe

Il s'agit à présent d'implémenter le parcours en profondeur (DFS) d'un graphe en python.

Pour cela, vous allez réaliser une bibliothèque pour les graphes (orientés ou non). Pour DFS, vous allez implémenter le diagramme de classes suivant :

Ceci se traduit en python par le squelette suivant :

#!/usr/bin/python
# -*- coding: latin-1 -*-
 
class Node(object):
	def __init__(self, id, attributes = {}):
		self.id = str(id)
		self.attributes = attributes
		self.neighbors = []  # list of neighbors id (ajacency list implementation)
 
	def dump(self):
		print "  id: %s, attributes: %s, neighbors: %s" % (self.id, self.attributes, ','.join(self.neighbors))
 
class Edge(object):
	def __init__(self, source, destination, attributes = {}):
		self.source      = source
		self.destination = destination
		self.attributes  = attributes
 
	def dump(self):
		print "  %s -- %s , attributes: %s" % (self.source.id, self.destination.id, self.attributes)
 
class Graph(object):
	# constructor
	def __init__(self):
		self.attributes = {}
		self.nodesById  = {}
		self.edges      = []
 
	def dump(self):
		print "Nodes"
		for n in self.nodes(): n.dump()
		print
		print "Edges"
		for e in self.edges: e.dump()
		print
 
	# modifiers
	###########
	def addNode(self, node, attributes = None):
		# TO DO
		return
 
	# accessors
	###########
	def node(self, obj): # convert node id or node to node (to ensure we have a node)
		# TO DO
		return None
 
	def nodes(self): # get all nodes as a vector
		# TO DO
		return None
 
	def neighbors(self, node):
		# TO DO
		return None
 
	# traversal
	###########
	def dfs(self):
		# TO DO
		return None
 
	# input
	#######
	def loadSIF(self, filename):
		# TO DO
		return None
 
class DirectedGraph(Graph):
	# constructor
	def __init__(self):
		super(DirectedGraph, self).__init__()
 
	# modifiers
	###########
	def addEdge(self, source, destination, attributes = None):
		# TO DO
		return None
 
	# accessors
	###########
	def isDirected(self):
		# TO DO
		return None
 
	def edge(self, source, destination):
		# TO DO
		return None
 
# TESTS
if __name__ == "__main__":
	g=DirectedGraph()
	# TO DO: LoadSIF
	# g.loadSIF('dressing.sif')
	# g.dump()
	# TO DO: DFS
	# g.dfs()
	# g.dump()
	# TO DO: Topological sort
	# nodes = g.topologicalSort()

Copiez le code ci-dessus dans un fichier Graph.py qui correspondra à votre librairie et testez le.

Ajoutez la méthode loadSIF() pour pouvoir charger un fichier au format SIF (simplifié) :

		# OPEN FILE
		with open(filename) as f: 
			# SKIP COLUMNS NAMES
			tmp = f.readline()
			# PROCESS THE REMAINING LINES
			row = f.readline().rstrip()
			while row:
				vals = row.split('\t')
				self.addEdge(vals[0], vals[2])
				row = f.readline().rstrip()

Pour cela, vous aurez besoin d'implémenter les méthodes addEdge et addNode.

Implémenter ensuite le parcours en profondeur dont on vous rappelle l'algorithme :

DFS(G)
  for each vertex u in V(G)
    do color[u] <- white
       pred[u]  <- NIL
  time <- 0
  for each vertex u in V(G)
    do if color[u] = white
      then DFS-VISIT(u)
DFS-VISIT(u)
  color[u] <- gray
  time <- time + 1
  d[u] <- time
  for each vertex v in Adj[u]
    do if color[v] = white
       then pred[v] <- u
            DFS-VISIT(v)
            class[ (u,v) ] <- tree edge
       else if color[v] = gray
            then class[ (u,v) ] <- back edge
            else if d[u] > d[v]
                 then class[ (u,v) ] <- cross edge
                 else class[ (u,v) ] <- forward edge
  color[u] <- black
  time <- time + 1
  f[u] <- time

Ajouter une méthode topologicalSort() qui renvoie les sommets du graphes en ayant effectué un tri topologique.