M1 MABS Graphes TP Visualisation et parcours en profondeur
From silico.biotoul.fr
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)