Number of Attractors in the Critical Kauffman Model Is Exponential.

The Kauffman model is the archetypal model of genetic computation. It highlights the importance of criticality, at which many biological systems seem poised. In a series of advances, researchers have honed in on how the number of attractors in the critical regime grows with network size. But a definitive answer has remained elusive. We prove that, for the critical Kauffman model with connectivity one, the number of attractors grows at least, and at most, as (2/sqrt[e])^{N}. This is the first proof that the number of attractors in a critical Kauffman model grows exponentially.

How much can we influence the rate of innovation?

Innovation is how organizations drive technological change, but the rate of innovation can vary considerably from one technological domain to another. To understand why some domains flourish more rapidly than others, we studied a model of innovation in which products are built out of components. We derived a conservation law for the average size of the product space as more components are acquired and tested our insights using historical data from language, gastronomy, mixed drinks, and technology. We find that the innovation rate is partly influenceable and partly predetermined, similar to how traits are partly set by nurture and partly set by nature. The predetermined aspect is fixed solely by the distribution of the complexity of products in each domain. Different distributions can produce markedly different innovation rates. This helps explain why some domains show faster innovation than others, despite similar efforts to accelerate them. Our insights also give a quantitative perspective on lean methodology, frugal innovation, and mechanisms to encourage tinkering.

Serendipity and strategy in rapid innovation.

Innovation is to organizations what evolution is to organisms: it is how organizations adapt to environmental change and improve. Yet despite advances in our understanding of evolution, what drives innovation remains elusive. On the one hand, organizations invest heavily in systematic strategies to accelerate innovation. On the other, historical analysis and individual experience suggest that serendipity plays a significant role. To unify these perspectives, we analysed the mathematics of innovation as a search for designs across a universe of component building blocks. We tested our insights using data from language, gastronomy and technology. By measuring the number of makeable designs as we acquire components, we observed that the relative usefulness of different components can cross over time. When these crossovers are unanticipated, they appear to be the result of serendipity. But when we can predict crossovers in advance, they offer opportunities to strategically increase the growth of the product space.

Form and function in gene regulatory networks: the structure of network motifs determines fundamental properties of their dynamical state space.

Network motifs have been studied extensively over the past decade, and certain motifs, such as the feed-forward loop, play an important role in regulatory networks. Recent studies have used Boolean network motifs to explore the link between form and function in gene regulatory networks and have found that the structure of a motif does not strongly determine its function, if this is defined in terms of the gene expression patterns the motif can produce. Here, we offer a different, higher-level definition of the 'function' of a motif, in terms of two fundamental properties of its dynamical state space as a Boolean network. One is the basin entropy, which is a complexity measure of the dynamics of Boolean networks. The other is the diversity of cyclic attractor lengths that a given motif can produce. Using these two measures, we examine all 104 topologically distinct three-node motifs and show that the structural properties of a motif, such as the presence of feedback loops and feed-forward loops, predict fundamental characteristics of its dynamical state space, which in turn determine aspects of its functional versatility. We also show that these higher-level properties have a direct bearing on real regulatory networks, as both basin entropy and cycle length diversity show a close correspondence with the prevalence, in neural and genetic regulatory networks, of the 13 connected motifs without self-interactions that have been studied extensively in the literature.

Self-assembly, modularity, and physical complexity.

We present a quantitative measure of physical complexity, based on the amount of information required to build a given physical structure through self-assembly. Our procedure can be adapted to any given geometry, and thus, to any given type of physical structure that can be divided into building blocks. We illustrate our approach using self-assembling polyominoes, and demonstrate the breadth of its potential applications by quantifying the physical complexity of molecules and protein complexes. This measure is particularly well suited for the detection of symmetry and modularity in the underlying structure, and allows for a quantitative definition of structural modularity. Furthermore we use our approach to show that symmetric and modular structures are favored in biological self-assembly, for example in protein complexes. Lastly, we also introduce the notions of joint, mutual and conditional complexity, which provide a useful quantitative measure of the difference between physical structures.

Clustering signatures classify directed networks.

We use a clustering signature, based on a recently introduced generalization of the clustering coefficient to directed networks, to analyze 16 directed real-world networks of five different types: social networks, genetic transcription networks, word adjacency networks, food webs, and electric circuits. We show that these five classes of networks are cleanly separated in the space of clustering signatures due to the statistical properties of their local neighborhoods, demonstrating the usefulness of clustering signatures as a classifier of directed networks.

Ensemble approach to the analysis of weighted networks.

We present an approach to the analysis of weighted networks, by providing a straightforward generalization of any network measure defined on unweighted networks, such as the average degree of the nearest neighbors, the clustering coefficient, the "betweenness," the distance between two nodes, and the diameter of a network. All these measures are well established for unweighted networks but have hitherto proven difficult to define for weighted networks. Our approach is based on the translation of a weighted network into an ensemble of edges. Further introducing this approach we demonstrate its advantages by applying the clustering coefficient constructed in this way to two real-world weighted networks.

Unbiased pattern detection in microarray data series.

MOTIVATION: Following the advent of microarray technology in recent years, the challenge for biologists is to identify genes of interest from the thousands of genetic expression levels measured in each microarray experiment. In many cases the aim is to identify pattern in the data series generated by successive microarray measurements. RESULTS: Here we introduce a new method of detecting pattern in microarray data series which is independent of the nature of this pattern. Our approach provides a measure of the algorithmic compressibility of each data series. A series which is significantly compressible is much more likely to result from simple underlying mechanisms than series which are incompressible. Accordingly, the gene associated with a compressible series is more likely to be biologically significant. We test our method on microarray time series of yeast cell cycle and show that it blindly selects genes exhibiting the expected cyclic behaviour as well as detecting other forms of pattern. Our results successfully predict two independent non-microarray experimental studies.