"The analysis of protein-protein interactions is fundamental to the understanding of cellular organization, processes, and functions. Recent large-scale investigations of protein-protein interactions using such techniques as two-hybrid systems, mass spectrometry, and protein microarrays have enriched the available protein interaction data and facilitated the construction of integrated protein-protein interaction networks. The resulting large volume of protein-protein interaction data has posed a challenge to experimental investigation. This book provides a comprehensive understanding of the computational methods available for the analysis of protein-protein interaction networks. It offers an in-depth survey of a range of approaches, including statistical, topological, data-mining, and ontology-based methods. The author discusses the fundamental principles underlying each of these approaches and their respective benefits and drawbacks, and she offers suggestions for future research."

"In this paper, we propose a novel inference method for dynamic genetic networks which makes it possible to face with a number of time measurements n much smaller than the number of genes p. The approach is based on the concept of low order conditional dependence graph that we extend here in the case of Dynamic Bayesian Networks. Most of our results are based on the theory of graphical models associated with the Directed Acyclic Graphs (DAGs). In this way, we define a minimal DAG G which describes exactly the full order conditional dependencies given the past of the process. Then, to face with the large p and small n estimation case, we propose to approximate DAG G by considering low order conditional independencies. We introduce partial qth order conditional dependence DAGs G(q) and analyze their probabilistic properties. In general, DAGs G(q) differ from DAG G but still reflect relevant dependence facts for sparse networks such as genetic networks. By using this approximation, we set out a non-bayesian inference method and demonstrate the effectiveness of this approach on both simulated and real data analysis. The inference procedure is implemented in the R package 'G1DBN' freely available from the CRAN archive."

"Adaptation of cells to environmental changes requires dynamic interactions between metabolic and regulatory networks, but studies typically address only one or a few layers of regulation. For nutritional shifts between two preferred carbon sources of Bacillus subtilis, we combined statistical and model-based data analyses of dynamic transcript, protein, and metabolite abundances and promoter activities. Adaptation to malate was rapid and primarily controlled posttranscriptionally compared with the slow, mainly transcriptionally controlled adaptation to glucose that entailed nearly half of the known transcription regulation network. Interactions across multiple levels of regulation were involved in adaptive changes that could also be achieved by controlling single genes. Our analysis suggests that global trade-offs and evolutionary constraints provide incentives to favor complex control programs."

"We introduce a quantitative measure of the capacity of a small biological network to evolve. We apply our measure to a stochastic description of the experimental setup of Guet et al. (Science 296:1466, 2002), treating chemical inducers as functional inputs to biochemical networks and the expression of a reporter gene as the functional output. We take an information-theoretic approach, allowing the system to set parameters that optimize signal processing ability, thus enumerating each network's highest-fidelity functions. We find that all networks studied are highly evolvable by our measure, meaning that change in function has little dependence on change in parameters. Moreover, we find that each network's functions are connected by paths in the parameter space along which information is not significantly lowered, meaning a network may continuously change its functionality without losing it along the way. This property further underscores the evolvability of the networks."

"The past decade has seen great advances in our understanding of the role of noise in gene regulation and the physical limits to signaling in biological networks. Here we introduce the spectral method for computation of the joint probability distribution over all species in a biological network. The spectral method exploits the natural eigenfunctions of the master equation of birth-death processes to solve for the joint distribution of modules within the network, which then inform each other and facilitate calculation of the entire joint distribution. We illustrate the method on a ubiquitous case in nature: linear regulatory cascades. The efficiency of the method makes possible numerical optimization of the input and regulatory parameters, revealing design properties of, e.g., the most informative cascades. We find, for threshold regulation, that a cascade of strong regulations converts a unimodal input to a bimodal output, that multimodal inputs are no more informative than bimodal inputs, and that a chain of up-regulations outperforms a chain of down-regulations. We anticipate that this numerical approach may be useful for modeling noise in a variety of small network topologies in biology."

"Network inference approaches are now widely used in biological applications to probe regulatory relationships between molecular components such as genes or proteins. Many methods have been proposed for this setting, but the connections and differences between their statistical formulations have received less attention. In this paper, we show how a broad class of statistical network inference methods, including a number of existing approaches, can be described in terms of variable selection for the linear model. This reveals some subtle but important differences between the methods, including the treatment of time intervals in discretely observed data. In developing a general formulation, we also explore the relationship between single-cell stochastic dynamics and network inference on averages over cells. This clarifies the link between biochemical networks as they operate at the cellular level and network inference as carried out on data that are averages over populations of cells. We present empirical results, comparing thirty-two network inference methods that are instances of the general formulation we describe, using two published dynamical models. Our investigation sheds light on the applicability and limitations of network inference and provides guidance for practitioners and suggestions for experimental design."

"We study a mechanism for reliable switching in biomolecular signal-transduction cascades. Steady bistable states are created by system-size cooperative effects in populations of proteins, in spite of the fact that the phosphorylation-state transitions of any molecule, by means of which the switch is implemented, are highly stochastic. The emergence of switching is a nonequilibrium phase transition in an energetically driven, dissipative system described by a master equation. We use operator and functional integral methods from reaction-diffusion theory to solve for the phase structure, noise spectrum, and escape trajectories and first-passage times of a class of minimal models of switches, showing how all critical properties for switch behavior can be computed within a unified framework."

"Cellular function is widely believed to be organized in a modular fashion. On all scales and at all levels of complexity, relatively independent sub-units perform relatively independent sub-tasks of biological function. This functional modularity must be reflected in the topology of molecular networks. But how a functional module should be represented in an interaction network is an open question. In protein-interaction networks (PIN), one can identify a protein-complex as a module on a small scale, i.e. modules are understood as densely linked, resp. interacting, groups of proteins, that are only sparsely interacting with the rest of the network.
In this contribution, we show that extrapolating this concept of cohesively linked clusters of proteins as modules to the scale of the entire PIN inevitable misses important and functionally relevant structure inherent in the network. As an alternative, we introduce a novel way of decomposing a network into functional roles and show that this represents network structure and function more efficiently. This finding should have a profound impact on all module assisted methods of protein function prediction and should shed new light on how functional modules can be represented in molecular interaction networks in general."

"A network observed in a particular context may appear to have "unusual" properties. To quantify this, it is appropriate to randomize the network and test the hypothesis that the network is not statistically different from expected in a motivated ensemble. However, when dealing with metabolic networks, the straightforward randomization of the network generates fictitious reactions that are biochemically meaningless. Here we provide several natural ensembles for randomizing such metabolic networks. A first constraint is to use valid biochemical reactions. Further constraints correspond to imposing appropriate functional constraints. We explain how to perform these randomizations and show how they allow one to approach the properties of biological metabolic networks. An implication of the present work is that the observed global structural properties of real metabolic networks are likely to be the consequence of simple biochemical and functional constraints."

"Cells are complex objects, representing a multitude of structures and processes. In order to understand the organization, interaction and hierarchy of these structures and processes, a quantitative understanding is absolutely critical. Traditionally, statistical mechanics-based treatment of biological systems has focused on the molecular level, with larger systems being ignored. This book integrates understanding from the molecular to the cellular and multi-cellular level in a quantitative framework that will benefit a wide audience engaged in biological, biochemical, biophysical and clinical research. It will build new bridges of quantitative understanding that link fundamental physical principles governing cellular structure and function with implications in clinical and biomedical contexts."

"The relationship between a network's degree-degree correlation and a loose version of graph coloring is studied on networks with broad degree distributions. We find that, given similar conditions on the number of nodes, number of links, and clustering levels, fewer colors are needed to color disassortative than assortative networks. Since fewer colors create fewer independent sets, our finding implies that disassortative networks may have higher concurrency potential than assortative networks. This in turn suggests another reason for the disassortative mixing pattern observed in biological networks such as those of protein-protein interaction and gene regulation. In addition to the functional specificity and stability suggested by Maslov and Sneppen, a disassortative network topology may also enhance the ability of cells to perform crucial tasks concurrently..." Related to Judd/Kearns experiments on human graph coloring?

For that final exam...

"The dynamic properties and independence structure of stochastic kinetic models (SKMs) .., An SKM is a highly multivariate jump process used to model chemical reaction networks.. We identify SKM subprocesses with the corresponding counting processes and propose a directed, cyclic graph (the kinetic independence graph or KIG) that encodes the local independence structure of their conditional intensities. Given a partition [A, D, B] of the vertices, the graphical separation A ⊥ B|D in the undirected KIG has an intuitive chemical interpretation and implies that A is locally independent of B given A ∪ D. ... this separation also results in global independence of the internal histories of A and B conditional on a history of the jumps in D which ... mathematical definition of a modularization of an SKM using its implied dynamics. Graphical decomposition methods are developed for the identification and efficient computation of nested modularizations. "

"Biochemical networks are often called upon to illustrate emergent properties of living systems. In this contribution, I question such emergentist claims by means of theoretical work on genetic regulatory models and random Boolean networks. If the existence of a critical connectivity Kc of such networks has often been coined “emergent” or “irreducible”, I propose on the contrary that the existence of a critical connectivity Kc is indeed mathematically explainable in network theory. This conclusion also applies to many other types of formal networks and weakens the emergentist claim attached to bio-molecular networks, and by extension to living systems."

"Regulatory interactions between genes show a large amount of cross-species variability, even when the underlying functions are conserved ... investigate the ability of regulatory networks to reproduce given expression levels within a simple model of gene regulation ... find an exponentially large space of regulatory networks compatible with a given set of expression level"

"we analyze a comprehensive data set of protein-protein and transcriptional regulatory interaction networks in yeast, an E. coli metabolic network, and gene activity profiles for different metabolic states in both organisms. We show that in all cases the networks have a heavy-tailed distribution, but most of them present significant differences from a power-law model according to a stringent statistical test. Those few data sets that have a statistically significant fit with a power-law model follow other distributions equally well. Thus, while our analysis supports that both global connectivity interaction networks and activity distributions are heavy-tailed, they are not generally described by any specific distribution model, leaving space for further inferences on generative models."

Worth using in the Annals project?

The Gaussian-approximation bit seems pretty dubious. But this is a very good idea.

I'm kinda dubious from the abstract.

"How does a single-cell creature, such as an amoeba ... hunt living prey, respond to lights, sounds, and smells, and display complex sequences of movements without the benefit of a nervous system? This book offers a startling and original answer. ... taps the findings of the new discipline of systems biology to show that the internal chemistry of living cells is a form of computation. Cells are built out of molecular circuits that perform logical operations, as electronic devices do, but with unique properties. Bray argues that the computational juice of cells provides the basis of all the distinctive properties of living systems: it allows organisms to embody in their internal structure an image of the world, and this accounts for their adaptability, responsiveness, and intelligence."

(An "original answer" only if you've never heard of Norbert Wiener or Jacques Monod, but it still looks worth reading.)

Not very scale-free at all. Now, to be fair, they try to fit power laws to the _whole_ degree distribution, and most of the models would, strictly, only predict it only for the upper tails of the distributions --- but it's quite decisive that it's not completely scale-free.

"a guide to the growing literature which approaches the phenomena of cell biology from a more theoretical point of view. We begin with the building blocks of cellular networks, and proceed toward the different classes of models being explored, finally discussing the "design principles" which have been suggested for these systems. Although largely a dispassionate review, we do draw attention to areas where there seems to be general consensus on ideas that have not been tested very thoroughly and, more optimistically, to areas where we feel promising ideas deserve to be more fully explored."

How much of this should I inflict on my students in 462 next semester?

Blurb, table of contents, ch. 1 (not yet read) --- if they really make a connection between their regulatory models and the rest of it, that'd be really exciting. If not, not so much. Check out from library.  --- ETA: Disappointing; standard ML techniques, plus "and then you could this to gene chip data".

Jesus Haploid Christ, someone did Stu Kauffman's "shuffle the punch cards" experiment with real E. coli!