Easily repairable networks: reconnecting nodes after damage.

We introduce a simple class of distribution networks that withstand damage by being repairable instead of redundant. Instead of asking how hard it is to disconnect nodes through damage, we ask how easy it is to reconnect nodes after damage. We prove that optimal networks on regular lattices have an expected cost of reconnection proportional to the lattice length, and that such networks have exactly three levels of structural hierarchy. We extend our results to networks subject to repeated attacks, in which the repairs themselves must be repairable. We find that, in exchange for a modest increase in repair cost, such networks are able to withstand any number of attacks.

Detecting separate time scales in genetic expression data.

BACKGROUND: Biological processes occur on a vast range of time scales, and many of them occur concurrently. As a result, system-wide measurements of gene expression have the potential to capture many of these processes simultaneously. The challenge however, is to separate these processes and time scales in the data. In many cases the number of processes and their time scales is unknown. This issue is particularly relevant to developmental biologists, who are interested in processes such as growth, segmentation and differentiation, which can all take place simultaneously, but on different time scales. RESULTS: We introduce a flexible and statistically rigorous method for detecting different time scales in time-series gene expression data, by identifying expression patterns that are temporally shifted between replicate datasets. We apply our approach to a Saccharomyces cerevisiae cell-cycle dataset and an Arabidopsis thaliana root developmental dataset. In both datasets our method successfully detects processes operating on several different time scales. Furthermore we show that many of these time scales can be associated with particular biological functions. CONCLUSIONS: The spatiotemporal modules identified by our method suggest the presence of multiple biological processes, acting at distinct time scales in both the Arabidopsis root and yeast. Using similar large-scale expression datasets, the identification of biological processes acting at multiple time scales in many organisms is now possible.

Phase transition creates the geometry of the continuum from discrete space.

Models of discrete space and space-time that exhibit continuum-like behavior at large lengths could have profound implications for physics. They may help tame the infinities arising from quantizing gravity, and remove the need for the machinery of the real numbers; a construct with no direct observational support. However, despite many attempts to build discrete space, researchers have failed to produce even the simplest geometries. Here we investigate graphs as the most elementary discrete models of two-dimensional space. We show that if space is discrete, it must be disordered, by proving that all planar lattice graphs exhibit a taxicab metric similar to square grids. We then give an explicit recipe for growing disordered discrete space by sampling a Boltzmann distribution of graphs at low temperature. Finally, we propose three conditions which any discrete model of Euclid's plane must meet: have a Hausdorff dimension of 2, support unique straight lines, and obey Pythagoras' theorem. Our model satisfies all three, resulting in a discrete model in which continuum-like behavior emerges at large lengths.

How much non-coding DNA do eukaryotes require?

Despite tremendous advances in the field of genomics, the amount and function of the large non-coding part of the genome in higher organisms remains poorly understood. Here we report an observation, made for 37 fully sequenced eukaryotic genomes, which indicates that eukaryotes require a certain minimum amount of non-coding DNA (ncDNA). This minimum increases quadratically with the amount of DNA located in exons. Based on a simple model of the growth of regulatory networks, we derive a theoretical prediction of the required quantity of ncDNA and find it to be in excellent agreement with the data. The amount of additional ncDNA (in basepairs) which eukaryotes require obeys N(DEF)=1/2 (N(C)/N(P)) (N(C)-N(P)), where N(C) is the amount of exonic DNA, and N(P) is a constant of about 10 Mb. This value N(DEF) corresponds to a few percent of the genome in Homo sapiens and other mammals, and up to half the genome in simpler eukaryotes. Thus, our findings confirm that eukaryotic life depends on a substantial fraction of ncDNA and also make a prediction of the size of this fraction, which matches the data closely.

Protein design depends on the size of the amino acid alphabet.

We consider the design of proteins to be simultaneously thermodynamically stable in multiple independent and correlated conformations. We first show that a protein can be trained to fold to multiple independent conformations and calculate its capacity. The number of configurations that it can remember is proportional to the logarithm of the number of amino acid species A, independent of chain length. Next we investigate the recognition of correlated conformations, which we apply to funnel design around a single configuration. The maximum basin of attraction, as parametrized in our model, also depends on the number of amino acid species as ln A. We argue that the extent to which the protein energy landscape can be manipulated is fixed, effecting a trade off between well breadth, well depth, and well number. This emerging picture motivates a clearer understanding of the scope and limits of protein and heteropolymer function.

Characterization of the probabilistic traveling salesman problem.

We show that stochastic annealing can be successfully applied to gain new results on the probabilistic traveling salesman problem. The probabilistic "traveling salesman" must decide on an a priori order in which to visit n cities (randomly distributed over a unit square) before learning that some cities can be omitted. We find the optimized average length of the pruned tour follows E(L(pruned))=sqrt[np](0.872-0.105p)f(np), where p is the probability of a city needing to be visited, and f(np)-->1 as np--> infinity. The average length of the a priori tour (before omitting any cities) is found to follow E(L(a priori))=sqrt[n/p]beta(p), where beta(p)=1/[1.25-0.82 ln(p)] is measured for 0.05< or =p< or =0.6. Scaling arguments and indirect measurements suggest that beta(p) tends towards a constant for p<0.03. Our stochastic annealing algorithm is based on limited sampling of the pruned tour lengths, exploiting the sampling error to provide the analog of thermal fluctuations in simulated (thermal) annealing. The method has general application to the optimization of functions whose cost to evaluate rises with the precision required.

Comparison of pattern detection methods in microarray time series of the segmentation clock.

While genome-wide gene expression data are generated at an increasing rate, the repertoire of approaches for pattern discovery in these data is still limited. Identifying subtle patterns of interest in large amounts of data (tens of thousands of profiles) associated with a certain level of noise remains a challenge. A microarray time series was recently generated to study the transcriptional program of the mouse segmentation clock, a biological oscillator associated with the periodic formation of the segments of the body axis. A method related to Fourier analysis, the Lomb-Scargle periodogram, was used to detect periodic profiles in the dataset, leading to the identification of a novel set of cyclic genes associated with the segmentation clock. Here, we applied to the same microarray time series dataset four distinct mathematical methods to identify significant patterns in gene expression profiles. These methods are called: Phase consistency, Address reduction, Cyclohedron test and Stable persistence, and are based on different conceptual frameworks that are either hypothesis- or data-driven. Some of the methods, unlike Fourier transforms, are not dependent on the assumption of periodicity of the pattern of interest. Remarkably, these methods identified blindly the expression profiles of known cyclic genes as the most significant patterns in the dataset. Many candidate genes predicted by more than one approach appeared to be true positive cyclic genes and will be of particular interest for future research. In addition, these methods predicted novel candidate cyclic genes that were consistent with previous biological knowledge and experimental validation in mouse embryos. Our results demonstrate the utility of these novel pattern detection strategies, notably for detection of periodic profiles, and suggest that combining several distinct mathematical approaches to analyze microarray datasets is a valuable strategy for identifying genes that exhibit novel, interesting transcriptional patterns.

Identifying genes from up-down properties of microarray expression series.

MOTIVATION: We consider any collection of microarrays that can be ordered to form a progression; for example, as a function of time, severity of disease or dose of a stimulant. By plotting the expression level of each gene as a function of time, or severity, or dose, we form an expression series, or curve, for each gene. While most of these curves will exhibit random fluctuations, some will contain a pattern, and these are the genes that are most likely associated with the quantity used to order them. RESULTS: We introduce a method of identifying the pattern and hence genes in microarray expression curves without knowing what kind of pattern to look for. Key to our approach is the sequence of ups and downs formed by pairs of consecutive data points in each curve. As a benchmark, we blindly identified genes from yeast cell cycles without selecting for periodic or any other anticipated behaviour. CONTACT: tmf20@cam.ac.uk SUPPLEMENTARY INFORMATION: The complete versions of Table 2 and Figure 4, as well as other material, can be found at http://www.lps.ens.fr/~willbran/up-down/ or http://www.tcm.phy.cam.ac.uk/~tmf20/up-down/

Sequence determination from overlapping fragments: a simple model of whole-genome shotgun sequencing.

Assembling fragments randomly sampled from along a sequence is the basis of whole-genome shotgun sequencing, a technique used to map the DNA of the human and other genomes. We calculate the probability that a random sequence can be recovered from a collection of overlapping fragments. We provide an exact solution for an infinite alphabet and in the case of constant overlaps. For the general problem we apply two assembly strategies and give the probability that the assembly puzzle can be solved in the limit of infinitely many fragments.

Stochastic annealing.

We show how to simulate a system in thermal equilibrium when the energy cannot be evaluated exactly: the error distribution needs to be symmetric, but it does not need to be known. We also solve the Ceperley-Dewing version of this problem, where the error distribution is taken to be fully known. These underlying ideas give an effective optimization strategy for problems where the evaluation of each design can be sampled only statistically, including an application to protein folding.