A statistical method for revealing form-function relations in biological networks

This dissertation contributes to mathematical and algorithmic problems that arise in the analysis of network and biological data.

Recent evidence indicates that the abundance of recurring elementary interaction patterns in complex networks, often called subgraphs or motifs, carry significant information about their function and overall organization. Yet, the underlying reasons for the variable quantity of different subgraph types, their propensity to form clusters, and their relationship with the networks' global organization remain poorly understood. Here we show that a network's large-scale topologica...

These are notes for a set of 7 two-hour lectures given at the 2010 Summer School on Quantitative Evolutionary and Comparative Genomics at OIST, Okinawa, Japan. The emphasis is on understanding how biological systems process information. We take a physicist's approach of looking for simple phenomenological descriptions that can address the questions of biological function without necessarily modeling all (mostly unknown) microscopic details; the example that is developed throu...

Developing and maintaining life requires a lot of computation. This is done by gene regulatory networks. But we have little understanding of how this computation is organized. I show that there is a direct correspondence between the structural and functional building blocks of regulatory networks, which I call regulatory motifs. I derive a simple bound on the range of function that these motifs can perform, in terms of the local network structure. I prove that this range is a...

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...

The degree distribution of many biological and technological networks has been described as a power-law distribution. While the degree distribution does not capture all aspects of a network, it has often been suggested that its functional form contains important clues as to underlying evolutionary processes that have shaped the network. Generally, the functional form for the degree distribution has been determined in an ad-hoc fashion, with clear power-law like behaviour ofte...

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.

Empirical studies of graphs have contributed enormously to our understanding of complex systems. Known today as network science, what was originally a theoretical study of graphs has grown into a more scientific exploration of communities spanning the physical, biological, and social. However, as the quantity and types of networks have grown so has their heterogeneity in quality and specificity. This has hampered efforts to develop general network theory capable of inferring ...

Gene regulatory networks typically have low in-degrees, whereby any given gene is regulated by few of the genes in the network. What mechanisms might be responsible for these low in-degrees? Starting with an accepted framework of the binding of transcription factors to DNA, we consider a simple model of gene regulatory dynamics. In this model, we show that the constraint of having a given function leads to the emergence of minimum connectivities compatible with function. We e...

We analyse growing networks ranging from collaboration graphs of scientists to the network of similarities defined among the various transcriptional profiles of living cells. For the explicit demonstration of the scale-free nature and hierarchical organization of these graphs, a deterministic construction is also used. We demonstrate the use of determining the eigenvalue spectra of sparse random graph models for the categorization of small measured networks.