New experimental results on bacterial growth inspire a novel top-down approach to study cell metabolism, combining mass balance and proteomic constraints to extend and complement Flux Balance Analysis. We introduce here Constrained Allocation Flux Balance Analysis, CAFBA, in which the biosynthetic costs associated to growth are accounted for in an effective way through a single additional genome-wide constraint. Its roots lie in the experimentally observed pattern of proteome allocation for metabolic functions, allowing to bridge regulation and metabolism in a transparent way under the principle of growth-rate maximization. We provide a simple method to solve CAFBA efficiently and propose an "ensemble averaging" procedure to account for unknown protein costs. Applying this approach to modeling E. coli metabolism, we find that, as the growth rate increases, CAFBA solutions cross over from respiratory, growth-yield maximizing states (preferred at slow growth) to fermentative states with carbon overflow (preferred at fast growth). In addition, CAFBA allows for quantitatively accurate predictions on the rate of acetate excretion and growth yield based on only 3 parameters determined by empirical growth laws.

Cells employ a myriad of signaling circuits to detect environmental signals and drive specific gene expression responses. A common motif in these circuits is inducible auto-activation: a transcription factor that activates its own transcription upon activation by a ligand or by post-transcriptional modification. Examples range from the two-component signaling systems in bacteria and plants to the genetic circuits of animal viruses such as HIV. We here present a theoretical study of such circuits, based on analytical calculations, numerical computations, and simulation. Our results reveal several surprising characteristics. They show that auto-activation can drastically enhance the sensitivity of the circuit's response to input signals: even without molecular cooperativity, an ultra-sensitive threshold response can be obtained. However, the increased sensitivity comes at a cost: auto-activation tends to severely slow down the speed of induction, a stochastic effect that was strongly underestimated by earlier deterministic models. This slow-induction effect again requires no molecular cooperativity and is intimately related to the bimodality recently observed in non-cooperative auto-activation circuits. These phenomena pose strong constraints on the use of auto-activation in signaling networks. To achieve both a high sensitivity and a rapid induction, an inducible auto-activation circuit is predicted to acquire low cooperativity and low fold-induction. Examples from Escherichia coli's two-component signaling systems support these predictions.

MOTIVATION: Neighbor-dependent substitution processes generated specific pattern of dinucleotide frequencies in the genomes of most organisms. The CpG-methylation-deamination process is, e.g. a prominent process in vertebrates (CpG effect). Such processes, often with unknown mechanistic origins, need to be incorporated into realistic models of nucleotide substitutions. RESULTS: Based on a general framework of nucleotide substitutions we developed a method that is able to identify the most relevant neighbor-dependent substitution processes, estimate their relative frequencies and judge their importance in order to be included into the modeling. Starting from a model for neighbor independent nucleotide substitution we successively added neighbor-dependent substitution processes in the order of their ability to increase the likelihood of the model describing given data. The analysis of neighbor-dependent nucleotide substitutions based on repetitive elements found in the genomes of human, zebrafish and fruit fly is presented. AVAILABILITY: A web server to perform the presented analysis is freely available at: http://evogen.molgen.mpg.de/server/substitution-analysis

MOTIVATION: Substantial regional variations of substitutional processes have recently been reported from human/mouse comparisons. However, several features including the C + G dependence and the CpG-based transition effect remain obscure. RESULTS: Utilizing the vast amount of transposable elements in the human genome, we performed detailed analysis of the substitutional and insertion/deletion patterns along the human lineage in a regional and time-resolved fashion. We observed a drastic increase in the CpG-based transition frequency at about the time of the mammalian radiation. We also observed clear regional biases of substitution patterns, most notably a bias to enrich the C+G content toward the telomeres. AVAILABILITY: The programs used are available upon request from the authors.

We introduce a model of DNA sequence evolution which can account for biases in mutation rates that depend on the identity of the neighboring bases. An analytic solution for this class of models is developed by adopting well-known methods of nonlinear dynamics. Results are presented for the CpG-methylation-deamination process which dominates point substitutions in vertebrates. The dinucleotide frequencies generated by the model (using empirically obtained mutation rates) match the overall pattern observed in non-coding DNA. A web-based tool has been constructed to compute single- and dinucleotide frequencies for arbitrary neighbor-dependent mutation rates. Also provided is the backward procedure to infer the mutation rates using maximum likelihood analysis given the observed single- and dinucleotide frequencies. Reasonable estimates of the mutation rates can be obtained very efficiently, using generic non-coding DNA sequences as input, after masking out long homonucleotide subsequences. Our method is much more convenient and versatile to use than the traditional method of deducing mutation rates by counting mutation events in carefully chosen sequences. More generally, our approach provides a more realistic but still tractable description of non-coding genomic DNA, and may be used as a null model for various sequence analysis applications.

MOTIVATION: The DNA microarray technology can generate a large amount of data describing the time-course of gene expression. These data, when properly interpreted, can yield a great deal of information concerning differential gene expression during development. Much current effort in bioinformatics has been devoted to the analysis of gene expression data, usually via some 'clustering analysis' on the raw data in some abstract high dimensional space. Here, we describe a method where we first 'process' the raw time-course data using a simple biologically based kinetic model of gene expression. This allows us to reduce the vast data to a few vital attributes characterizing each expression profile, e.g. the times of the onset and cessation of the expression of the developmentally regulated genes. These vital attributes can then be trivially clustered by visual inspection to reveal biologically significant effects. RESULTS: We have applied this approach to microarray expression data from samples isolated every 2 h throughout the 24 h developmental program of Dictyostelium discoideum. mRNA accumulation patterns for 50 developmental genes were found to fit the kinetic model with a p-value of 0.05 or better. Transcription of these genes appears to be initiated in bursts at well-defined periods during development, in a manner suggestive of a dependent sequence. This approach can be applied to analyses of other temporal gene expression patterns, including those of the cell cycle.

The score statistics of a recently introduced 'hybrid alignment' algorithm is studied in detail numerically. An extensive survey across the 2216 models of protein domains contained in the Pfam v5.4 database (Bateman et al., Nucleic Acids Res., 28, 263-266, 2000) verifies the theoretical predictions: For the position-specific scoring functions used in the Pfam models, the score statistics of hybrid alignment obey the Gumbel distribution, with the key Gumbel parameter lambda taking on the asymptotic value 1 universally for all models. Thus, the use of hybrid alignment eliminates the time-consuming computer simulations normally needed to assign p-values to alignment scores, freeing the users to experiment with different scoring parameters and functions. The performance of the hybrid algorithm in detecting sequence homology is also studied. For protein sequences from the SCOP database (Murzin et al., J. Mol. Biol., 247, 536-540, 1995) using uniform scoring functions, the performance is found to be comparable to the best of the existing methods. Preliminary results using the PfamA database suggest that the hybrid algorithm achieves similar performance as existing methods for position-specific scoring systems as well. Hybrid alignment is thereby established as a high performance alignment algorithm with well-characterized, universal statistics.

The statistical properties of local alignment algorithms with gaps are analyzed theoretically for uucorrelated and corre-lated random sequences. In the viciuity of the log-linear phase transition, the statistics of alignment with gaps is shone to be characteristically different from that of gap-less alignment. The optimal scores obtained for uncorre-lated sequences obey certain robust scaling laws. Deviation from these scaling laws signals sequence homology, and can be used to guide the empirical selection of scoring parame-ters for the optimal detection of sequence similarities. This can be accomplished in a computationally efficient way by using a novel approach focusing on the score profiles. Fur-thermore, by assmting a few gross features characterizing the statistics of underlying sequence-sequence correlations, quantitative criteria are obtained for the choice of optimal scoring parameters: Optimal similarity detection is most likely to occur in a region close to the log side of the log-linear phase transition