Context-dependent design of induced-fit enzymes using deep learning generates well-expressed, thermally stable and active enzymes.

The potential of engineered enzymes in industrial applications is often limited by their expression levels, thermal stability, and catalytic diversity. De novo enzyme design faces challenges due to the complexity of enzymatic catalysis. An alternative approach involves expanding natural enzyme capabilities for new substrates and parameters. Here, we introduce CoSaNN (Conformation Sampling using Neural Network), an enzyme design strategy using deep learning for structure prediction and sequence optimization. CoSaNN controls enzyme conformations to expand chemical space beyond simple mutagenesis. It employs a context-dependent approach for generating enzyme designs, considering non-linear relationships in sequence and structure space. We also developed SolvIT, a graph NN predicting protein solubility in Escherichia coli, optimizing enzyme expression selection from larger design sets. Using this method, we engineered enzymes with superior expression levels, with 54% expressed in E. coli, and increased thermal stability, with over 30% having higher Tm than the template, with no high-throughput screening. Our research underscores AI's transformative role in protein design, capturing high-order interactions and preserving allosteric mechanisms in extensively modified enzymes, and notably enhancing expression success rates. This method's ease of use and efficiency streamlines enzyme design, opening broad avenues for biotechnological applications and broadening field accessibility.

The Fitness Effects of Codon Composition of the Horizontally Transferred Antibiotic Resistance Genes Intensify at Sub-lethal Antibiotic Levels.

The rampant variability in codon bias existing between bacterial genomes is expected to interfere with horizontal gene transfer (HGT), a phenomenon that drives bacterial adaptation. However, delineating the constraints imposed by codon bias on functional integration of the transferred genes is complicated by multiple genomic and functional barriers controlling HGT, and by the dependence of the evolutionary outcomes of HGT on the host's environment. Here, we designed an experimental system in which codon composition of the transferred genes is the only variable triggering fitness change of the host. We replaced Escherichia coli's chromosomal folA gene encoding dihydrofolate reductase, an essential enzyme that constitutes a target for trimethoprim, with combinatorial libraries of synonymous codons of folA genes from trimethoprim-sensitive Listeria grayi and trimethoprim-resistant Neisseria sicca. The resulting populations underwent selection at a range of trimethoprim concentrations, and the ensuing changes in variant frequencies were used to infer the fitness effects of the individual combinations of codons. We found that when HGT causes overstabilization of the 5'-end mRNA, the fitness contribution of mRNA folding stability dominates over that of codon optimality. The 5'-end overstabilization can also lead to mRNA accumulation outside of the polysome, thus preventing the decay of the foreign transcripts despite the codon composition-driven reduction in translation efficiency. Importantly, the fitness effects of mRNA stability or codon optimality become apparent only at sub-lethal levels of trimethoprim individually tailored for each library, emphasizing the central role of the host's environment in shaping the codon bias compatibility of horizontally transferred genes.

A biological solution to a fundamental distributed computing problem.

Computational and biological systems are often distributed so that processors (cells) jointly solve a task, without any of them receiving all inputs or observing all outputs. Maximal independent set (MIS) selection is a fundamental distributed computing procedure that seeks to elect a set of local leaders in a network. A variant of this problem is solved during the development of the fly's nervous system, when sensory organ precursor (SOP) cells are chosen. By studying SOP selection, we derived a fast algorithm for MIS selection that combines two attractive features. First, processors do not need to know their degree; second, it has an optimal message complexity while only using one-bit messages. Our findings suggest that simple and efficient algorithms can be developed on the basis of biologically derived insights.

Approximate maximum parsimony and ancestral maximum likelihood.

We explore the maximum parsimony (MP) and ancestral maximum likelihood (AML) criteria in phylogenetic tree reconstruction. Both problems are NP-hard, so we seek approximate solutions. We formulate the two problems as Steiner tree problems under appropriate distances. The gist of our approach is the succinct characterization of Steiner trees for a small number of leaves for the two distances. This enables the use of known Steiner tree approximation algorithms. The approach leads to a 16/9 approximation ratio for AML and asymptotically to a 1.55 approximation ratio for MP.

Biomolecular network motif counting and discovery by color coding.

Protein-protein interaction (PPI) networks of many organisms share global topological features such as degree distribution, k-hop reachability, betweenness and closeness. Yet, some of these networks can differ significantly from the others in terms of local structures: e.g. the number of specific network motifs can vary significantly among PPI networks. Counting the number of network motifs provides a major challenge to compare biomolecular networks. Recently developed algorithms have been able to count the number of induced occurrences of subgraphs with k < or = 7 vertices. Yet no practical algorithm exists for counting non-induced occurrences, or counting subgraphs with k > or = 8 vertices. Counting non-induced occurrences of network motifs is not only challenging but also quite desirable as available PPI networks include several false interactions and miss many others. In this article, we show how to apply the 'color coding' technique for counting non-induced occurrences of subgraph topologies in the form of trees and bounded treewidth subgraphs. Our algorithm can count all occurrences of motif G' with k vertices in a network G with n vertices in time polynomial with n, provided k = O(log n). We use our algorithm to obtain 'treelet' distributions for k < or = 10 of available PPI networks of unicellular organisms (Saccharomyces cerevisiae Escherichia coli and Helicobacter Pyloris), which are all quite similar, and a multicellular organism (Caenorhabditis elegans) which is significantly different. Furthermore, the treelet distribution of the unicellular organisms are similar to that obtained by the 'duplication model' but are quite different from that of the 'preferential attachment model'. The treelet distribution is robust w.r.t. sparsification with bait/edge coverage of 70% but differences can be observed when bait/edge coverage drops to 50%.

Resolution enhancement in MRI.

We consider the problem of super-resolution reconstruction (SRR) in MRI. Subpixel-shifted MR images were taken in several fields of view (FOVs) to reconstruct a high-resolution image. A novel algorithm is presented. The algorithm can be applied locally and guarantees perfect reconstruction in the absence of noise. Results that demonstrate resolution improvement are given for phantom studies (mathematical model) as well as for MRI studies of a phantom carried out with a GE clinical scanner. The method raises questions that are discussed in the last section of the paper. Open questions should be answered in order to apply this method for clinical purposes.

Multi-node graphs: a framework for multiplexed biological assays.

Multiplex polymerase chain reaction (PCR) is an extension of the standard PCR protocol in which primers for multiple DNA loci are pooled together within a single reaction tube, enabling simultaneous sequence amplification, thus reducing costs and saving time. Potential cost saving and throughput improvements directly depend on the level of multiplexing achieved. Designing reliable and highly multiplexed assays is challenging because primers that are pooled together in a single reaction tube may cross-hybridize, though this can be addressed either by modifying the choice of primers for one or more amplicons, or by altering the way in which DNA loci are partitioned into separate reaction tubes. In this paper, we introduce a new graph formalism called a multi-node graph, and describe its application to the analysis of multiplex PCR scalability. We show, using random multi-node graphs that the scalability of multiplex PCR is constrained by a phase transition, suggesting fundamental limits on efforts to improve the cost-effectiveness and throughput of standard multiplex PCR assays. In particular, we show that when the multiplexing level of the reaction tubes is roughly theta(log (sn)) (where s is the number of primer pair candidates per locus and n is the number of loci to be amplified), then with very high probability we can 'cover' all loci with a valid assignment to one of the tubes in the assay. However, when the multiplexing level of the tube exceeds these bounds, there is no possible cover and moreover the size of the cover drops dramatically. Simulations using a simple greedy algorithm on real DNA data also confirm the presence of this phase transition. Our theoretical results suggest, however, that the resulting phase transition is a fundamental characteristic of the problem, implying intrinsic limits on the development of future assay design algorithms.