5. Différents types de graphes pour représenter les interactions
Un interactome peut décrire des dizaines de milliers d'interactions qui forment un réseau biologique généralement représenté par un graphe qui peut être défini comme une paire (V,E) :
- V est un ensemble de sommets représentant les nœuds. Dans un réseau d'interactions protéine-protéine, les nœuds représentent les protéines.
- E est un ensemble d'arêtes (ou arcs) représentant les interactions entre les nœuds (protéines).
Exemple ci-dessous : une partie du réseau d'interactions établies par Dnm1, protéine clé de la fission des mitochondries.
Source : STRING
α. Graphe unique non orienté ("undirected single graph")
Les modèles d'interactions physiques utilisent fréquemment des arêtes non orientées :
- Si la protéine A interagit avec la protéine B, alors B interagit avec A. L'interaction est établie dans les deux sens (relation symétrique) : le graphe est dit non orienté.
- Le nombre d'arêtes reliant un noeud dans un graphe non orienté est le degré du noeud.
Une connexion à tronçons multiples se compose d'au moins 2 tronçons ayant les mêmes extrémités : chaque connexion indique un type d'information différent. Cette caractéristique est importante car, au sein des les réseaux d'interactions protéine-protéine, deux protéines peuvent :
- être liées sur le plan évolutif
- être co-citées dans la littérature
- être co-exprimées dans certaines expériences
- Ces 3 types d'interactions ont des significations différentes.
STRING est une base de données PPI construite sur ces 3 types d'interactions entre protéines.
β. Graphe orienté ("directed graph")
Les techniques expérimentales peuvent se traduire par une "asymétrie" :
- Si la protéine A est une "proie", une interaction avec la protéine B peut être mise en évidence.
- Inversement, l'utilisation de B comme proie peut ne pas révéler d'interaction avec A.
Un graphe orienté est défini comme un triplet ordonné G = (V,E,f), où f est une fonction qui associe chaque élément de E à une paire ordonnée de sommets dans V.
Les paires ordonnées de sommets sont appelées arêtes orientées ou flèches : une arête E = (i,j) est orientée de i vers j.
- Les graphes orientés sont adaptés à la représentation de processus biologiques caractérisés par des interactions séquentielles entre protéines avec un flux d'information au travers du réseau.
- Il traduisent donc particulièrement bien les voies métaboliques, les voies de transduction du signal ou les voies de régulation.
δ. Graphique pondéré ("weighted graph")
Un graphe pondéré est défini comme un graphe G = (V,E) où V est un ensemble de sommets et E un ensemble d'arêtes entre ces sommets lui associant une fonction de poids (w : E->R, R est l'ensemble des nombres réels).
Les graphes pondérés sont les réseaux les plus utilisés en bioinformatique.
- Le plus souvent, le poids wij de l'arête entre les nœuds i et j représente la pertinence de l'interaction : plus l'interaction est prouvée, plus son poids est important.
- Exemple de co-occurrence de données biologiques ayant une incidence sur leur pertinence et donc sur le poids des interactions : fouille de données textuelles et/ou co-expression de gènes et/ou similarités de séquences ou de structures entre protéines.
γ. Graphe bipartie ("bipartite graph")
Un graphe bipartie (ou bigraphe ou réseau à 2 modes) est un graphe non orienté G = (V, E) dans lequel V peut être partitionné en 2 ensembles V1 et V2 tels que (u,v) ∈ E implique soit (u ∈ V1 et v ∈ V2) OU (v ∈ V1 et u ∈ V2) : en d'autres termes, chaque arête (E) relie un sommet de V1 à un sommet de V2.
Ce type de graphe est adapté à la représentation des liens [enzyme - réaction] dans les voies métaboliques et à l'annotation sur la base d'une ontologie. |
