Search

Despite major environmental and genetic differences, microbial metabolic networks are known to generate consistent physiological outcomes across vastly different organisms. This remarkable robustness suggests that, at least in bacteria, metabolic activity may be guided by universal principles. The constrained optimization of evolutionarily motivated objective functions, such as the growth rate, has emerged as the key theoretical assumption for the study of bacterial metabolism. While conceptually and practically useful in many situations, the idea that certain functions are optimized is hard to validate in data. Moreover, it is not always clear how optimality can be reconciled with the high degree of single-cell variability observed in experiments within microbial populations. To shed light on these issues, we develop an inverse modeling framework that connects the fitness of a population of cells (represented by the mean single-cell growth rate) to the underlying metabolic variability through the maximum entropy inference of the distribution of metabolic phenotypes from data. While no clear objective function emerges, we find that, as the medium gets richer, the fitness and inferred variability for Escherichia coli populations follow and slowly approach the theoretically optimal bound defined by minimal reduction of variability at given fitness. These results suggest that bacterial metabolism may be crucially shaped by a population-level trade-off between growth and heterogeneity., A.B., A.D.M., A.P., and A.P.M. acknowledge financial support from Marie Skłodowska-Curie, grant agreement no. 734439(INFERNET).

Summary Topology determination is one of the most important intermediate steps toward building the atomic structure of proteins from their medium-resolution cryo-electron microscopy (cryo-EM) map. The main goal in the topology determination is to identify correct matches (i.e. assignment and direction) between secondary structure elements (SSEs) (α-helices and β-sheets) detected in a protein sequence and cryo-EM density map. Despite many recent advances in molecular biology technologies, the problem remains a challenging issue. To overcome the problem, this article proposes a linear programming-based topology determination (LPTD) method to solve the secondary structure topology problem in three-dimensional geometrical space. Through modeling of the protein’s sequence with the aid of extracting highly reliable features and a distance-based scoring function, the secondary structure matching problem is transformed into a complete weighted bipartite graph matching problem. Subsequently, an algorithm based on linear programming is developed as a decision-making strategy to extract the true topology (native topology) between all possible topologies. The proposed automatic framework is verified using 12 experimental and 15 simulated α–β proteins. Results demonstrate that LPTD is highly efficient and extremely fast in such a way that for 77% of cases in the dataset, the native topology has been detected in the first rank topology in Availability and implementation The LPTD package (source code and data) is publicly available at https://github.com/B-Behkamal/LPTD. Moreover, two test samples as well as the instruction of utilizing the graphical user interface have been provided in the shared readme file. Supplementary information Supplementary data are available at Bioinformatics online.

International audience; We present Annealed Mutational approximated Landscape (AMaLa), a new method to infer fitness landscapes from Directed Evolution experiments sequencing data. Such experiments typically start from a single wild-type sequence, which undergoes Darwinian in vitro evolution via multiple rounds of mutation and selection for a target phenotype. In the last years, Directed Evolution is emerging as a powerful instrument to probe fitness landscapes under controlled experimental conditions and as a relevant testing ground to develop accurate statistical models and inference algorithms (thanks to high-throughput screening and sequencing). Fitness landscape modeling either uses the enrichment of variants abundances as input, thus requiring the observation of the same variants at different rounds or assuming the last sequenced round as being sampled from an equilibrium distribution. AMaLa aims at effectively leveraging the information encoded in the whole time evolution. To do so, while assuming statistical sampling independence between sequenced rounds, the possible trajectories in sequence space are gauged with a time-dependent statistical weight consisting of two contributions: (i) an energy term accounting for the selection process and (ii) a generalized Jukes–Cantor model for the purely mutational step. This simple scheme enables accurately describing the Directed Evolution dynamics and inferring a fitness landscape that correctly reproduces the measures of the phenotype under selection (e.g., antibiotic drug resistance), notably outperforming widely used inference strategies. In addition, we assess the reliability of AMaLa by showing how the inferred statistical model could be used to predict relevant structural properties of the wild-type sequence.

The recent technological advances underlying the screening of large combinatorial libraries in high-throughput mutational scans deepen our understanding of adaptive protein evolution and boost its applications in protein design. Nevertheless, the large number of possible genotypes requires suitable computational methods for data analysis, the prediction of mutational effects, and the generation of optimized sequences. We describe a computational method that, trained on sequencing samples from multiple rounds of a screening experiment, provides a model of the genotype–fitness relationship. We tested the method on five large-scale mutational scans, yielding accurate predictions of the mutational effects on fitness. The inferred fitness landscape is robust to experimental and sampling noise and exhibits high generalization power in terms of broader sequence space exploration and higher fitness variant predictions. We investigate the role of epistasis and show that the inferred model provides structural information about the 3D contacts in the molecular fold.

Sequences of nucleotides (for DNA and RNA) or amino acids (for proteins) are central objects in biology. Among the most important computational problems is that of sequence alignment, i.e. arranging sequences from different organisms in such a way to identify similar regions, to detect evolutionary relationships between sequences, and to predict biomolecular structure and function. This is typically addressed through profile models, which capture position-specificities like conservation in sequences, but assume an independent evolution of different positions. Over the last years, it has been well established that coevolution of different amino-acid positions is essential for maintaining three-dimensional structure and function. Modeling approaches based on inverse statistical physics can catch the coevolution signal in sequence ensembles; and they are now widely used in predicting protein structure, protein-protein interactions, and mutational landscapes. Here, we present DCAlign, an efficient alignment algorithm based on an approximate message-passing strategy, which is able to overcome the limitations of profile models, to include coevolution among positions in a general way, and to be therefore universally applicable to protein- and RNA-sequence alignment without the need of using complementary structural information. The potential of DCAlign is carefully explored using well-controlled simulated data, as well as real protein and RNA sequences., 20 pages, 11 figures + Supplementary Information

The inverse problem is studied in multi-body systems with nonlinear dynamics representing, e.g., phase-locked wave systems, standard multimode and random lasers. Using a general model for four-body interacting complex-valued variables we test two methods based on pseudolikelihood, respectively with regularization and with decimation, to determine the coupling constants from sets of measured configurations. We test statistical inference predictions for increasing number of sampled configurations and for an externally tunable {\em temperature}-like parameter mimicing real data noise and helping minimization procedures. Analyzed models with phasors and rotors are generalizations of problems of real-valued spherical problems (e.g., density fluctuations), discrete spins (Ising and vectorial Potts) or finite number of states (standard Potts): inference methods presented here can, then, be straightforward applied to a large class of inverse problems., 9 pages, 9 figures

Clostridium cellulovorans is among the most promising candidates for consolidated bioprocessing (CBP) of cellulosic biomass to liquid biofuels (ethanol, butanol). C. cellulovorans metabolizes all the main plant polysaccharides and mainly produces butyrate. Since most butyrate and butanol biosynthetic reactions from acetyl-CoA are common, introduction of single heterologous alcohol/aldehyde dehydrogenase can divert the branching-point intermediate (butyryl-CoA) towards butanol production in this strain. However, engineering C. cellulovorans metabolic pathways towards industrial utilization requires better understanding of its metabolism. The present study aimed at improving comprehension of cellulose metabolism in C. cellulovorans by comparing growth kinetics, substrate consumption/product accumulation and whole-cell soluble proteome (data available via ProteomeXchange, identifier PXD015487) with those of the same strain grown on a soluble carbohydrate, glucose, as the main carbon source. Growth substrate-dependent modulations of the central metabolism were detected, including regulation of several glycolytic enzymes, fermentation pathways (e.g. hydrogenase, pyruvate formate lyase, phosphate transacetylase) and nitrogen assimilation (e.g. glutamate dehydrogenase). Overexpression of hydrogenase and increased ethanol production by glucose-grown bacteria suggest a more reduced redox state. Higher energy expenditure seems to occur in cellulose-grown C. cellulovorans (likely related to overexpression and secretion of (hemi-)cellulases), which induces up-regulation of ATP synthetic pathways, e.g. acetate production and ATP synthase. Significance: C. cellulovorans can metabolize all the main plant polysaccharides (cellulose, hemicelluloses and pectins) and, unlike other well established cellulolytic microorganisms, can produce butyrate. C. cellulovorans is therefore among the most attractive candidates for direct fermentation of lignocellulose to high-value chemicals and, especially, n-butanol, i.e. one of the most promising liquid biofuels for the future. Recent studies aimed at engineering n-butanol production in C. cellulovorans represent milestones towards production of biofuels through one-step fermentation of lignocellulose but also indicated that more detailed understanding of the C. cellulovorans central carbon metabolism is essential to refine metabolic engineering strategies towards improved n-butanol production in this strain. The present study helped identifying key genes associated with specific catabolic reactions and indicated modulations of central carbon metabolism (including redox and energy balance) associated with cellulose consumption. This information will be useful to determine key enzymes and possible metabolic bottlenecks to be addressed towards improved metabolic engineering of this strain.

Even if we know that two families of homologous proteins interact, we do not necessarily know, which specific proteins interact inside each species. The reason is that most families contain paralogs, i.e., more than one homologous sequence per species. We have developed a tool to predict interacting paralogs between the two protein families, which is based on the idea of inter-protein coevolution: our algorithm matches those members of the two protein families, which belong to the same species and collectively maximize the detectable coevolutionary signal. It is applicable even in cases, where simpler methods based, e.g., on genomic co-localization of genes coding for interacting proteins or orthology-based methods fail. In this method paper, we present an efficient implementation of this idea based on freely available software.

Tomographic image reconstruction can be mapped to a problem of finding solutions to a large system of linear equations which maximize a function that includes \textit{a priori} knowledge regarding features of typical images such as smoothness or sharpness. This maximization can be performed with standard local optimization tools when the function is concave, but it is generally intractable for realistic priors, which are non-concave. We introduce a new method to reconstruct images obtained from Radon projections by using Expectation Propagation, which allows us to reframe the problem from an Bayesian inference perspective. We show, by means of extensive simulations, that, compared to state-of-the-art algorithms for this task, Expectation Propagation paired with very simple but non log-concave priors, is often able to reconstruct images up to a smaller error while using a lower amount of information per pixel. We provide estimates for the critical rate of information per pixel above which recovery is error-free by means of simulations on ensembles of phantom and real images., Comment: 12 pages, 6 figures

We propose and test improvements to state-of-the-art techniques of Bayeasian statistical inference based on pseudolikelihood maximization with $\ell_1$ regularization and with decimation. In particular, we present a method to determine the best value of the regularizer parameter starting from a hypothesis testing technique. Concerning the decimation, we also analyze the worst case scenario in which there is no sharp peak in the tilded-pseudolikelihood function, firstly defined as a criterion to stop the decimation. Techniques are applied to noisy systems with non-linear dynamics, mapped onto multi-variable interacting Hamiltonian effective models for waves and phasors. Results are analyzed varying the number of available samples and the externally tunable temperature-like parameter mimicing real data noise. Eventually the behavior of inference procedures described are tested against a wrong hypothesis: non-linearly generated data are analyzed with a pairwise interacting hypothesis. Our analysis shows that, looking at the behavior of the inverse graphical problem as data size increases, the methods exposed allow to rule out a wrong hypothesis., Comment: 37 pages, 24 figures

Gene expression is a noisy process and several mechanisms, both transcriptional and post-transcriptional, can stabilize protein levels in cells. Much work has focused on the role of miRNAs, showing in particular that miRNA-mediated regulation can buffer expression noise for lowly expressed genes. Here, using in silico simulations and mathematical modeling, we demonstrate that miRNAs can exert a much broader influence on protein levels by orchestrating competition-induced crosstalk between mRNAs. Most notably, we find that miRNA-mediated cross-talk (i) can stabilize protein levels across the full range of gene expression rates, and (ii) modifies the correlation pattern of co-regulated interacting proteins, changing the sign of correlations from negative to positive. The latter feature may constitute a potentially robust signature of the existence of RNA crosstalk induced by endogenous competition for miRNAs in standard cellular conditions.

Background Distinct RNA species may compete for binding to microRNAs (miRNAs). This competition creates an indirect interaction between miRNA targets, which behave as miRNA sponges and eventually influence each other’s expression levels. Theoretical predictions suggest that not only the mean expression levels of targets but also the fluctuations around the means are coupled through miRNAs. This may result in striking effects on a broad range of cellular processes, such as cell differentiation and proliferation. Although several studies have reported the functional relevance of this mechanism of interaction, detailed experiments are lacking that study this phenomenon in controlled conditions by mimicking a physiological range. Results We used an experimental design based on two bidirectional plasmids and flow cytometry measurements of cotransfected mammalian cells. We validated a stochastic gene interaction model that describes how mRNAs can influence each other’s fluctuations in a miRNA-dependent manner in single cells. We show that miRNA–target correlations eventually lead to either bimodal cell population distributions with high and low target expression states, or correlated fluctuations across targets when the pool of unbound targets and miRNAs are in near-equimolar concentration. We found that there is an optimal range of conditions for the onset of cross-regulation, which is compatible with 10–1000 copies of targets per cell. Conclusions Our results are summarized in a phase diagram for miRNA-mediated cross-regulation that links experimentally measured quantities and effective model parameters. This phase diagram can be applied to in vivo studies of RNAs that are in competition for miRNA binding. Electronic supplementary material The online version of this article (doi:10.1186/s13059-017-1162-x) contains supplementary material, which is available to authorized users.

Understanding protein-protein interactions is central to our understanding of almost all complex biological processes. Computational tools exploiting rapidly growing genomic databases to characterize protein-protein interactions are urgently needed. Such methods should connect multiple scales from evolutionary conserved interactions between families of homologous proteins, over the identification of specifically interacting proteins in the case of multiple paralogs inside a species, down to the prediction of residues being in physical contact across interaction interfaces. Statistical inference methods detecting residue-residue coevolution have recently triggered considerable progress in using sequence data for quaternary protein structure prediction; they require, however, large joint alignments of homologous protein pairs known to interact. The generation of such alignments is a complex computational task on its own; application of coevolutionary modeling has in turn been restricted to proteins without paralogs, or to bacterial systems with the corresponding coding genes being co-localized in operons. Here we show that the Direct-Coupling Analysis of residue coevolution can be extended to connect the different scales, and simultaneously to match interacting paralogs, to identify inter-protein residue-residue contacts and to discriminate interacting from noninteracting families in a multiprotein system. Our results extend the potential applications of coevolutionary analysis far beyond cases treatable so far., Main Text 19 pages Supp. Inf. 16 pages

We implement a pseudolikelyhood approach with l2-regularization as well as the recently introduced pseudolikelihood with decimation procedure to the inverse problem in continuous spin models on arbitrary networks, with arbitrarily disordered couplings. Performances of the approaches are tested against data produced by Monte Carlo numerical simulations and compared also from previously studied fully-connected mean-field-based inference techniques. The results clearly show that the best network reconstruction is obtained through the decimation scheme, that also allows to dwell the inference down to lower temperature regimes. Possible applications to phasor models for light propagation in random media are proposed and discussed., 10 pages, 12 figures

International audience; Interaction between proteins is a fundamental mechanism that underlies virtually all biological processes. Many important interactions are conserved across a large variety of species. The need to maintain interaction leads to a high degree of co-evolution between residues in the interface between partner proteins. The inference of protein-protein interaction networks from the rapidly growing sequence databases is one of the most formidable tasks in systems biology today. We propose here a novel approach based on the Direct-Coupling Analysis of the co-evolution between inter-protein residue pairs. We use ribosomal and trp operon proteins as test cases: For the small resp. large ribosomal subunit our approach predicts protein interaction partners at a true-positive rate of 70% resp. 90% within the first 10 predictions, with areas of 0.69 resp. 0.81 under the ROC curves for all predictions. In the trp operon, it assigns the two largest interaction scores to the only two interactions experimentally known. On the level of residue interactions we show that for both the small and the large ribosomal subunit our approach predicts interacting residues in the system with a true positive rate of 60% and 85% in the first 20 predictions. We use artificial data to show that the performance of our approach depends crucially on the size of the joint multiple sequence alignments and analyze how many sequences would be necessary for a perfect prediction if the sequences were sampled from the same model that we use for prediction. Given the performance of our approach on the test data we speculate that it can be used to detect new interactions, especially in the light of the rapid growth of available sequence data.

Interaction between proteins is a fundamental mechanism that underlies virtually all biological processes. Many important interactions are conserved across a large variety of species. The need to maintain interaction leads to a high degree of co-evolution between residues in the interface between partner proteins. The inference of protein-protein interaction networks from the rapidly growing sequence databases is one of the most formidable tasks in systems biology today. We propose here a novel approach based on the Direct-Coupling Analysis of the co-evolution between inter-protein residue pairs. We use ribosomal and trp operon proteins as test cases: For the small resp. large ribosomal subunit our approach predicts protein-interaction partners at a true-positive rate of 70% resp. 90% within the first 10 predictions, with areas of 0.69 resp. 0.81 under the ROC curves for all predictions. In the trp operon, it assigns the two largest interaction scores to the only two interactions experimentally known. On the level of residue interactions we show that for both the small and the large ribosomal subunit our approach predicts interacting residues in the system with a true positive rate of 60% and 85% in the first 20 predictions. We use artificial data to show that the performance of our approach depends crucially on the size of the joint multiple sequence alignments and analyze how many sequences would be necessary for a perfect prediction if the sequences were sampled from the same model that we use for prediction. Given the performance of our approach on the test data we speculate that it can be used to detect new interactions, especially in the light of the rapid growth of available sequence data.

A statistical inference method is developed and tested for pairwise interacting systems whose degrees of freedom are continuous angular variables, such as planar spins in magnetic systems or wave phases in optics and acoustics. We investigate systems with both deterministic and quenched disordered couplings on two extreme topologies: complete and sparse graphs. To match further applications in optics also complex couplings and external fields are considered and general inference formulas are derived for real and imaginary parts of Hermitian coupling matrices from real and imaginary parts of complex correlation functions. The whole procedure is, eventually, tested on numerically generated correlation functions and local magnetizations by means of Monte Carlo simulations., Comment: 17 pages, 7 figures

Human SLAMF1 (signaling-lymphocytic-activation-molecule-family1, CD150) is a self-ligand adhesion/co-stimulatory molecule wich belongs to a family of 9 receptors. SLAMF1 is also a microbial sensor, as it regulates Gram- bacterial phagosome functions through an ubiquitous cellular autophagic machinery and serves as a receptor for Measles virus. In this work, we investigated expression and function of SLAMF1 in chronic lymphocytic leukemia (CLL) cells. Results indicate that expression of SLAMF1 is lost in a subset of patients with chronic lymphocytic leukemia characterized by an aggressive form of the disease, with shorter time to first treatment (median 2.2 years in SLAMF1- vs 7.6 in SLAMF1+ patients, P=.001) and overall survival (77.5% survival rate at 10 years in SLAMF1- vs 94.7% years in SLAMF1+ patients, P=.036). Consistently, SLAMF1low CLL patients are characterized by clinical or molecular markers of a more aggressive disease. Stable silencing of SLAMF1 in the CLL-like Mec-1 cell line (constitutively SLAMF1+) modulated pathways related to cell migration, cytoskeletal organization and intracellular vesicle formation/recirculation. Decreased expression of CXCR3 and an increased expression of CXCR4, CD38 and CD44 were maintained at the molecular level, likely explaining why SLAMF1- cells show enhanced chemotactic responses to CXCL12. This phenotype was confirmed in primary cells, by comparing a cohorts of SLAMF1high to one of SLAMF1low patients. Gene expression profiling also indicates profound modulation of pathways connected with vesicle formation and recirculation. Consistently, cross-linking of SLAMF1 with an agonisic mAb in primary cells and in the Mec-1 cell line enhanced the generation of autophagic vesicles and their fusion with the lysosomes. Ligation of SLAMF1 with this agonistic monoclonal antibody promoted the autophagic flux, by increasing accumulation of reactive oxygen species (ROS) and inducing phosphorylation of p38, JNK1/2 and bcl-2. The direct consequence was the formation of the autophagy macro-complex containing SLAMF1, the scaffold protein beclin1 and the enzyme Vps34. In agreement with the observation that many drugs used in CLL have autophagy-mediated effects, including fludarabine and the BH3 mimetic ABT-737, SLAMF1-silenced Mec-1 cells or SLAMF1low primary CLL cells were resistant to treatment with both agents. These results indicate that SLAMF1 plays as a critical role in CLL homeostasis. Loss of SLAMF1 expression modulates genetic pathways that regulate chemotaxis and autophagy and that potentially affect drug responses, thus providing a likely explanation for the unfavorable clinical outcome experienced by this patient subset. Restoring SLAMF1 expression in CLL cells would therefore be of therapeutic value for patients with aggressive CLL. Disclosures Gaidano: Morphosys, Roche, Novartis, GlaxoSmith Kline, Amgen, Janssen, Karyopharm: Honoraria, Other: Advisory boards; Celgene: Research Funding.

Correlation patterns in multiple sequence alignments of homologous proteins can be exploited to infer information on the three-dimensional structure of their members. The typical pipeline to address this task, which we in this paper refer to as the three dimensions of contact prediction, is to (i) filter and align the raw sequence data representing the evolutionarily related proteins; (ii) choose a predictive model to describe a sequence alignment; (iii) infer the model parameters and interpret them in terms of structural properties, such as an accurate contact map. We show here that all three dimensions are important for overall prediction success. In particular, we show that it is possible to improve significantly along the second dimension by going beyond the pair-wise Potts models from statistical physics, which have hitherto been the focus of the field. These (simple) extensions are motivated by multiple sequence alignments often containing long stretches of gaps which, as a data feature, would be rather untypical for independent samples drawn from a Potts model. Using a large test set of proteins we show that the combined improvements along the three dimensions are as large as any reported to date., Author Summary Proteins are large molecules that living cells make by stringing together building blocks called amino acids or peptides, following their blue-prints in the DNA. Freshly made proteins are typically long, structure-less chains of peptides, but shortly afterwards most of them fold into characteristic structures. Proteins execute many functions in the cell, for which they need to have the right structure, which is therefore very important in determining what the proteins can do. The structure of a protein can be determined by X-ray diffraction and other experimental approaches which are all, to this day, somewhat labor-intensive and difficult. On the other hand, the order of the peptides in a protein can be read off from the DNA blue-print, and such protein sequences are today routinely produced in large numbers. In this paper we show that many similar protein sequences can be used to find information about the structure. The basic approach is to construct a probabilistic model for sequence variability, and then to use the parameters of that model to predict structure in three-dimensional space. The main technical novelty compared to previous contributions in the same general direction is that we use models more directly matched to the data.

In the course of evolution, proteins show a remarkable conservation of their three-dimensional structure and their biological function, leading to strong evolutionary constraints on the sequence variability between homologous proteins. Our method aims at extracting such constraints from rapidly accumulating sequence data, and thereby at inferring protein structure and function from sequence information alone. Recently, global statistical inference methods (e.g. direct-coupling analysis, sparse inverse covariance estimation) have achieved a breakthrough towards this aim, and their predictions have been successfully implemented into tertiary and quaternary protein structure prediction methods. However, due to the discrete nature of the underlying variable (amino-acids), exact inference requires exponential time in the protein length, and efficient approximations are needed for practical applicability. Here we propose a very efficient multivariate Gaussian modeling approach as a variant of direct-coupling analysis: the discrete amino-acid variables are replaced by continuous Gaussian random variables. The resulting statistical inference problem is efficiently and exactly solvable. We show that the quality of inference is comparable or superior to the one achieved by mean-field approximations to inference with discrete variables, as done by direct-coupling analysis. This is true for (i) the prediction of residue-residue contacts in proteins, and (ii) the identification of protein-protein interaction partner in bacterial signal transduction. An implementation of our multivariate Gaussian approach is available at the website http://areeweb.polito.it/ricerca/cmp/code, Comment: 24 pages, 7 pdf figures, 2 tables, plus supporting informations. Published on PLOS ONE

International audience; Systems biology aims at creating mathematical models, i.e., computational reconstructions of biological systems and processes that will result in a new level of understanding-the elucidation of the basic and presumably conserved "design" and "engineering" principles of biomolecular systems. Thus, systems biology will move biology from a phenomenological to a predictive science. Mathematical modeling of biological networks and processes has already greatly improved our understanding of many cellular processes. However, given the massive amount of qualitative and quantitative data currently produced and number of burning questions in health care and biotechnology needed to be solved is still in its early phases. The field requires novel approaches for abstraction, for modeling bioprocesses that follow different biochemical and biophysical rules, and for combining different modules into larger models that still allow realistic simulation with the computational power available today. We have identified and discussed currently most prominent problems in systems biology: (1) how to bridge different scales of modeling abstraction, (2) how to bridge the gap between topological and mechanistic modeling, and (3) how to bridge the wet and dry laboratory gap. The future success of systems biology largely depends on bridging the recognized gaps.

We present a powerful experimental-computational technology for inferring network models that predict the response of cells to perturbations, and that may be useful in the design of combinatorial therapy against cancer. The experiments are systematic series of perturbations of cancer cell lines by targeted drugs, singly or in combination. The response to perturbation is quantified in terms of relative changes in the measured levels of proteins, phospho-proteins and cellular phenotypes such as viability. Computational network models are derived de novo, i.e., without prior knowledge of signaling pathways, and are based on simple non-linear differential equations. The prohibitively large solution space of all possible network models is explored efficiently using a probabilistic algorithm, Belief Propagation (BP), which is three orders of magnitude faster than standard Monte Carlo methods. Explicit executable models are derived for a set of perturbation experiments in SKMEL-133 melanoma cell lines, which are resistant to the therapeutically important inhibitor of RAF kinase. The resulting network models reproduce and extend known pathway biology. They empower potential discoveries of new molecular interactions and predict efficacious novel drug perturbations, such as the inhibition of PLK1, which is verified experimentally. This technology is suitable for application to larger systems in diverse areas of molecular biology., Author Summary Drugs that target specific effects of signaling proteins are promising agents for treating cancer. One of the many obstacles facing optimal drug design is inadequate quantitative understanding of the coordinated interactions between signaling proteins. De novo model inference of network or pathway models refers to the algorithmic construction of mathematical predictive models from experimental data without dependence on prior knowledge. De novo inference is difficult because of the prohibitively large number of possible sets of interactions that may or may not be consistent with observations. Our new method overcomes this difficulty by adapting a method from statistical physics, called Belief Propagation, which first calculates probabilistically the most likely interactions in the vast space of all possible solutions, then derives a set of individual, highly probable solutions in the form of executable models. In this paper, we test this method on artificial data and then apply it to model signaling pathways in a BRAF-mutant melanoma cancer cell line based on a large set of rich output measurements from a systematic set of perturbation experiments using drug combinations. Our results are in agreement with established biological knowledge, predict novel interactions, and predict efficacious drug targets that are specific to the experimental cell line and potentially to related tumors. The method has the potential, with sufficient systematic perturbation data, to model, de novo and quantitatively, the effects of hundreds of proteins on cellular responses, on a scale that is currently unreachable in diverse areas of cell biology. In a disease context, the method is applicable to the computational design of novel combination drug treatments.

Competitive endogenous (ce)RNAs cross-regulate each other through sequestration of shared microRNAs and form complex regulatory networks based on their microRNA signature. However, the molecular requirements for ceRNA cross-regulation and the extent of ceRNA networks remain unknown. Here, we present a mathematical mass-action model to determine the optimal conditions for ceRNA activity in silico . This model was validated using phosphatase and tensin homolog (PTEN) and its ceRNA VAMP (vesicle-associated membrane protein)-associated protein A (VAPA) as paradigmatic examples. A computational assessment of the complexity of ceRNA networks revealed that transcription factor and ceRNA networks are intimately intertwined. Notably, we found that ceRNA networks are responsive to transcription factor up-regulation or their aberrant expression in cancer. Thus, given optimal molecular conditions, alterations of one ceRNA can have striking effects on integrated ceRNA and transcriptional networks.

Signaling and regulatory networks are essential for cells to control processes such as growth, differentiation, and response to stimuli. Although many “omic” data sources are available to probe signaling pathways, these data are typically sparse and noisy. Thus, it has been difficult to use these data to discover the cause of the diseases and to propose new therapeutic strategies. We overcome these problems and use “omic” data to reconstruct simultaneously multiple pathways that are altered in a particular condition by solving the prize-collecting Steiner forest problem. To evaluate this approach, we use the well-characterized yeast pheromone response. We then apply the method to human glioblastoma data, searching for a forest of trees, each of which is rooted in a different cell-surface receptor. This approach discovers both overlapping and independent signaling pathways that are enriched in functionally and clinically relevant proteins, which could provide the basis for new therapeutic strategies. Although the algorithm was not provided with any information about the phosphorylation status of receptors, it identifies a small set of clinically relevant receptors among hundreds present in the interactome.

The evolutionary trajectory of a protein through sequence space is constrained by its function. Collections of sequence homologs record the outcomes of millions of evolutionary experiments in which the protein evolves according to these constraints. Deciphering the evolutionary record held in these sequences and exploiting it for predictive and engineering purposes presents a formidable challenge. The potential benefit of solving this challenge is amplified by the advent of inexpensive high-throughput genomic sequencing. In this paper we ask whether we can infer evolutionary constraints from a set of sequence homologs of a protein. The challenge is to distinguish true co-evolution couplings from the noisy set of observed correlations. We address this challenge using a maximum entropy model of the protein sequence, constrained by the statistics of the multiple sequence alignment, to infer residue pair couplings. Surprisingly, we find that the strength of these inferred couplings is an excellent predictor of residue-residue proximity in folded structures. Indeed, the top-scoring residue couplings are sufficiently accurate and well-distributed to define the 3D protein fold with remarkable accuracy. We quantify this observation by computing, from sequence alone, all-atom 3D structures of fifteen test proteins from different fold classes, ranging in size from 50 to 260 residues., including a G-protein coupled receptor. These blinded inferences are de novo, i.e., they do not use homology modeling or sequence-similar fragments from known structures. The co-evolution signals provide sufficient information to determine accurate 3D protein structure to 2.7–4.8 A Cα-RMSD error relative to the observed structure, over at least two-thirds of the protein (method called EVfold, details at http://EVfold.org). This discovery provides insight into essential interactions constraining protein evolution and will facilitate a comprehensive survey of the universe of protein structures, new strategies in protein and drug design, and the identification of functional genetic variants in normal and disease genomes.

The similarity in the three-dimensional structures of homologous proteins imposes strong constraints on their sequence variability. It has long been suggested that the resulting correlations among amino acid compositions at different sequence positions can be exploited to infer spatial contacts within the tertiary protein structure. Crucial to this inference is the ability to disentangle direct and indirect correlations, as accomplished by the recently introduced Direct Coupling Analysis (DCA) (Weigt et al. (2009) Proc Natl Acad Sci 106:67). Here we develop a computationally efficient implementation of DCA, which allows us to evaluate the accuracy of contact prediction by DCA for a large number of protein domains, based purely on sequence information. DCA is shown to yield a large number of correctly predicted contacts, recapitulating the global structure of the contact map for the majority of the protein domains examined. Furthermore, our analysis captures clear signals beyond intra- domain residue contacts, arising, e.g., from alternative protein conformations, ligand- mediated residue couplings, and inter-domain interactions in protein oligomers. Our findings suggest that contacts predicted by DCA can be used as a reliable guide to facilitate computational predictions of alternative protein conformations, protein complex formation, and even the de novo prediction of protein domain structures, provided the existence of a large number of homologous sequences which are being rapidly made available due to advances in genome sequencing., 28 pages, 7 figures, to appear in PNAS

We investigate a minimal model for non-crystalline water, defined on a Husimi lattice. The peculiar random-regular nature of the lattice is meant to account for the formation of a random 4-coordinated hydrogen-bond network. The model turns out to be consistent with most thermodynamic anomalies observed in liquid and supercooled-liquid water. Furthermore, the model exhibits two glassy phases with different densities, which can coexist at a first-order transition. The onset of a complex free-energy landscape, characterized by an exponentially large number of metastable minima, is pointed out by the cavity method, at the level of 1-step replica symmetry breaking., Comment: expanded version: 6 pages, 7 figures

Background Transcriptional gene regulation is one of the most important mechanisms in controlling many essential cellular processes, including cell development, cell-cycle control, and the cellular response to variations in environmental conditions. Genes are regulated by transcription factors and other genes/proteins via a complex interconnection network. Such regulatory links may be predicted using microarray expression data, but most regulation models suppose transcription factor independence, which leads to spurious links when many genes have highly correlated expression levels. Results We propose a new algorithm to infer combinatorial control networks from gene-expression data. Based on a simple model of combinatorial gene regulation, it includes a message-passing approach which avoids explicit sampling over putative gene-regulatory networks. This algorithm is shown to recover the structure of a simple artificial cell-cycle network model for baker's yeast. It is then applied to a large-scale yeast gene expression dataset in order to identify combinatorial regulations, and to a data set of direct medical interest, namely the Pleiotropic Drug Resistance (PDR) network. Conclusions The algorithm we designed is able to recover biologically meaningful interactions, as shown by recent experimental results [1]. Moreover, new cases of combinatorial control are predicted, showing how simple models taking this phenomenon into account can lead to informative predictions and allow to extract more putative regulatory interactions from microarray databases.

In this work we suggest a statistical mechanics approach to the classification of high-dimensional data according to a binary label. We propose an algorithm whose aim is twofold: First it learns a classifier from a relatively small number of data, second it extracts a sparse signature, {\it i.e.} a lower-dimensional subspace carrying the information needed for the classification. In particular the second part of the task is NP-hard, therefore we propose a statistical-mechanics based message-passing approach. The resulting algorithm is firstly tested on artificial data to prove its validity, but also to elucidate possible limitations. As an important application, we consider the classification of gene-expression data measured in various types of cancer tissues. We find that, despite the currently low quantity and quality of available data (the number of available samples is much smaller than the number of measured genes, limiting thus strongly the predictive capacities), the algorithm performs slightly better than many state-of-the-art approaches in bioinformatics., 15 pages, 13 eps figures

One of the crucial tasks in many inference problems is the extraction of an underlying sparse graphical model from a given number of high-dimensional measurements. In machine learning, this is frequently achieved using, as a penalty term, the L p norm of the model parameters, with p ≤ 1 for efficient dilution. Here we propose a statistical-mechanics analysis of the problem in the setting of perceptron memorization and generalization. Using a replica approach, we are able to evaluate the relative performance of naive dilution (obtained by learning without dilution, following by applying a threshold to the model parameters), L 1 dilution (which is frequently used in convex optimization) and L 0 dilution (which is optimal but computationally hard to implement). Whereas both L p diluted approaches clearly outperform the naive approach, we find a small region where L 0 works almost perfectly and strongly outperforms the simpler to implement L 1 dilution. In the second part we propose an efficient message-passing strategy in the simpler case of discrete classification vectors, where the norm L 0 norm coincides with the L 1 . Some examples are discussed.

In this work we propose a novel algorithmic strategy that allows for an efficient characterization of the whole set of stable fluxes compatible with the metabolic constraints. The algorithm, based on the well-known Bethe approximation, allows the computation in polynomial time of the volume of a non full-dimensional convex polytope in high dimensions. The result of our algorithm match closely the prediction of Monte Carlo based estimations of the flux distributions of the Red Blood Cell metabolic network but in incomparably shorter time. We also analyze the statistical properties of the average fluxes of the reactions in the E-Coli metabolic network and finally to test the effect of flux knock-outs on the size of the solution space of the E-Coli central metabolism.

Since their introduction, Boolean networks have been traditionally studied in view of their rich dynamical behavior under different update protocols and for their qualitative analogy with cell regulatory networks. More recently, tools borrowed from statistical physics of disordered systems and from computer science have provided a more complete characterization of their equilibrium behavior. However, the largest part of the results have been obtained in the thermodynamic limit, which is often far from being reached when dealing with realistic instances of the problem. The numerical analysis presented here aims at comparing - for a specific family of models - the outcomes given by the heuristic belief propagation algorithm with those given by exhaustive enumeration. In the second part of the paper some analytical considerations on the validity of the annealed approximation are discussed., Minor corrections