Navigation – Plan du site

Recherche de classes empiétantes dans un graphe : application aux réseaux d’interactions entre protéines

Computation of overlapping classes in a graph: application to protein-protein interactions networks
Lucile Denoeud-Belgacem
p. 7-42

Résumés

Cet article présente une méthode de classification empiétante permettant de mettre en évidence des zones denses en arêtes dans un graphe. On cherche plus précisément à extraire du graphe des sous-graphes dont la densité en arêtes soit élevée par rapport à la densité du graphe entier, ces sous-graphes pouvant avoir des sommets en commun. Cette méthode est appliquée à un problème issu de la biologique : l’annotation des protéines. Les graphes considérés traduisent alors des interactions observées entre les protéines. Partant du principe biologique que des protéines impliquées dans une même fonction cellulaire interagissent, les sous-graphes obtenus par l’application de la méthode de classification empiétante aux réseaux d’interactions donnent des indications sur les fonctions des protéines constituant ces sous-graphes, ce qui permet de fournir une aide informatique à la prédiction de fonctions inconnues de certaines protéines. Le caractère empitétant autorisé par la méthode présentée ici permet en particulier de prendre en compte le fait que les protéines peuvent être impliquées chacune dans plusieurs fonctions cellulaires.

Computation of overlapping classes in a graph: application to protein-protein interactions networks

This article describes a method of overlapping classification, in order to compute zones which are dense in edges in a graph. More precisely, the aim is to compute subgraphs in which the density of edges is large compared to the edge-density of the whole graph. These subgraphs may share common vertices. This method is applied to a problem arising in biology: the annotation of proteins. The graphs then represent the observed interactions between proteins. Thanks to the biological principle that proteins involved in the same cellular function interact, the subgraphs provided when the method is applied to the protein-protein interactions networks provide information about the functions of proteins belonging to these subgraphs. This provides a computer-aided tool for the prediction of unknown functions of some proteins. The overlapping allowed by the method depicted here makes it possible to take into account the fact that each protein may be involved into several cellular functions.

Haut de page

Pour citer cet article

Référence électronique

Lucile Denoeud-Belgacem, « Recherche de classes empiétantes dans un graphe : application aux réseaux d’interactions entre protéines », Mathématiques et sciences humaines [En ligne], 187 | Automne 2009, mis en ligne le 15 décembre 2009, consulté le 13 décembre 2017. URL : http://journals.openedition.org/msh/11106

Haut de page

Auteur

Lucile Denoeud-Belgacem

Futur master, lucile.belgacem@futurmaster.com

Haut de page

Droits d’auteur

© École des hautes études en sciences sociales

Haut de page