Selection protocols such as SELEX, where molecules are selected over multiple rounds for their ability to bind to a target of interest, are popular methods for obtaining binders for diagnostic and therapeutic purposes. We show that Restricted Boltzmann Machines (RBMs), an unsupervised two-layer neural network architecture, can successfully be trained on sequence ensembles from single rounds of SELEX experiments for thrombin aptamers. RBMs assign scores to sequences that can be directly related to their fitnesses estimated through experimental enrichment ratios. Hence, RBMs trained from sequence data at a given round can be used to predict the effects of selection at later rounds. Moreover, the parameters of the trained RBMs are interpretable and identify functional features contributing most to sequence fitness. To exploit the generative capabilities of RBMs, we introduce two different training protocols: one taking into account sequence counts, capable of identifying the few best binders, and another based on unique sequences only, generating more diverse binders. We then use RBMs model to generate novel aptamers with putative disruptive mutations or good binding properties, and validate the generated sequences with gel shift assay experiments. Finally, we compare the RBM’s performance with different supervised learning approaches that include random forests and several deep neural network architectures.
Antigen immunogenicity and the specificity of binding of T-cell receptors to antigens are key properties underlying effective immune responses. Here we propose diffRBM, an approach based on transfer learning and Restricted Boltzmann Machines, to build sequence-based predictive models of these properties. DiffRBM is designed to learn the distinctive patterns in amino-acid composition that, on the one hand, underlie the antigen’s probability of triggering a response, and on the other hand the T-cell receptor’s ability to bind to a given antigen. We show that the patterns learnt by diffRBM allow us to predict putative contact sites of the antigen-receptor complex. We also discriminate immunogenic and non-immunogenic antigens, antigen-specific and generic receptors, reaching performances that compare favorably to existing sequence-based predictors of antigen immunogenicity and T-cell receptor specificity.
Advances in techniques for thermal sampling in classical and quantum systems would deepen understanding of the underlying physics. Unfortunately, one often has to rely solely on inexact numerical simulation, due to the intractability of computing the partition function in many systems of interest. Emerging hardware, such as quantum annealers, provide novel tools for such investigations, but it is well known that studying general, non-native systems on such devices requires graph minor embedding, at the expense of introducing additional variables. The effect of embedding for sampling is more pronounced than for optimization; for optimization one is just concerned with the ground-state physics, whereas for sampling one needs to consider states at all energies. We argue that as the system size or the embedding size grows, the chance of a sample being in the subspace of interest—the logical subspace—can be exponentially suppressed. Though the severity of this scaling can be lessened through favorable parameter choices, certain physical constraints (such as a fixed temperature and range of couplings) provide hard limits on what is currently feasible. Furthermore, we show that up to some practical and reasonable assumptions, any type of postprocessing to project samples back into the logical subspace will bias the resulting statistics. We introduce such a technique, based on resampling, that substantially outperforms majority vote, which is shown to fail quite dramatically at preserving distribution properties.
We show that the average optimal cost for the traveling salesman problem in two dimensions, which is the archetypal problem in combinatorial optimization, in the bipartite case, is simply related to the average optimal cost of the assignment problem with the same Euclidean, increasing, convex weights. In this way we extend a result already known in one dimension where exact solutions are available. The recently determined average optimal cost for the assignment when the cost function is the square of the distance between the points provides therefore an exact prediction for large number of points . As a by-product of our analysis, also the loop covering problem has the same optimal average cost. We also explain why this result cannot be extended to higher dimensions. We numerically check the exact predictions.
Riboswitches are structured allosteric RNA molecules that change conformation upon metabolite binding, triggering a regulatory response. Here we focus on the de novo design of riboswitch-like aptamers, the core part of the riboswitch undergoing structural changes. We use Restricted Boltzmann machines (RBM) to learn generative models from homologous sequence data. We first verify, on four different riboswitch families, that RBM-generated sequences correctly capture the conservation, covariation and diversity of natural aptamers. The RBM model is then used to design new SAM-I riboswitch aptamers. To experimentally validate the properties of the structural switch in designed molecules, we resort to chemical probing (SHAPE and DMS), and develop a tailored analysis pipeline adequate for high-throughput tests of diverse sequences. We probe a total of 476 RBM-designed and 201 natural sequences. Designed molecules with high RBM scores, with 20% to 40% divergence from any natural sequence, display ≈ 30% success rate of responding to SAM with a structural switch similar to their natural counterparts. We show how the capability of the designed molecules to switch conformation is connected to fine energetic features of their structural components.
The traveling-salesman problem is one of the most studied combinatorial optimization problems, because of the simplicity in its statement and the difficulty in its solution. We characterize the optimal cycle for every convex and increasing cost function when the points are thrown independently and with an identical probability distribution in a compact interval. We compute the average optimal cost for every number of points when the distance function is the square of the Euclidean distance. We also show that the average optimal cost is not a self-averaging quantity by explicitly computing the variance of its distribution in the thermodynamic limit. Moreover, we prove that the cost of the optimal cycle is not smaller than twice the cost of the optimal assignment of the same set of points. Interestingly, this bound is saturated in the thermodynamic limit.