Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Assessing the exceptionality of coloured motifs in networks

Abstract : Various methods have been recently employed to characterise the structure of biological networks. In particular, the concept of network motif and the related one of coloured motif have proven useful to model the notion of a functional/evolutionary building block. However, algorithms that enumerate all the motifs of a network may produce a very large output, and methods to decide which motifs should be selected for downstream analysis are needed. A widely used method is to assess if the motif is exceptional, that is, over- or under-represented with respect to a null hypothesis. Much effort has been put in the last thirty years to derive P-values for the frequencies of topological motifs, that is, fixed subgraphs. They rely either on (compound) Poisson and Gaussian approximations for the motif count distribution in Erdös-Rényi random graphs or on simulations in other models. We focus on a different definition of graph motifs that corresponds to coloured motifs. A coloured motif is a connected subgraph with fixed vertex colours but unspecified topology. Our work is the first analytical attempt to assess the exceptionality of coloured motifs in networks without any simulation. We first establish analytical formulae for the mean and the variance of the count of a coloured motif in an Erdös-Rényi random graph model. Using simulations under this model, we further show that a Pólya-Aeppli distribution better approximates the distribution of the motif count compared to Gaussian or Poisson distributions. The Pólya-Aeppli distribution, and more generally the compound Poisson distributions, are indeed well designed to model counts of clumping events. Altogether, these results enable to derive a P-value for a coloured motif, without spending time on simulations
Type de document :
Article dans une revue
Liste complète des métadonnées
Déposant : Migration Prodinra <>
Soumis le : vendredi 29 mai 2020 - 23:06:13
Dernière modification le : lundi 16 novembre 2020 - 15:26:09

Lien texte intégral




Sophie Schbath, Vincent Lacroix, Marie-France Sagot. Assessing the exceptionality of coloured motifs in networks. EURASIP Journal on Bioinformatics and Systems Biology, SpringerOpen, 2009, 2009, 9 p. on line. ⟨10.1155/2009/616234⟩. ⟨hal-02656035⟩



Consultations de la notice