Search

Due to highly personalized biological and lifestyle characteristics, different individuals may have different metabolite responses to specific foods and nutrients. In particular, the gut microbiota, a collection of trillions of microorganisms living in the gastrointestinal tract, is highly personalized and plays a key role in the metabolite responses to foods and nutrients. Accurately predicting metabolite responses to dietary interventions based on individuals' gut microbial compositions holds great promise for precision nutrition. Existing prediction methods are typically limited to traditional machine learning models. Deep learning methods dedicated to such tasks are still lacking. Here we develop a method McMLP ( M etabolite response predictor using c oupled M ulti l ayer P erceptrons) to fill in this gap. We provide clear evidence that McMLP outperforms existing methods on both synthetic data generated by the microbial consumer-resource model and real data obtained from six dietary intervention studies. Furthermore, we perform sensitivity analysis of McMLP to infer the tripartite food-microbe-metabolite interactions, which are then validated using the ground-truth (or literature evidence) for synthetic (or real) data, respectively. The presented tool has the potential to inform the design of microbiota-based personalized dietary strategies to achieve precision nutrition., Competing Interests: Competing Interests. The authors declare no competing interests.

Background: Pathogenic infections pose a significant threat to global health, affecting millions of people every year and presenting substantial challenges to healthcare systems worldwide. Efficient and timely testing plays a critical role in disease control and transmission prevention. Group testing is a well-established method for reducing the number of tests needed to screen large populations when the disease prevalence is low. However, it does not fully utilize the quantitative information provided by qPCR methods, nor is it able to accommodate a wide range of pathogen loads., Results: To address these issues, we introduce a novel adaptive semi-quantitative group testing (SQGT) scheme to efficiently screen populations via two-stage qPCR testing. The SQGT method quantizes cycle threshold (Ct) values into multiple bins, leveraging the information from the first stage of screening to improve the detection sensitivity. Dynamic Ct threshold adjustments mitigate dilution effects and enhance test accuracy. Comparisons with traditional binary outcome GT methods show that SQGT reduces the number of tests by 24% on the only complete real-world qPCR group testing dataset from Israel, while maintaining a negligible false negative rate., Conclusion: In conclusion, our adaptive SQGT approach, utilizing qPCR data and dynamic threshold adjustments, offers a promising solution for efficient population screening. With a reduction in the number of tests and minimal false negatives, SQGT holds potential to enhance disease control and testing strategies on a global scale., (© 2024. The Author(s).)

Exon skipping technologies enable exclusion of targeted exons from mature mRNA transcripts, which has broad applications in molecular biology, medicine, and biotechnology. Existing exon skipping techniques include antisense oligonucleotides, targetable nucleases, and base editors, which, while effective for specific applications at some target exons, remain hindered by shortcomings, including transient effects for oligonucleotides, genotoxicity for nucleases and inconsistent exon skipping for base editors. To overcome these limitations, we created SPLICER, a toolbox of next-generation base editors consisting of near-PAMless Cas9 nickase variants fused to adenosine or cytosine deaminases for the simultaneous editing of splice acceptor (SA) and splice donor (SD) sequences. Synchronized SA and SD editing with SPLICER improves exon skipping, reduces aberrant outcomes, including cryptic splicing and intron retention, and enables skipping of exons refractory to single splice-site editing. To demonstrate the therapeutic potential of SPLICER, we targeted APP exon 17, which encodes the amino acid residues that are cleaved to form the Aβ plaques in Alzheimer's disease. SPLICER reduced the formation of Aβ42 peptides in vitro and enabled efficient exon skipping in a mouse model of Alzheimer's disease. Overall, SPLICER is a widely applicable and efficient toolbox for exon skipping with broad therapeutic applications.

Life as we know it relies on the interplay between catalytic activity and information processing carried out by biological polymers. Here we present a plausible pathway by which a pool of prebiotic information-coding oligomers could acquire an early catalytic function, namely sequence-specific cleavage activity. Starting with a system capable of non-enzymatic templated replication, we demonstrate that even non-catalyzed spontaneous cleavage would promote proliferation by generating short fragments that act as primers. Furthermore, we show that catalytic cleavage function can naturally emerge and proliferate in this system. Specifically, a cooperative catalytic network with four subpopulations of oligomers is selected by the evolution in competition with chains lacking catalytic activity. The cooperative system emerges through the functional differentiation of oligomers into catalysts and their substrates. The model is inspired by the structure of the hammerhead RNA enzyme as well as other DNA- and RNA-based enzymes with cleavage activity that readily emerge through natural or artificial selection. We identify the conditions necessary for the emergence of the cooperative catalytic network. In particular, we show that it requires the catalytic rate enhancement over the spontaneous cleavage rate to be at least 10 2 -10 3 , a factor consistent with the existing experiments. The evolutionary pressure leads to a further increase in catalytic efficiency. The presented mechanism provides an escape route from a relatively simple pairwise replication of oligomers toward a more complex behavior involving catalytic function. This provides a bridge between the information-first origin of life scenarios and the paradigm of autocatalytic sets and hypercycles, albeit based on cleavage rather than synthesis of reactants., Competing Interests: AT, SM No competing interests declared

Importance: Issatchenkia orientalis is a promising industrial chassis to produce biofuels and bioproducts due to its high tolerance to multiple environmental stresses such as low pH, heat, and other chemicals otherwise toxic for the most widely used microbes. Yet, little is known about specific mechanisms of such tolerance in this organism, hindering our ability to engineer this species to produce valuable biochemicals. Here, we report a comprehensive study of the mechanisms of acidic tolerance in this species via transcriptome profiling across variable pH for 12 different strains with different phenotypes. We found multiple regulatory mechanisms involved in tolerance to low pH in different strains of I. orientalis , marking potential targets for future gene editing and perturbation experiments., Competing Interests: The authors declare no conflict of interest.

The dynamics of microbial communities is complex, determined by competition for metabolic substrates and cross-feeding of byproducts. Species in the community grow by harvesting energy from chemical reactions that transform substrates to products. In many anoxic environments, these reactions are close to thermodynamic equilibrium and growth is slow. To understand the community structure in these energy-limited environments, we developed a microbial community consumer-resource model incorporating energetic and thermodynamic constraints on an interconnected metabolic network. The central element of the model is product inhibition, meaning that microbial growth may be limited not only by depletion of metabolic substrates but also by accumulation of products. We demonstrate that these additional constraints on microbial growth cause a convergence in the structure and function of the community metabolic network-independent of species composition and biochemical details-providing a possible explanation for convergence of community function despite taxonomic variation observed in many natural and industrial environments. Furthermore, we discovered that the structure of community metabolic network is governed by the thermodynamic principle of maximum free energy dissipation. Our results predict the decrease of functional convergence in faster growing communities, which we validate by analyzing experimental data from anaerobic digesters. Overall, the work demonstrates how universal thermodynamic principles may constrain community metabolism and explain observed functional convergence in microbial communities., (© 2023. The Author(s), under exclusive licence to International Society for Microbial Ecology.)

Alterations of the normal gut microbiota can cause various human health concerns. Environmental chemicals are one of the drivers of such disturbances. The aim of our study was to examine the effects of exposure to perfluoroalkyl and polyfluoroalkyl substances (PFAS)-specifically, perfluorooctane sulfonate (PFOS) and 2,3,3,3-tetrafluoro-2-(heptafluoropropoxy) propanoic acid (GenX)-on the microbiome of the small intestine and colon, as well as on liver metabolism. Male CD-1 mice were exposed to PFOS and GenX in different concentrations and compared to controls. GenX and PFOS were found to have different effects on the bacterial community in both the small intestine and colon based on 16S rRNA profiles. High GenX doses predominantly led to increases in the abundance of Clostridium sensu stricto , Alistipes , and Ruminococcus , while PFOS generally altered Lactobacillus , Limosilactobacillus , Parabacteroides , Staphylococcus , and Ligilactobacillus . These treatments were associated with alterations in several important microbial metabolic pathways in both the small intestine and colon. Untargeted LC-MS/MS metabolomic analysis of the liver, small intestine, and colon yielded a set of compounds significantly altered by PFOS and GenX. In the liver, these metabolites were associated with the important host metabolic pathways implicated in the synthesis of lipids, steroidogenesis, and in the metabolism of amino acids, nitrogen, and bile acids. Collectively, our results suggest that PFOS and GenX exposure can cause major perturbations in the gastrointestinal tract, aggravating microbiome toxicity, hepatotoxicity, and metabolic disorders.

Characterizing the metabolic profile of a microbial community is crucial for understanding its biological function and its impact on the host or environment. Metabolomics experiments directly measuring these profiles are difficult and expensive, while sequencing methods quantifying the species composition of microbial communities are well-developed and relatively cost-effective. Computational methods that are capable of predicting metabolomic profiles from microbial compositions can save considerable efforts needed for metabolomic profiling experimentally. Yet, despite existing efforts, we still lack a computational method with high prediction power, general applicability, and great interpretability. Here we develop a method - mNODE (Metabolomic profile predictor using Neural Ordinary Differential Equations), based on a state-of-the-art family of deep neural network models. We show compelling evidence that mNODE outperforms existing methods in predicting the metabolomic profiles of human microbiomes and several environmental microbiomes. Moreover, in the case of human gut microbiomes, mNODE can naturally incorporate dietary information to further enhance the prediction of metabolomic profiles. Besides, susceptibility analysis of mNODE enables us to reveal microbe-metabolite interactions, which can be validated using both synthetic and real data. The presented results demonstrate that mNODE is a powerful tool to investigate the microbiome-diet-metabolome relationship, facilitating future research on precision nutrition., Competing Interests: Competing Interests. The authors declare no competing interests.

Recent observations have revealed that closely related strains of the same microbial species can stably coexist in natural and laboratory settings subject to boom and bust dynamics and serial dilutions, respectively. However, the possible mechanisms enabling the coexistence of only a handful of strains, but not more, have thus far remained unknown. Here, using a consumer-resource model of microbial ecosystems, we propose that by differentiating along Monod parameters characterizing microbial growth rates in high and low nutrient conditions, strains can coexist in patterns similar to those observed. In our model, boom and bust environments create satellite niches due to resource concentrations varying in time. These satellite niches can be occupied by closely related strains, thereby enabling their coexistence. We demonstrate that this result is valid even in complex environments consisting of multiple resources and species. In these complex communities, each species partitions resources differently and creates separate sets of satellite niches for their own strains. While there is no theoretical limit to the number of coexisting strains, in our simulations, we always find between 1 and 3 strains coexisting, consistent with known experiments and observations., Competing Interests: The authors have declared that no competing interests exist., (Copyright: © 2022 Fridman et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.)

In Fall 2020, universities saw extensive transmission of SARS-CoV-2 among their populations, threatening health of the university and surrounding communities, and viability of in-person instruction. Here we report a case study at the University of Illinois at Urbana-Champaign, where a multimodal "SHIELD: Target, Test, and Tell" program, with other non-pharmaceutical interventions, was employed to keep classrooms and laboratories open. The program included epidemiological modeling and surveillance, fast/frequent testing using a novel low-cost and scalable saliva-based RT-qPCR assay for SARS-CoV-2 that bypasses RNA extraction, called covidSHIELD, and digital tools for communication and compliance. In Fall 2020, we performed >1,000,000 covidSHIELD tests, positivity rates remained low, we had zero COVID-19-related hospitalizations or deaths amongst our university community, and mortality in the surrounding Champaign County was reduced more than 4-fold relative to expected. This case study shows that fast/frequent testing and other interventions mitigated transmission of SARS-CoV-2 at a large public university., (© 2022. The Author(s).)

To enable personalized cancer treatment, machine learning models have been developed to predict drug response as a function of tumor and drug features. However, most algorithm development efforts have relied on cross-validation within a single study to assess model accuracy. While an essential first step, cross-validation within a biological data set typically provides an overly optimistic estimate of the prediction performance on independent test sets. To provide a more rigorous assessment of model generalizability between different studies, we use machine learning to analyze five publicly available cell line-based data sets: National Cancer Institute 60, ancer Therapeutics Response Portal (CTRP), Genomics of Drug Sensitivity in Cancer, Cancer Cell Line Encyclopedia and Genentech Cell Line Screening Initiative (gCSI). Based on observed experimental variability across studies, we explore estimates of prediction upper bounds. We report performance results of a variety of machine learning models, with a multitasking deep neural network achieving the best cross-study generalizability. By multiple measures, models trained on CTRP yield the most accurate predictions on the remaining testing data, and gCSI is the most predictable among the cell line data sets included in this study. With these experiments and further simulations on partial data, two lessons emerge: (1) differences in viability assays can limit model generalizability across studies and (2) drug diversity, more than tumor diversity, is crucial for raising model generalizability in preclinical screening., (© The Author(s) 2021. Published by Oxford University Press.)

Many microbes grow diauxically, utilizing the available resources one at a time rather than simultaneously. The properties of communities of microbes growing diauxically remain poorly understood, largely due to a lack of theory and models of such communities. Here, we develop and study a minimal model of diauxic microbial communities assembling in a serially diluted culture. We find that unlike co-utilizing communities, diauxic community assembly repeatably and spontaneously leads to communities with complementary resource preferences, namely communities where species prefer different resources as their top choice. Simulations and theory explain that the emergence of complementarity is driven by the disproportionate contribution of the top choice resource to the growth of a diauxic species. Additionally, we develop a geometric approach for analyzing serially diluted communities, with or without diauxie, which intuitively explains several additional emergent community properties, such as the apparent lack of species which grow fastest on a resource other than their most preferred resource. Overall, our work provides testable predictions for the assembly of natural as well as synthetic communities of diauxically shifting microbes., (© 2021. The Author(s).)

It is well recognized that population heterogeneity plays an important role in the spread of epidemics. While individual variations in social activity are often assumed to be persistent, that is, constant in time, here we discuss the consequences of dynamic heterogeneity. By integrating the stochastic dynamics of social activity into traditional epidemiological models, we demonstrate the emergence of a new long timescale governing the epidemic, in broad agreement with empirical data. Our stochastic social activity model captures multiple features of real-life epidemics such as COVID-19, including prolonged plateaus and multiple waves, which are transiently suppressed due to the dynamic nature of social activity. The existence of a long timescale due to the interplay between epidemic and social dynamics provides a unifying picture of how a fast-paced epidemic typically will transition to an endemic state., Competing Interests: AT, SM, TW, AE, GW, NG No competing interests declared

Epidemics generally spread through a succession of waves that reflect factors on multiple timescales. On short timescales, superspreading events lead to burstiness and overdispersion, whereas long-term persistent heterogeneity in susceptibility is expected to lead to a reduction in both the infection peak and the herd immunity threshold (HIT). Here, we develop a general approach to encompass both timescales, including time variations in individual social activity, and demonstrate how to incorporate them phenomenologically into a wide class of epidemiological models through reparameterization. We derive a nonlinear dependence of the effective reproduction number [Formula: see text] on the susceptible population fraction S. We show that a state of transient collective immunity (TCI) emerges well below the HIT during early, high-paced stages of the epidemic. However, this is a fragile state that wanes over time due to changing levels of social activity, and so the infection peak is not an indication of long-lasting herd immunity: Subsequent waves may emerge due to behavioral changes in the population, driven by, for example, seasonal factors. Transient and long-term levels of heterogeneity are estimated using empirical data from the COVID-19 epidemic and from real-life face-to-face contact networks. These results suggest that the hardest hit areas, such as New York City, have achieved TCI following the first wave of the epidemic, but likely remain below the long-term HIT. Thus, in contrast to some previous claims, these regions can still experience subsequent waves., Competing Interests: The authors declare no competing interest., (Copyright © 2021 the Author(s). Published by PNAS.)

Understanding a complex microbial ecosystem such as the human gut microbiome requires information about both microbial species and the metabolites they produce and secrete. These metabolites are exchanged via a large network of cross-feeding interactions, and are crucial for predicting the functional state of the microbiome. However, till date, we only have information for a part of this network, limited by experimental throughput. Here, we propose an ecology-based computational method, GutCP, using which we predict hundreds of new experimentally untested cross-feeding interactions in the human gut microbiome. GutCP utilizes a mechanistic model of the gut microbiome with the explicit exchange of metabolites and their effects on the growth of microbial species. To build GutCP, we combine metagenomic and metabolomic measurements from the gut microbiome with optimization techniques from machine learning. Close to 65% of the cross-feeding interactions predicted by GutCP are supported by evidence from genome annotations, which we provide for experimental testing. Our method has the potential to greatly improve existing models of the human gut microbiome, as well as our ability to predict the metabolic profile of the gut.

The COVID-19 pandemic disrupted the world in 2020 by spreading at unprecedented rates and causing tens of thousands of fatalities within a few months. The number of deaths dramatically increased in regions where the number of patients in need of hospital care exceeded the availability of care. Many COVID-19 patients experience Acute Respiratory Distress Syndrome (ARDS), a condition that can be treated with mechanical ventilation. In response to the need for mechanical ventilators, designed and tested an emergency ventilator (EV) that can control a patient's peak inspiratory pressure (PIP) and breathing rate, while keeping a positive end expiratory pressure (PEEP). This article describes the rapid design, prototyping, and testing of the EV. The development process was enabled by rapid design iterations using additive manufacturing (AM). In the initial design phase, iterations between design, AM, and testing enabled a working prototype within one week. The designs of the 16 different components of the ventilator were locked by additively manufacturing and testing a total of 283 parts having parametrically varied dimensions. In the second stage, AM was used to produce 75 functional prototypes to support engineering evaluation and animal testing. The devices were tested over more than two million cycles. We also developed an electronic monitoring system and with automatic alarm to provide for safe operation, along with training materials and user guides. The final designs are available online under a free license. The designs have been transferred to more than 70 organizations in 15 countries. This project demonstrates the potential for ultra-fast product design, engineering, and testing of medical devices needed for COVID-19 emergency response., Competing Interests: The study was funded by University of Illinois Urbana-Champaign and by Carle Foundation Hospital. GD is principal at Tekmill Inc., which worked on the project at the direction of and under contract to the University of Illinois Urbana-Champaign. SE, AM, and BR are employees of Creative Thermal Solutions Inc., which worked on the project at the direction of and under contract to the University of Illinois Urbana-Champaign. DB, MN, JO, SR, and CW are employees at Fast Radius Inc., which worked on the project at the direction of and under contract to the University of Illinois Urbana-Champaign. WPK is Professor at University of Illinois Urbana-Champaign and Chief Scientist at Fast Radius Inc., which manufactured prototypes used in this study. WPK performed the work in as an employee at the University of Illinois Urbana-Champaign and received no compensation from Fast Radius. This project was conducted in accordance with conflict of management policies at both organizations. This does not alter our adherence to PLOS ONE policies on sharing data and materials. There are no other patents, products in development or marketed products associated with this research to declare.

As a heritable sequence-specific adaptive immune system, CRISPR-Cas is a powerful force shaping strain diversity in host-virus systems. While the diversity of CRISPR alleles has been explored, the associated structure and dynamics of host-virus interactions have not. We explore the role of CRISPR in mediating the interplay between host-virus interaction structure and eco-evolutionary dynamics in a computational model and compare the results with three empirical datasets from natural systems. We show that the structure of the networks describing who infects whom and the degree to which strains are immune, are respectively modular (containing groups of hosts and viruses that interact strongly) and weighted-nested (specialist hosts are more susceptible to subsets of viruses that in turn also infect the more generalist hosts with many spacers matching many viruses). The dynamic interplay between these networks influences transitions between dynamical regimes of virus diversification and host control. The three empirical systems exhibit weighted-nested immunity networks, a pattern our theory shows is indicative of hosts able to suppress virus diversification. Previously missing from studies of microbial host-pathogen systems, the immunity network plays a key role in the coevolutionary dynamics.

Social interaction between microbes can be described at many levels of details: from the biochemistry of cell-cell interactions to the ecological dynamics of populations. Choosing an appropriate level to model microbial communities without losing generality remains a challenge. Here we show that modeling cross-feeding interactions at an intermediate level between genome-scale metabolic models of individual species and consumer-resource models of ecosystems is suitable to experimental data. We applied our modeling framework to three published examples of multi-strain Escherichia coli communities with increasing complexity: uni-, bi-, and multi-directional cross-feeding of either substitutable metabolic byproducts or essential nutrients. The intermediate-scale model accurately fit empirical data and quantified metabolic exchange rates that are hard to measure experimentally, even for a complex community of 14 amino acid auxotrophies. By studying the conditions of species coexistence, the ecological outcomes of cross-feeding interactions, and each community's robustness to perturbations, we extracted new quantitative insights from these three published experimental datasets. Our analysis provides a foundation to quantify cross-feeding interactions from experimental data, and highlights the importance of metabolic exchanges in the dynamics and stability of microbial communities., Competing Interests: The authors have declared that no competing interests exist.

Natural bacterial populations are subjected to constant predation pressure by bacteriophages. Bacteria use a variety of molecular mechanisms to defend themselves from phage predation. However, since phages are nonmotile, perhaps the simplest defense against phage is for bacteria to move faster than phages. In particular, chemotaxis, the active migration of bacteria up attractant gradients, may help the bacteria escape slowly diffusing phages. Here we study phage infection dynamics in migrating bacterial populations driven by chemotaxis through low viscosity agar plates. We find that expanding phage-bacteria populations supports two moving fronts, an outermost bacterial front driven by nutrient uptake and chemotaxis and an inner phage front at which the bacterial population collapses due to phage predation. We show that with increasing adsorption rate and initial phage population, the speed of the moving phage front increases, eventually overtaking the bacterial front and driving the system across a transition from a regime where bacterial front speed exceeds that of the phage front to one where bacteria must evolve phage resistance to survive. Our data support the claim that this process requires phage to hitchhike with moving bacteria. A deterministic model recapitulates the transition under the assumption that phage virulence declines with host growth rate which we confirm experimentally. Finally, near the transition between regimes we observe macroscopic fluctuations in bacterial densities at the phage front. Our work opens a new, spatio-temporal, line of investigation into the eco-evolutionary struggle between bacteria and phage.

The competition between bacteria often involves both nutrients and phage predators and may give rise to abrupt regime shifts between the alternative stable states characterized by different species compositions. While such transitions have been previously studied in the context of competition for nutrients, the case of phage-induced bistability between competing bacterial species has not been considered yet. Here we demonstrate a possibility of regime shifts in well-mixed phage-bacterium ecosystems. In one of the bistable states, the fast-growing bacteria competitively exclude the slow-growing ones by depleting their common nutrient. Conversely, in the second state, the slow-growing bacteria with a large burst size generate such a large phage population that the other species cannot survive. This type of bistability can be realized as the competition between a strain of bacteria protected from phage by abortive infection and another strain with partial resistance to phage. It is often desirable to reliably control the state of microbial ecosystems, yet bistability significantly complicates this task. We discuss successes and limitations of one control strategy in which one adds short pulses to populations of individual species. Our study proposes a new type of phage therapy, where introduction of the phage is supplemented by the addition of a partially resistant host bacteria. IMPORTANCE Phage-microbe communities play an important role in human health as well as natural and industrial environments. Here we show that these communities can assume several alternative species compositions separated by abrupt regime shifts. Our model predicts these regime shifts in the competition between bacterial strains protected by two different phage defense mechanisms: abortive infection/CRISPR and partial resistance. The history dependence caused by regime shifts greatly complicates the task of manipulation and control of a community. We propose and study a successful control strategy via short population pulses aimed at inducing the desired regime shifts. In particular, we predict that a fast-growing pathogen could be eliminated by a combination of its phage and a slower-growing susceptible host., (Copyright © 2019 Maslov and Sneppen.)

Experimental studies of microbial communities routinely reveal that they have multiple stable states. While each of these states is generally resilient, certain perturbations such as antibiotics, probiotics, and diet shifts, result in transitions to other states. Can we reliably both predict such stable states as well as direct and control transitions between them? Here we present a new conceptual model-inspired by the stable marriage problem in game theory and economics-in which microbial communities naturally exhibit multiple stable states, each state with a different species' abundance profile. Our model's core ingredient is that microbes utilize nutrients one at a time while competing with each other. Using only two ranked tables, one with microbes' nutrient preferences and one with their competitive abilities, we can determine all possible stable states as well as predict inter-state transitions, triggered by the removal or addition of a specific nutrient or microbe. Further, using an example of seven Bacteroides species common to the human gut utilizing nine polysaccharides, we predict that mutual complementarity in nutrient preferences enables these species to coexist at high abundances.

Reduction of information entropy along with ever-increasing complexity is among the key signatures of life. Understanding the onset of such behavior in the early prebiotic world is essential for solving the problem of the origin of life. Here we study a general problem of heteropolymers capable of template-assisted ligation based on Watson-Crick-like hybridization. The system is driven off-equilibrium by cyclic changes in the environment. We model the dynamics of 2-mers, i.e., sequential pairs of specific monomers within the heteropolymer population. While the possible number of them is Z 2 (where Z is the number of monomer types), we observe that most of the 2-mers get extinct, leaving no more than 2 Z survivors. This leads to a dramatic reduction of the information entropy in the sequence space. Our numerical results are supported by a general mathematical analysis of the competition of growing polymers for constituent monomers. This natural-selection-like process ultimately results in a limited subset of polymer sequences. Importantly, the set of surviving sequences depends on initial concentrations of monomers and remains exponentially large (2 L down from Z L for length L ) in each of realizations. Thus, an inhomogeneity in initial conditions allows for a massively parallel search of the sequence space for biologically functional polymers, such as ribozymes. We also propose potential experimental implementations of our model in the contexts of either biopolymers or artificial nano-structures.

How do living cells achieve sufficient abundances of functional protein complexes while minimizing promiscuous nonfunctional interactions? Here we study this problem using a first-principle model of the cell whose phenotypic traits are directly determined from its genome through biophysical properties of protein structures and binding interactions in a crowded cellular environment. The model cell includes three independent prototypical pathways, whose topologies of protein-protein interaction (PPI) subnetworks are different, but whose contributions to the cell fitness are equal. Model cells evolve through genotypic mutations and phenotypic protein copy number variations. We found a strong relationship between evolved physical-chemical properties of protein interactions and their abundances due to a "frustration" effect: Strengthening of functional interactions brings about hydrophobic interfaces, which make proteins prone to promiscuous binding. The balancing act is achieved by lowering concentrations of hub proteins while raising solubilities and abundances of functional monomers. On the basis of these principles we generated and analyzed a possible realization of the proteome-wide PPI network in yeast. In this simulation we found that high-throughput affinity capture-mass spectroscopy experiments can detect functional interactions with high fidelity only for high-abundance proteins while missing most interactions for low-abundance proteins.

It has been reported that the number of transcription factors encoded in prokaryotic genomes scales approximately quadratically with their total number of genes. We propose a conceptual explanation of this finding and illustrate it using a simple model in which metabolic and regulatory networks of prokaryotes are shaped by horizontal gene transfer of coregulated metabolic pathways. Adapting to a new environmental condition monitored by a new transcription factor (e.g., learning to use another nutrient) involves both acquiring new enzymes and reusing some of the enzymes already encoded in the genome. As the repertoire of enzymes of an organism (its toolbox) grows larger, it can reuse its enzyme tools more often and thus needs to get fewer new ones to master each new task. From this observation, it logically follows that the number of functional tasks and their regulators increases faster than linearly with the total number of genes encoding enzymes. Genomes can also shrink, e.g., because of a loss of a nutrient from the environment, followed by deletion of its regulator and all enzymes that become redundant. We propose several simple models of network evolution elaborating on this toolbox argument and reproducing the empirically observed quadratic scaling. The distribution of lengths of pathway branches in our model agrees with that of the real-life metabolic network of Escherichia coli. Thus, our model provides a qualitative explanation for broad distributions of regulon sizes in prokaryotes.

Background: Finding the dominant direction of flow of information in densely interconnected regulatory or signaling networks is required in many applications in computational biology and neuroscience. This is achieved by first identifying and removing links which close up feedback loops in the original network and hierarchically arranging nodes in the remaining network. In mathematical language this corresponds to a problem of making a graph acyclic by removing as few links as possible and thus altering the original graph in the least possible way. The exact solution of this problem requires enumeration of all cycles and combinations of removed links, which, as an NP-hard problem, is computationally prohibitive even for modest-size networks., Results: We introduce and compare two approximate numerical algorithms for solving this problem: the probabilistic one based on a simulated annealing of the hierarchical layout of the network which minimizes the number of "backward" links going from lower to higher hierarchical levels, and the deterministic, "greedy" algorithm that sequentially cuts the links that participate in the largest number of feedback cycles. We find that the annealing algorithm outperforms the deterministic one in terms of speed, memory requirement, and the actual number of removed links. To further improve a visual perception of the layout produced by the annealing algorithm, we perform an additional minimization of the length of hierarchical links while keeping the number of anti-hierarchical links at their minimum. The annealing algorithm is then tested on several examples of regulatory and signaling networks/pathways operating in human cells., Conclusion: The proposed annealing algorithm is powerful enough to performs often optimal layouts of protein networks in whole organisms, consisting of around approximately 10(4) nodes and approximately 10(5) links, while the applicability of the greedy algorithm is limited to individual pathways with approximately 100 vertices. The considered examples indicate that the annealing algorithm produce biologically meaningful layouts: The function of the most of the anti-hierarchical links is indeed to send a feedback signal to the upstream pathway elements. Source codes of F90 and Matlab implementation of the two algorithms are available at http://www.cmth.bnl.gov/~maslov/programs.htm.

We demonstrate that protein-protein interaction networks in several eukaryotic organisms contain significantly more self-interacting proteins than expected if such homodimers randomly appeared in the course of the evolution. We also show that on average homodimers have twice as many interaction partners than non-self-interacting proteins. More specifically, the likelihood of a protein to physically interact with itself was found to be proportional to the total number of its binding partners. These properties of dimers are in agreement with a phenomenological model, in which individual proteins differ from each other by the degree of their 'stickiness' or general propensity toward interaction with other proteins including oneself. A duplication of self-interacting proteins creates a pair of paralogous proteins interacting with each other. We show that such pairs occur more frequently than could be explained by pure chance alone. Similar to homodimers, proteins involved in heterodimers with their paralogs on average have twice as many interacting partners than the rest of the network. The likelihood of a pair of paralogous proteins to interact with each other was also shown to decrease with their sequence similarity. This points to the conclusion that most of interactions between paralogs are inherited from ancestral homodimeric proteins, rather than established de novo after duplication. We finally discuss possible implications of our empirical observations from functional and evolutionary standpoints.

Molecular networks guide the biochemistry of a living cell on multiple levels: Its metabolic and signaling pathways are shaped by the network of interacting proteins, whose production, in turn, is controlled by the genetic regulatory network. To address topological properties of these two networks, we quantified correlations between connectivities of interacting nodes and compared them to a null model of a network, in which all links were randomly rewired. We found that for both interaction and regulatory networks, links between highly connected proteins are systematically suppressed, whereas those between a highly connected and low-connected pairs of proteins are favored. This effect decreases the likelihood of cross talk between different functional modules of the cell and increases the overall robustness of a network by localizing effects of deleterious perturbations.