DIA-MCIS: an importance sampling network randomizer for network motif discovery and other topological observables in transcription networks.

MOTIVATION: Transcription networks, and other directed networks can be characterized by some topological observables (e.g. network motifs), that require a suitable randomized network ensemble, typically with the same degree sequences of the original ones. The commonly used algorithms sometimes have long convergence times, and sampling problems. We present here an alternative, based on a variant of the importance sampling Monte Carlo developed by (Chen et al.). AVAILABILITY: The algorithm is available at http://wwwteor.mi.infn.it/bassetti/downloads.html

Random networks tossing biased coins.

In statistical mechanical investigations of complex networks, it is useful to employ random graph ensembles as null models to compare with experimental realizations. Motivated by transcription networks, we present here a simple way to generate an ensemble of random directed graphs with asymptotically, scale-free out-degree and compact in-degree. Entries in each row of the adjacency matrix are set to 0 or 1 according to the toss of a biased coin, with a chosen probability distribution for the biases. This defines a quick and simple algorithm, which yields good results already for graphs of size n approximately 100. Perhaps more importantly, many of the relevant observables are accessible analytically, improving upon previous estimates for similar graphs. The technique is easily generalizable to different kinds of graphs.

Hierarchy and feedback in the evolution of the Escherichia coli transcription network.

The Escherichia coli transcription network has an essentially feedforward structure, with abundant feedback at the level of self-regulations. Here, we investigate how these properties emerged during evolution. An assessment of the role of gene duplication based on protein domain architecture shows that (i) transcriptional autoregulators have mostly arisen through duplication, whereas (ii) the expected feedback loops stemming from their initial cross-regulation are strongly selected against. This requires a divergent coevolution of the transcription factor DNA-binding sites and their respective DNA cis-regulatory regions. Moreover, we find that the network tends to grow by expansion of the existing hierarchical layers of computation, rather than by addition of new layers. We also argue that rewiring of regulatory links due to mutation/selection of novel transcription factor/DNA binding interactions appears not to significantly affect the network global hierarchy, and that horizontally transferred genes are mainly added at the bottom, as new target nodes. These findings highlight the important evolutionary roles of both duplication and selective deletion of cross-talks between autoregulators in the emergence of the hierarchical transcription network of E. coli.

Logic backbone of a transcription network.

A great part of the effort in the study of coarse-grained models of transcription networks concentrates on their dynamical features. In this Letter, we consider their equilibrium properties, showing that the backbone underlying the dynamic descriptions is an optimization problem. It involves N variables, the gene expression levels, and M constraints, the effects of transcriptional regulation. In the case of Boolean variables and constraints, we investigate the structure of the solutions and derive phase diagrams. Notably, the model exhibits a connectivity transition between a regime of simple gene control, where the input genes control O(1) other genes, and a regime of complex control, where some core input genes control O(N) others.

Metachronal waves for deterministic switching two-state oscillators with hydrodynamic interaction.

We employ a model system, called rowers, as a generic physical framework to define the problem of the coordinated motion of cilia (the metachronal wave) as a far from equilibrium process. Rowers are active (two-state) oscillators in a low Reynolds number fluid, and interact solely through the forces of hydrodynamic origin. In this work, we consider the case of fully deterministic dynamics, find analytical solutions of the equation of motion in the long-wavelength (continuum) limit, and investigate numerically the short-wavelength limit. We prove the existence of metachronal waves below a characteristic wavelength. Such waves are unstable and become stable only if the sign of the coupling is reversed. We also find that with normal hydrodynamic interaction, the metachronal pattern has the form of stable trains of traveling wave packets sustained by the onset of anti-coordinated beating of consecutive rowers.