silico.biotoul.fr
 

M1 MABS Graphes TP Visualisation et parcours en profondeur

From silico.biotoul.fr

(Difference between revisions)
Jump to: navigation, search
m
m
Line 26: Line 26:
= Parcours en profondeur d'un graphe =
= Parcours en profondeur d'un graphe =
-
On rappelle l'algorithme récursif
 
-
<source lang="ada">
 
-
dfs(UndirectedGraph g, Vertex v)
 
-
  mark(s)
 
-
  for each Neighbor n of v do
 
-
      if not marked(n) then
 
-
        dfs(g, n)
 
-
</source>
 
-
 
implémenter en python
implémenter en python
Line 64: Line 55:
besoin de récupérer les voisins d'un sommet
besoin de récupérer les voisins d'un sommet
 +
 +
pour la représentation interne, liberté de choix :
 +
* matrice d'adjacence
 +
* listes d'adjacence
 +
 +
fonction à définir :
 +
* createGraph
 +
* addNode
 +
* addEdge
 +
* getNeighbors
 +
 +
Après chargement du graphe, faire afficher l'ordre du graphe ainsi que le nombre d'arête.
 +
 +
Implémenter DFS
 +
 +
On rappelle l'algorithme récursif
 +
<source lang="ada">
 +
dfs(UndirectedGraph g, Vertex v)
 +
  mark(s)
 +
  for each Neighbor n of v do
 +
      if not marked(n) then
 +
        dfs(g, n)
 +
</source>

Revision as of 15:10, 6 February 2012

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.

format sif string experimental

layout

attributs node/edge annotation des gènes confidence

vizzmapper


selection

string coexpression merge

format table string selection

Parcours en profondeur d'un graphe

implémenter en python

procédure pour charger le graphe à partir du fichier au format table 

def loadGraph(filename):
	UG = createGraph()
	# OPEN FILE
	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)
			addNode(UG, v1)
			addNode(UG, v2)
			addEdge(UG, v1, v2, attNames, vals)
			row = f.readline().rstrip()
	return UG


besoin de récupérer les voisins d'un sommet

pour la représentation interne, liberté de choix :

  • matrice d'adjacence
  • listes d'adjacence

fonction à définir :

  • createGraph
  • addNode
  • addEdge
  • getNeighbors

Après chargement du graphe, faire afficher l'ordre du graphe ainsi que le nombre d'arête.

Implémenter DFS

On rappelle l'algorithme récursif 

dfs(UndirectedGraph g, Vertex v)
   mark(s)
   for each Neighbor n of v do
      if not marked(n) then
         dfs(g, n)
Retrieved from "http://silico.biotoul.fr/p/M1_MABS_Graphes_TP_Visualisation_et_parcours_en_profondeur"