August 13, 2003
Interaction networks are of central importance in post-genomic molecular biology, with increasing amounts of data becoming available by high-throughput methods. Examples are gene regulatory networks or protein interaction maps. The main challenge in the analysis of these data is to read off biological functions from the topology of the network. Topological motifs, i.e., patterns occurring repeatedly at different positions in the network have recently been identified as basic modules of molecular information processing. In this paper, we discuss motifs derived from families of mutually similar but not necessarily identical patterns. We establish a statistical model for the occurrence of such motifs, from which we derive a scoring function for their statistical significance. Based on this scoring function, we develop a search algorithm for topological motifs called graph alignment, a procedure with some analogies to sequence alignment. The algorithm is applied to the gene regulation network of E. coli.
Similar papers 1
July 8, 2010
Studying the topology of so-called real networks, that is networks obtained from sociological or biological data for instance, has become a major field of interest in the last decade. One way to deal with it is to consider that networks are built from small functional units called motifs, which can be found by looking for small subgraphs whose numbers of occurrences in the whole network are surprisingly high. In this article, we propose to define motifs through a local overre...
April 2, 2009
Studying the topology of so-called {\em real networks}, that is networks obtained from sociological or biological data for instance, has become a major field of interest in the last decade. One way to deal with it is to consider that networks are built from small functional units called {\em motifs}, which can be found by looking for small subgraphs whose numbers of occurrences in the whole network of interest are surprisingly high. In this paper, we propose to define motifs ...
December 19, 2017
The biological processes of cellular decision making and differentiation involve a plethora of signalling pathways and gene regulatory circuits. These networks, in their turn, exhibit a multitude of motifs playing crucial parts in regulating network activity. Here, we compare the topological placement of motifs in gene regulatory and signalling networks and find that it suggests different evolutionary strategies in motif distribution for distinct cellular subnetworks.
January 29, 2020
Analysis of the structure of biological networks often uses statistical tests to establish the over-representation of motifs, which are thought to be important building blocks of such networks, related to their biological functions. However, there is disagreement as to the statistical significance of these motifs, and there are potential problems with standard methods for estimating this significance. Exponential random graph models (ERGMs) are a class of statistical model th...
May 27, 2020
One of the most important concepts in biological network analysis is that of network motifs, which are patterns of interconnections that occur in a given network at a frequency higher than expected in a random network. In this work we are interested in searching and inferring network motifs in a class of biological networks that can be represented by vertex-colored graphs. We show the computational complexity for many problems related to colorful topological motifs and presen...
September 9, 2011
Topological network motifs represent functional relationships within and between regulatory and protein-protein interaction networks. Enriched motifs often aggregate into self-contained units forming functional modules. Theoretical models for network evolution by duplication-divergence mechanisms and for network topology by hierarchical scale-free networks have suggested a one-to-one relation between network motif enrichment and aggregation, but this relation has never been t...
November 30, 2010
Over the past decade, a number of researchers in systems biology have sought to relate the function of biological systems to their network-level descriptions -- lists of the most important players and the pairwise interactions between them. Both for large networks (in which statistical analysis is often framed in terms of the abundance of repeated small subgraphs) and for small networks which can be analyzed in greater detail (or even synthesized in vivo and subjected to expe...
July 27, 2009
The identification of motifs--subgraphs that appear significantly more often in a particular network than in an ensemble of randomized networks--has become a ubiquitous method for uncovering potentially important subunits within networks drawn from a wide variety of fields. We find that the most common algorithms used to generate the ensemble from the real network change subgraph counts in a highly correlated manner, so that one subgraph's status as a motif may not be indepen...
September 28, 2006
An important part of the analysis of bio-molecular networks is to detect different functional units. Different functions are reflected in a different evolutionary dynamics, and hence in different statistical characteristics of network parts. In this sense, the {\em global statistics} of a biological network, e.g., its connectivity distribution, provides a background, and {\em local deviations} from this background signal functional units. In the computational analysis of biol...
February 3, 2010
We introduce a method to convert an ensemble of sequences of symbols into a weighted directed network whose nodes are motifs, while the directed links and their weights are defined from statistically significant co-occurences of two motifs in the same sequence. The analysis of communities of networks of motifs is shown to be able to correlate sequences with functions in the human proteome database, to detect hot topics from online social dialogs, to characterize trajectories ...