Le deuxième article sur la repré­sen­ta­tion du méta­bo­lisme et son ana­lyse !

Pour rap­pel, le pre­mier volet est ici !

---

Un grand nombre de phé­no­mènes bio­lo­giques peuvent être repré­sen­tés sous la forme d'un réseau. Qui n'a jamais enten­du par­ler de réseaux d'intéraction pro­téine-pro­téine (fameux réseaux "PPI"), de réseaux de gènes ou encore de réseaux méta­bo­liques ? En fait, dès qu'il s'agit de repré­sen­ter des connexions ou des inté­rac­tions entre des enti­tés, que ce soit en bio­lo­gie ou dans un autre domaine. Je pour­rais citer, entre nom­breux autres, la socio­lo­gie — pen­sez aux réseaux sociaux d'intéractions de per­sonnes entre elles, la phy­sique — notam­ment les réseaux élec­triques et ceux d'intéraction de dif­fé­rentes par­ti­cules (sub)atomiques, la chi­mie — par exemple une molé­cule qui peut être repré­sen­tée comme un réseau d'intéraction des atomes qui la consti­tuent… et j'en passe ! Pen­sez aus­si aux réseaux que vous uti­li­sez tous les jours, comme les réseaux rou­tiers, les réseaux de trans­port, inter­net.… vous ima­gi­nez bien qu'il y a des gens qui se sont spé­cia­li­sés dans l'analyse de réseaux ! On parle d'ailleurs de plus en plus de "net­work science", qui cherche à ras­sem­bler les déve­lop­pe­ments autour des réseaux réa­li­sés dans dif­fé­rents domaines.

Tout ce qui va suivre dans cet article est appli­cable à peu près à n'importe quel type de réseau. Mais bon, ici, on est sur un blog de bioin­fo, donc ima­gi­nons tous ensemble qu'on veut ana­ly­ser un réseau méta­bo­lique (je dis ça car je tra­vaille sur des réseaux méta­bo­liques). Ou un réseau PPI. Ou encore un réseau de gènes. Comme vous vou­lez !

Voi­ci donc une intro­duc­tion à l'analyse des carac­té­ris­tiques topo­lo­giques d'un réseau

On peut ima­gi­ner qu’il existe une cor­ré­la­tion entre la struc­ture d’un réseau bio­lo­gique et les fonc­tions bio­lo­giques retrou­vées dans ce der­nier. Le défi consiste alors à retrou­ver des struc­tures topo­lo­giques inté­res­santes d’un point de vue bio­lo­gique (et oui, car nous somme là pour ana­ly­ser la bio­lo­gie d'un orga­nisme, non?) dans les réseaux métaboliques.Afin de faire ça, nous allons confron­ter des ana­lyses infor­ma­tiques de graphes (ce type d’analyses est notam­ment très uti­li­sé pour ana­ly­ser des réseaux sociaux, domaine qui nous dépasse un peu sur l'analyse de ce type de don­nées) avec des don­nées bio­lo­giques diverses. Ici, je vais par­ler de deux types d’analyses topo­lo­giques, les « clas­siques » et les cen­tra­li­tés de graphes.

C'est par­ti !

Analyses topologiques classiques

Ici je vais juste vous faire un petit résu­mé des dif­fé­rents métriques de graphes, qui peuvent s'avérer très utiles lorsque l'on veut faire connais­sance avec cette chose. Alors, n'ayez pas peur des petites for­mules que je vais mettre ici, elles sont en fait très très simples !

Alors, ima­gi­nons un graphe, tout simple. Avec des noeuds (ver­tices ou nodes en anglais) et des arêtes (edges). Et appel­lons-le G (oui, G comme "Graphe", très ori­gi­nal, héhé).

 

Soit G(V,E) un graphe tel que E contient l’ensemble des arêtes du graphe et V contient l’ensemble de ses nœuds. Appe­lons, très clas­si­que­ment, v un nœud du graphe G tel que v ∈ V.

La pre­mière métrique, la plus simple est le degré d(v) d’un nœud v. Il s'agit du nombre d’arêtes qui le lient à d’autres nœuds du même graphe. Dans le cas d’un graphe orien­té, on pour­ra dis­tin­guer le degré sor­tant d⁺(v) (« out degree » en anglais) qui est le nombre d’arcs ayant le nœud comme source et le degré entrant d^-(v) (« in degree ») qui cor­res­pond au nombre d’arcs qui ont le nœud comme cible.

Dans notre exemple, d(Node3)=4, d⁺(Node 3)=2 et d^-(Node 3) =2.

Si on aug­mente la taille des noeuds pro­por­tio­nel­le­ment à leur degré total, ça donne ça :

Ensuite, il y a d'autres métriques :

• La dis­tance entre deux nœuds dans un graphe, qui est la lon­gueur du (ou des) plus court(s) chemin(s) entre ces deux nœuds.
• Le rayon du graphe, qui cor­res­pond à la plus petite dis­tance à laquelle puisse se trou­ver un nœud de tous les autres nœuds du graphe. Cette mesure cor­res­pond à l’excen­tri­ci­té mini­male des nœuds du graphe.
• Le dia­mètre d’un graphe, qui repré­sente la dis­tance maxi­male par­mi les dis­tances entre toutes les paires de nœuds dans le graphe. Le dia­mètre cor­res­pond à l’excen­tri­ci­té maxi­male du graphe.
• Le centre d’un graphe cor­res­pond à l’ensemble non-nul des nœuds d’excentricité mini­male.

 

A cette liste je vou­drais aus­si ajou­ter le coef­fi­cient d'agglomération (ou de « clus­te­ring » pour faire un angli­cisme) qui est la mesure de regrou­pe­ment de nœuds dans un réseau. Concrè­te­ment, pour un nœud, ce coef­fi­cient mesure à quel point le voi­si­nage de ce nœud est connec­té. Expli­ca­tion par l'image :

 

Comme vous pou­vez le consta­ter, les deux métriques de graphes illus­trées mettent en valeur des noeuds dif­fé­rents. Il est donc impor­tant de savoir ce que l'on sou­haite voir dans le réseau avant de se lan­cer dans le cal­cul des dif­fé­rentes ana­lyses ! Et c'est pas fini ! Car je vais main­te­nant vous par­ler de métriques un peu plus com­plexes, mais d'autant plus utiles pour ana­ly­ser la topo­lo­gie d'un graphe ! Je vous pré­sente…

Les centralités

Durant ma thèse j'ai pas mal étu­dié le sujet, je pour­rais donc en par­ler pen­dant des heures et des heures… mais ce n'est pas le but ici ! Alors si le topic vous inter­esse, je vous ren­voie à la lit­té­ra­ture, notam­ment l'excellent livre en accès libre "Net­work ana­ly­sis" où plu­sieurs cha­pitres y sont consa­crés. Je vais entre temps sur­vo­ler le sujet, en pré­sen­tant les cen­tra­li­tés les plus cou­rantes et les plus utiles.

Mais tout d'abord, qu'est ce qu'une cen­tra­li­té ?

Les indices de cen­tra­li­té quan­ti­fient le sen­ti­ment intui­tif que dans la plu­part des réseaux, cer­tains nœuds ou arêtes sont plus impor­tants (ou plus cen­traux) que d’autres. Logique, hein ? Beau­coup d’indices de cen­tra­li­té rela­tifs aux nœuds ont été intro­duits à par­tir des années 1940, comme la cen­tra­li­té de degré ("degree cen­tra­li­ty" — il s'agit en fait tout sim­ple­ment du degré de chaque noeud) ou la cen­tra­li­té feed­back. Depuis, des dizaines de nou­veaux indices de cen­tra­li­tés ont été publiés, car toutes les cen­tra­li­tés ne repré­sentent pas la même chose, et il faut adap­ter cette mesure à chaque appli­ca­tion.

L’importance des nœuds et des arêtes dans un graphe est éva­luée selon des valeurs réelles qui y sont asso­ciées, et ces valeurs dépendent uni­que­ment de la struc­ture de ce graphe. Aus­si, une cen­tra­li­té doit res­ter inva­riante dans le cas de graphes iso­mor­phiques (qui ont la même topo­lo­gie).

Les indices de cen­tra­li­té peuvent être clas­sés dans plu­sieurs caté­go­ries :

Centralités de distances et de voisinage

Les cen­tra­li­tés liées au voi­si­nage des nœuds et aux dis­tances qui les séparent éva­luent l’accessibilité d’un nœud. Dans un réseau, ces mesures per­mettent de clas­ser les nœuds en fonc­tion du nombre de leurs voi­sins et/​ou du coût néces­saire pour atteindre tous les autres nœuds. La cen­tra­li­té basée sur la notion de voi­si­nage est l’indice le plus basique. On a déjà par­lé pré­cé­dem­ment du degré d'un nœud, et bien en fait c'est aus­si une cen­tra­li­té !

La cen­tra­li­té de degré est une mesure locale car sa valeur pour un nœud don­né est sim­ple­ment déter­mi­née par le nombre de ses voi­sins. Les cen­tra­li­tés impli­quant la notion de dis­tances dans un graphe sont des mesures glo­bales de cen­tra­li­té. Géné­ra­le­ment ces mesures sont assi­mi­lées aux pro­blèmes de loca­li­sa­tion des éta­blis­se­ments (« Faci­li­ty Loca­tion Pro­blems »), car elles servent à trou­ver le ou les nœuds les plus acces­sibles à par­tir de tous les autres nœuds du graphe. La mesure de l’excentricité, par exemple, peut être assi­mi­lée à la recherche du nœud qui mini­mise la dis­tance maxi­male jusqu’à tous les autres empla­ce­ments dans le réseau. Pour illus­trer cette mesure, il faut ima­gi­ner que l’on veut trou­ver l’endroit opti­mal pour un hôpi­tal dans une ville, où le temps de tra­jet jusqu’à cet hôpi­tal soit opti­mi­sé quel que soit le point de départ :

Centralités des plus courts chemins

Les indices de cen­tra­li­té basés sur les ensembles de plus courts che­mins dans un réseau sont aus­si des cen­tra­li­tés glo­bales. Soit deux nœuds u et v dans un graphe. Le plus court che­min entre u et v est une séquence de nœuds connec­tés par des arêtes tel que u et v soient aux extré­mi­tés de ce che­min, et que le nombre de nœuds inter­mé­diaires soit mini­mal. Il s’agit en fait, de la dis­tance entre u et v. Pour cal­cu­ler les cen­tra­li­tés basées sur cette notion, une étape de pré-cal­cul des plus courts che­mins pour toutes les paires de nœuds du graphe est néces­saire.

Ici je ne pré­sen­te­rai que la cen­tra­li­té appel­lée "bet­ween­ness", mais sachez aus­si que la cen­tra­li­té de stress (stress cen­tra­li­ty) peut aus­si s’avérer aus­si très utile.

La cen­tra­li­té bet­ween­ness consiste à comp­ter le nombre rela­tif de plus courts che­mins qu'il existe entre chaque paire de nœuds. Ceci peut être inter­pré­té comme une mesure dans laquelle un nœud v contrôle la com­mu­ni­ca­tion entre une paire de nœuds s et t.

Soit la frac­tion de tous les plus courts che­mins entre s et t qui contiennent le som­met v :

oùest le nombre total de plus courts che­mins entre s et t, tels queet. Cette frac­tion peut être consi­dé­rée comme la pro­ba­bi­li­té que v est impli­qué dans la com­mu­ni­ca­tion entre s et t. La cen­tra­li­té bet­ween­nessdu nœud v est alors don­née par :

Pour dire les choses sim­ple­ment, pour chaque paire de noeuds dans le graphe, on va comp­ter tous les plus courts che­mins. Ensuite, pour chaque noeud, on va comp­ter com­bien de che­mins passent par ce noeud par­mi tous les plus courts che­mins, et ce, pour chaque paire de noeuds.

Ain­si, cette cen­tra­li­té met en valeur les noeuds par les­quels passe le plus d'information. Dans notre exemple du graphe G(V,E), les noeuds 5 et 9 sont à l'intersection de ses trois par­ties. Si on regarde de plus près, on est obli­gé de pas­ser par au moins un de ces deux noeuds pour aller d'une par­tie du graphe (du noeud 12 par exemple) vers une autre par­tie du graphe (vers le noeud 6 ou 2). La cen­tra­li­té bet­ween­ness sera donc très éle­vée pour ces deux noeuds.

Pour résu­mer, la cen­tra­li­té bet­ween­ness va être très éle­vée pour les nœuds par les­quels passent beau­coup de che­mins du graphe, ces noeuds étant ceux qui font les ponts entre tous les autres noeuds :

 

Feedback

La cen­tra­li­té dite "feed­back" (ou de "retour d’information") est basée sur le prin­cipe d’influence du voi­si­nage : plus un nœud a de voi­sins, plus il est cen­tral, et plus il est cen­tral, plus ses voi­sins le sont aus­si. On pour­ra aus­si repré­sen­ter ça d'une façon plus ima­gée, en pre­nant l'exemple sur l'importance des gens en poli­tique, ou dans tout autre groupe social : plus une per­sonne a des amis impor­tants, plus elle est impor­tante ; et plus une per­sonne est impor­tante, plus ses amis deviennent impor­tants.

Ce type de cen­tra­li­tés, plus com­plexes que celles pré­sen­tées pré­cé­dem­ment, est très uti­li­sé dans l’analyse de réseaux inter­net, de réseaux sociaux, et, moins, pour l’instant, dans les réseaux bio­lo­giques. Par­mi les cen­tra­li­tés "feed­back" les plus connues, on retrouve l’indice de Katz , la cen­tra­li­té de vec­teurs propres de Bona­cich , l’indice de Hub­bell, Page­Rank (uti­li­sée jadis par Google) et SALSA (le coeur de Wol­fram). Les notions de « hubs » et « d’autorités » sont très impor­tantes dans ces cen­tra­li­tés. Un hub est un nœud qui pointe vers beau­coup de bonnes auto­ri­tés, et une auto­ri­té est un nœud poin­té par beau­coup de bons hubs.

Ici je ne vous par­le­rai que de la cen­tra­li­té Page­Rank. Elle a, pen­dant très long­temps, été un des ingré­dients prin­ci­paux du célèbre moteur de recherche Google (qui l'a depuis repla­cé par des algo­rithmes encore plus com­plexes qu'efficaces por­tant plein de noms d'animaux — Pan­da, Pen­guin et Hum­ming­bird). L’idée prin­ci­pale de cet algo­rithme est de mar­quer une page inter­net en tenant compte de ses pro­prié­tés topo­lo­giques (c’est à dire de sa posi­tion dans le réseau). Il s’agit bien d’une cen­tra­li­té feed­back, car ici le score d’une page web dépend du nombre et des scores de ses pages voi­sines. Cette cen­tra­li­té peut être consi­dé­rée comme « semi-glo­bale », car elle per­met de cal­cu­ler des cen­tra­li­tés par zones d’influence de nœuds très auto­ri­taires, qui défi­nissent des régions autour d’eux. L'image sui­vante repré­sente bien le fonc­tion­ne­ment de cette cen­tra­li­té :

 

Sur cette image, la cou­leur et la taille des smi­leys dépend de impor­tance selon Page Rank. Par exemple, beau­coup de noeuds pointent sur le noeud jaune, donc il est très très cen­tral. Et il a la capa­ci­té de par­ta­ger cette cen­tra­li­té avec le seul noeud vers lequel il pointe (le gros rouge). En effet, même si ce smi­ley rouge n'est poin­té que par un seul autre smi­ley, il est quand même grand, car son voi­sin est très grand et par­tage un peu de son impor­tance avec lui.

 

Et notre petit G(V,E), vu par Page­Rank :

 

C'est la fin de cet article sur les métriques dans les réseaux… mais on reparle des réseaux très bientôt !

---

Quelques com­men­taires pour la fin (quand même):

• Les indices de cen­tra­li­té peuvent aus­si s'appliquer aux arêtes d'un graphe, exac­te­ment de la même façon que sur ses noeuds.
• Presque toutes les images de cet article ont été réa­li­sées avec Cytos­cape 3.
• J'ai pré­vu de faire un troi­sième article sur l'analyse de réseaux (méta­bo­liques ou non), donc si vous avez des envies par­ti­cu­lières, n'hésitez pas !

 

---

Un grand mer­ci aux relec­teurs pour leurs sug­gés­tions et dis­cus­sions : Mathu­rin, Hed­Jour et tadai­ma !