User Tools

Site Tools


marajo_veyssiere:paul_maheva_marajo_maeva_veyssiere

Visual Analytics Course

Bordeaux roadmap 2013- 2014 / Mahéva Marajo & Maeva Veyssiere's corner

Centralité basée sur les motifs

Introduction


Dans le cadre de notre UE Biovisualisation, nous avons eu comme projet la mise en œuvre d'un algorithme de visualisation basé sur un article scientifique.
Notre article « Ranking of network elements based on functional substructures » traite de l'analyse de la centralité d'un réseau biologique basée sur des motifs.

La centralité permet d'identifier et de classer les éléments clés d'un réseau en fonction de de leur caractéristique. C'est une fonction qui attribut à chaque nœud un nombre réel qui déterminera l'importance du nœud. Les nœuds peuvent donc être classés selon leur valeur de centralité.

Les réseaux sont représentés par un graphe orienté. Les motifs sont des petits sous-graphes récurrents dans un graphe. Un réseau de motifs est un ensemble des motifs correspondant à un motif donné. L'analyse du réseau de motifs est importante pour l'étude des réseaux biologiques. En effet, la présence d'un motif dans un réseau particulier serait une indication sur les fonctions de ce réseau.

La combinaison de l'analyse des motifs et du concept de centralité permettrait une analyse plus spécifique des propriétés fonctionnelles.

1. La centralité

1.1. Basée sur les motifs

La centralité basée sur les motifs correspond au nombre de fois où un noeud est impliqué dans une occurrence du motif étudié, dans le réseau. Plus cette centralité est grande plus le noeud (et l'entité qu'il représente) joue un rôle important dans le réseau.

1.2. Basée sur les motifs et les rôles

Les nœuds des motifs peuvent représenter différentes fonctions. C'est différentes fonctions s'appellent les rôles. Une fonction rôle attribut à chaque nœud un rôle et alors la fonction centralité va à nouveau attribuer à chaque nœud le nombre de ces correspondances mais pour un rôle donnée.
On aura la centralité de chaque nœud pour tous les rôles possibles et l'on pourra donc déterminer les nœuds les plus susceptible d'avoir certains rôles.

1.3. Basée sur les motifs et les rôles pour des classes de motifs

Il est possible d'attribuer le même rôle à des nœuds ayant les mêmes caractéristiques. La centralité sera donc basée sur une classe de motifs. Une classe de motif est représentée par l différents motifs. La centralité est définie par la somme des centralités des l différents motifs de la classe de motifs.

2. Implémentation de l'algorithme

2.1. La recherche de motif

Afin de trouver toutes les correspondances (patterns) du motif dans un graphe, il a été choisi de commencer par rechercher les patterns de plus petite taille (1 arête) puis d'augmenter la taille jusqu'à obtenir des patterns correspondant au motif recherché dans son ensemble.

2.1.1. Initialisation

Pour récupérer les patterns de taille i (nombre d'arêtes de 0 à n, où n est le nombre d'arêtes du motif), un arbre qui contient tous les patterns du motif est construit [fonction patternTree(currentGraph,t)].
Chaque noeud de cet arbre contient un pattern, sur un même niveau se trouvent tous les patterns de taille i.
Un pattern est implémenté sous la forme d'un objet qui a pour attributs : une liste d'arêtes et une liste de patterns (de taille +1 arête).

Une lecture en largeur de cet arbre [fonction read()] permet de créer une liste de pattern par niveau. Il faut créer en parallèle une liste contenant tous les patterns de taille 1 du graphe, ce qui correspond à toutes les arêtes de ce graphe.

2.1.2. Recherche des patterns de taille 2 à n arêtes dans le graphe

Dans un premier temps, il faut rechercher tous les patterns de taille n i dans le graphe. Pour cela, il est créé autant de nouveaux patterns qu'il y a d'arêtes incidentes aux patterns de taille n-1.

Chacun de ces nouveaux patterns est ensuite comparé à ceux de même taille dans le motif.
Le but est alors de trouver un equivalent de chaque noeud du pattern de graphe dans le pattern du motif comparé. Deux noeuds sont déterminés équivalents s'ils ont le même nombre d'arêtes entrantes et sortantes dans le pattern considéré.
C'est pourquoi, les noeuds et arêtes qui seront ensuite étudiées, le seront seulemnt pour des sous-graphes du graphe et du motif.

 Figure 1
Figure 1 : Recherche d'un motif dans un graphe. L'occurence est en bleu

Quand la taille de pattern maximum (n) a été atteinte, la dernière liste renvoyée ne contient que les patterns du graphe qui correspondent au motif dans son ensemble.

2.1.3 Classe de motifs

Lorsqu'une classe de motif est recherchée, la recherche est répétées pour chaque motif de la classe et chaque pattern correspondant est stocké dans une liste.

2.2. Le calcul de centralité

2.2.1.Totale

A chaque fois qu'un nœud est impliqué dans un pattern correspondant au motif, sa centralité augmente de 1. Ce calcul a été appliqué sur la figure 2, et les résultats ont été consignés dans le Tableau 1.

Vertex Centralité cmc
v0 1
v1 3
v2 2
v3 2
v4 1
Tableau 1 : Résultats du calcul de la centralité sur la Figure 2
2.2.2. Par rôle

Il est attribué à chaque nœud du graphe un dictionnaire qui contiendra la centralité totale, ainsi que la centralité par rôle. Le rôle d'un nœud dans un graphe est déterminé par le nombre d'arêtes entrantes et sortantes de ce dernier. Quand les conditions sont réunies, la centralité de chaque nœud augmente de 1 pour le rôle correspondant.

Le motif FFL :
Il a été déterminé que pour ce motif, le rôle A correspond aux nœuds qui ont deux arêtes sortantes ,le rôle B aux nœuds ayant une arête entrante et une arête sortante et le rôle C aux nœuds ayant deux arêtes entrantes.

 Figure2
Figure 2 : Recherche d'un motif de type FFL, 3 occurrences ont été trouvées
Centralité cemc
Vertex Rôle A Rôle B Rôle C
v0 1 0 0
v1 2 1 0
v3 0 1 1
v4 0 0 2
v5 0 1 0
Tableau 2 : Résultats du calcul de la centralité sur la Figure 2 pour un motif de type FFL
2.2.3. Par classe

Dans notre exemple, chaque motif de la classe SIM est représenté par le nombre de nœuds qui le compose. Une dimension est donc ajoutée à la recherche par rôle.

Le motif SIM :
Le rôle étudié dans notre exemple est le rôle A. Un nœud ayant ce rôle est défini comme n'ayant aucune arête entrante.

 Figure 3
Figure 3 : Recherche de motifs de type SIM

Ces calculs ont été appliqués sur la figure 3 et les résultats ont été consignés dans le Tableau 3. Quand un motif ne peut être obtenu à partir d'un vertex, la valeur de centralité correspondante est inexistante. Elle a été mise à “0” dans le tableau de résultat.

Centralité
Taille de la chaîne ( nombre de noeuds)
Vertex cmcc 2 3 4 5 6
v0 8 1 2 2 2 1
v1 7 2 2 2 1 0
v3 2 1 1 0 0 0
v4 1 1 0 0 0 0
v5 3 1 1 1 0 0
v6 2 1 1 0 0 0
v7 0 0 0 0 0 0
Tableau 3 : Résultats du calul de la centralité pour la figure 3, dans le cas d'une classe de motifs SIM pour le rôle A

3. Application

3.1 Création du réseau

Le fichier “network_tf_gene.csv” est chargé dans Tulip en créant une relation (arête) pour chaque ligne. Les gènes de la colonne 2 sont déterminés comme noeuds sources et les gènes de la colonne 4 comme cibles.
Pour alléger le graphe, un noeud ne doit avoir qu'une arête entrante. Pour cela, les noms de toutes les noeuds source des arêtes entrantes sont concaténer et un nouveau noeud portant ce nom est créé. Toutes les arêtes qui étaient alors entrantes sont supprimées et une nouvelle qui relie le noeud cible au nouveau noeud est créée.
Le graphe obtenu a 1861 noeuds et 1524 arêtes.

Le code se trouve ici : marajo_veyssiere_centrality.tlpx

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/marajo_veyssiere/paul_maheva_marajo_maeva_veyssiere.txt · Last modified: 2014/01/18 20:29 by mveyssiere