Reconstruction of novel transcription factor regulons through inference of their binding sites.

BACKGROUND: In most sequenced organisms the number of known regulatory genes (e.g., transcription factors (TFs)) vastly exceeds the number of experimentally-verified regulons that could be associated with them. At present, identification of TF regulons is mostly done through comparative genomics approaches. Such methods could miss organism-specific regulatory interactions and often require expensive and time-consuming experimental techniques to generate the underlying data. RESULTS: In this work, we present an efficient algorithm that aims to identify a given transcription factor's regulon through inference of its unknown binding sites, based on the discovery of its binding motif. The proposed approach relies on computational methods that utilize gene expression data sets and knockout fitness data sets which are available or may be straightforwardly obtained for many organisms. We computationally constructed the profiles of putative regulons for the TFs LexA, PurR and Fur in E. coli K12 and identified their binding motifs. Comparisons with an experimentally-verified database showed high recovery rates of the known regulon members, and indicated good predictions for the newly found genes with high biological significance. The proposed approach is also applicable to novel organisms for predicting unknown regulons of the transcriptional regulators. Results for the hypothetical protein D d e0289 in D. alaskensis include the discovery of a Fis-type TF binding motif. CONCLUSIONS: The proposed motif-based regulon inference approach can discover the organism-specific regulatory interactions on a single genome, which may be missed by current comparative genomics techniques due to their limitations.

Designing DNA barcodes orthogonal in melting temperature by simulated annealing optimization.

Molecular barcode arrays are widely employed in the analysis of large strain libraries, whereby probes linked to unique oligonucleotides ("antitags") are used to detect selected DNA targets ("tags") by highly specific hybridization. One of the major problems for such screen designs is thus insuring a high degree of probe-target specificity and a low level of nonspecific binding (in sum, "orthogonality") across the entire tag population ("collection"). Several approaches have been previously proposed for designing orthogonal DNA tags by-among others-focusing on their individual or pair-wise structures, such as Smith Waterman sequence similarity, the widely used nearest neighbor method, and full thermodynamic estimates of sequences. However, these methods generally involve imposing various heuristic constraints ("design rules") on possible tag/antitag (TaT) sequences in order to achieve probe-target specificity across the collection. The resulting lack of freedom in considering all putative sequences can lead to potentially suboptimal designs and to the ensuing reduction in the degree of orthogonality within the constructed TaT collections. Here, we demonstrate that a randomized-search algorithm based on simulated annealing optimization can be used in order to substantially free the design process from the limitations of sequence constraints-allowing for the elucidation of potentially more optimal DNA tag collections. The designed sets of DNA oligonucleotides are optimized for the highest degree of orthogonality as quantified by melting temperature Tm-an experimentally relevant system property, which could also be used as a theoretically meaningful thermodynamic metric for optimizing TaT binding specificity. That is, this work describes an approach to constructing tag/antitag libraries, which offer the greatest melting temperature separation between specific probe-target duplexes and other nonspecific structures. The proposed method finds, with high probability, the global solution that maximizes the difference in Tm between the specific and nonspecific tag-antitag hybridizations across a collection of given size for TaTs of specified length. An application of this approach is demonstrated using 2 different DNA probe sets.

Inference of gene regulatory networks from genome-wide knockout fitness data.

MOTIVATION: Genome-wide fitness is an emerging type of high-throughput biological data generated for individual organisms by creating libraries of knockouts, subjecting them to broad ranges of environmental conditions, and measuring the resulting clone-specific fitnesses. Since fitness is an organism-scale measure of gene regulatory network behaviour, it may offer certain advantages when insights into such phenotypical and functional features are of primary interest over individual gene expression. Previous works have shown that genome-wide fitness data can be used to uncover novel gene regulatory interactions, when compared with results of more conventional gene expression analysis. Yet, to date, few algorithms have been proposed for systematically using genome-wide mutant fitness data for gene regulatory network inference. RESULTS: In this article, we describe a model and propose an inference algorithm for using fitness data from knockout libraries to identify underlying gene regulatory networks. Unlike most prior methods, the presented approach captures not only structural, but also dynamical and non-linear nature of biomolecular systems involved. A state-space model with non-linear basis is used for dynamically describing gene regulatory networks. Network structure is then elucidated by estimating unknown model parameters. Unscented Kalman filter is used to cope with the non-linearities introduced in the model, which also enables the algorithm to run in on-line mode for practical use. Here, we demonstrate that the algorithm provides satisfying results for both synthetic data as well as empirical measurements of GAL network in yeast Saccharomyces cerevisiae and TyrR-LiuR network in bacteria Shewanella oneidensis. AVAILABILITY: MATLAB code and datasets are available to download at http://www.duke.edu/∼lw174/Fitness.zip and http://genomics.lbl.gov/supplemental/fitness-bioinf/

Bayesian multiple-instance motif discovery with BAMBI: inference of recombinase and transcription factor binding sites.

Finding conserved motifs in genomic sequences represents one of essential bioinformatic problems. However, achieving high discovery performance without imposing substantial auxiliary constraints on possible motif features remains a key algorithmic challenge. This work describes BAMBI-a sequential Monte Carlo motif-identification algorithm, which is based on a position weight matrix model that does not require additional constraints and is able to estimate such motif properties as length, logo, number of instances and their locations solely on the basis of primary nucleotide sequence data. Furthermore, should biologically meaningful information about motif attributes be available, BAMBI takes advantage of this knowledge to further refine the discovery results. In practical applications, we show that the proposed approach can be used to find sites of such diverse DNA-binding molecules as the cAMP receptor protein (CRP) and Din-family site-specific serine recombinases. Results obtained by BAMBI in these and other settings demonstrate better statistical performance than any of the four widely-used profile-based motif discovery methods: MEME, BioProspector with BioOptimizer, SeSiMCMC and Motif Sampler as measured by the nucleotide-level correlation coefficient. Additionally, in the case of Din-family recombinase target site discovery, the BAMBI-inferred motif is found to be the only one functionally accurate from the underlying biochemical mechanism standpoint. C++ and Matlab code is available at http://www.ee.columbia.edu/~guido/BAMBI or http://genomics.lbl.gov/BAMBI/.

Temperature control of fimbriation circuit switch in uropathogenic Escherichia coli: quantitative analysis via automated model abstraction.

Uropathogenic Escherichia coli (UPEC) represent the predominant cause of urinary tract infections (UTIs). A key UPEC molecular virulence mechanism is type 1 fimbriae, whose expression is controlled by the orientation of an invertible chromosomal DNA element-the fim switch. Temperature has been shown to act as a major regulator of fim switching behavior and is overall an important indicator as well as functional feature of many urologic diseases, including UPEC host-pathogen interaction dynamics. Given this panoptic physiological role of temperature during UTI progression and notable empirical challenges to its direct in vivo studies, in silico modeling of corresponding biochemical and biophysical mechanisms essential to UPEC pathogenicity may significantly aid our understanding of the underlying disease processes. However, rigorous computational analysis of biological systems, such as fim switch temperature control circuit, has hereto presented a notoriously demanding problem due to both the substantial complexity of the gene regulatory networks involved as well as their often characteristically discrete and stochastic dynamics. To address these issues, we have developed an approach that enables automated multiscale abstraction of biological system descriptions based on reaction kinetics. Implemented as a computational tool, this method has allowed us to efficiently analyze the modular organization and behavior of the E. coli fimbriation switch circuit at different temperature settings, thus facilitating new insights into this mode of UPEC molecular virulence regulation. In particular, our results suggest that, with respect to its role in shutting down fimbriae expression, the primary function of FimB recombinase may be to effect a controlled down-regulation (rather than increase) of the ON-to-OFF fim switching rate via temperature-dependent suppression of competing dynamics mediated by recombinase FimE. Our computational analysis further implies that this down-regulation mechanism could be particularly significant inside the host environment, thus potentially contributing further understanding toward the development of novel therapeutic approaches to UPEC-caused UTIs.

Stochastic bimodalities in deterministically monostable reversible chemical networks due to network topology reduction.

Recently, stochastic simulations of networks of chemical reactions have shown distributions of steady states that are inconsistent with the steady state solutions of the corresponding deterministic ordinary differential equations. One such class of systems is comprised of networks that have irreversible reactions, and the origin of the anomalous behavior in these cases is understood to be due to the existence of absorbing states. More puzzling is the report of such anomalies in reaction networks without irreversible reactions. One such biologically important example is the futile cycle. Here we show that, in these systems, nonclassical behavior can originate from a stochastic elimination of all the molecules of a key species. This leads to a reduction in the topology of the network and the sampling of steady states corresponding to a truncated network. Surprisingly, we find that, in spite of the purely discrete character of the topology reduction mechanism revealed by "exact" numerical solutions of the master equations, this phenomenon is reproduced by the corresponding Fokker-Planck equations.

From fluctuations to phenotypes: the physiology of noise.

There are fundamental physical reasons why biochemical processes might be subject to noise and stochastic fluctuations. Indeed, it has long been understood that random molecular-scale mechanisms, such as those that drive genetic mutation, lie at the heart of population-scale evolutionary dynamics. What we can now appreciate is how stochastic fluctuations inherent in biochemical processes contribute to cellular and organismal phenotypes. Advancements in techniques for empirically measuring single cells and in corresponding theoretical methods have enabled the rigorous design and interpretation of experiments that provide incontrovertible proof that there are important endogenous sources of stochasticity that drive biological processes at the scale of individual organisms. Recently, some studies have progressed beyond merely ascertaining the presence of noise in biological systems; they trace its role in cellular physiology as it is passed through and processed by the biomolecular pathways-from the underlying origins of stochastic fluctuations in random biomolecular interactions to their ultimate manifestations in characteristic species phenotypes. These emerging results suggest new biological network design principles that account for a constructive role played by noise in defining the structure, function, and fitness of biological systems. They further show that stochastic mechanisms open novel classes of regulatory, signaling, and organizational choices that can serve as efficient and effective biological solutions to problems that are more complex, less robust, or otherwise suboptimal to deal with in the context of purely deterministic systems. Research in Drosophila melanogaster eye color-vision development and Bacillus subtilis competence induction has elegantly traced the role of noise in vital physiological processes from fluctuations to phenotypes, and is used here to highlight these developments.

Deviant effects in molecular reaction pathways.

In biological networks, any manifestations of behaviors substantially 'deviant' from the predictions of continuous-deterministic classical chemical kinetics (CCK) are typically ascribed to systems with complex dynamics and/or a small number of molecules. Here we show that in certain cases such restrictions are not obligatory for CCK to be largely incorrect. By systematically identifying properties that may cause significant divergences between CCK and the more accurate discrete-stochastic chemical master equation (CME) system descriptions, we comprehensively characterize potential CCK failure patterns in biological settings, including consequences of the assertion that CCK is closer to the 'mode' rather than the 'average' of stochastic reaction dynamics, as generally perceived. We demonstrate that mechanisms underlying such nonclassical effects can be very simple, are common in cellular networks and result in often unintuitive system behaviors. This highlights the importance of deviant effects in biotechnologically or biomedically relevant applications, and suggests some approaches to diagnosing them in situ.