Efficient computation of optimal oligo-RNA binding.
Ontology highlight
ABSTRACT:
SUBMITTER: Hodas NO
PROVIDER: S-EPMC545450 | biostudies-literature | 2004
REPOSITORIES: biostudies-literature
Publications
Efficient computation of optimal oligo-RNA binding.
Hodas Nathan O NO Aalberts Daniel P DP
Nucleic acids research 20041217 22
We present an algorithm that calculates the optimal binding conformation and free energy of two RNA molecules, one or both oligomeric. This algorithm has applications to modeling DNA microarrays, RNA splice-site recognitions and other antisense problems. Although other recent algorithms perform the same calculation in time proportional to the sum of the lengths cubed, O((N1 + N2)3), our oligomer binding algorithm, called bindigo, scales as the product of the sequence lengths, O(N1*N2). The algor ...[more]
Similar Datasets
Project description:Optimal choice of actions is a fundamental problem relevant to fields as diverse as neuroscience, psychology, economics, computer science, and control engineering. Despite this broad relevance the abstract setting is similar: we have an agent choosing actions over time, an uncertain dynamical system whose state is affected by those actions, and a performance criterion that the agent seeks to optimize. Solving problems of this kind remains hard, in part, because of overly generic formulations. Here, we propose a more structured formulation that greatly simplifies the construction of optimal control laws in both discrete and continuous domains. An exhaustive search over actions is avoided and the problem becomes linear. This yields algorithms that outperform Dynamic Programming and Reinforcement Learning, and thereby solve traditional problems more efficiently. Our framework also enables computations that were not possible before: composing optimal control laws by mixing primitives, applying deterministic methods to stochastic systems, quantifying the benefits of error tolerance, and inferring goals from behavioral data via convex optimization. Development of a general class of easily solvable problems tends to accelerate progress--as linear systems theory has done, for example. Our framework may have similar impact in fields where optimal choice of actions is relevant.
| S-EPMC2705278 | biostudies-literature
Project description:BACKGROUND: The most frequently used tools in bioinformatics are those searching for similarities, or local alignments, between biological sequences. Since the exact dynamic programming algorithm is quadratic, linear-time heuristics such as BLAST are used. Spaced seeds are much more sensitive than the consecutive seed of BLAST and using several seeds represents the current state of the art in approximate search for biological sequences. The most important aspect is computing highly sensitive seeds. Since the problem seems hard, heuristic algorithms are used. The leading software in the common Bernoulli model is the SpEED program. FINDINGS: SpEED uses a hill climbing method based on the overlap complexity heuristic. We propose a new algorithm for this heuristic that improves its speed by over one order of magnitude. We use the new implementation to compute improved seeds for several software programs. We compute as well multiple seeds of the same weight as MegaBLAST, that greatly improve its sensitivity. CONCLUSION: Multiple spaced seeds are being successfully used in bioinformatics software programs. Enabling researchers to compute very fast high quality seeds will help expanding the range of their applications.
| S-EPMC3392737 | biostudies-literature
Project description:Sm and Sm-like proteins are members of a family of small proteins that is widespread throughout eukaryotic kingdoms. These proteins form heteromers with one another and bind, as heteromeric complexes, to various RNAs, recognizing primarily short U-rich stretches. Interestingly, completion of several genome projects revealed that archaea also contain genes that may encode Sm-like proteins. Herein, we studied the properties of one Sm-like protein derived from the archaebacterium Archaeoglobus fulgidus and overexpressed in Escherichia coli. This single small protein closely reflects the properties of an Sm or Sm-like protein heteromer. It binds to RNA with a high specificity for oligo(U), and assembles onto the RNA to form a complex that exhibits, as judged by electron microscopy, a ring-like structure similar to the ones observed with the Sm core ribonucleoprotein and the like Sm (LSm) protein heteromer. Importantly, multivariate statistical analysis of negative-stain electron-microscopic images revealed a sevenfold symmetry for the observed ring structure, indicating that the proteins form a homoheptamer. These results support the structural model of the Sm proteins derived from crystallographic studies on Sm heterodimers and demonstrate that the Sm protein family evolved from a single ancestor that was present before the eukaryotic and archaeal kingdoms separated.
| S-EPMC31112 | biostudies-literature
Project description:Here we present a novel, end-point method using the dead-end-elimination and A* algorithms to efficiently and accurately calculate the change in free energy, enthalpy, and configurational entropy of binding for ligand-receptor association reactions. We apply the new approach to the binding of a series of human immunodeficiency virus (HIV-1) protease inhibitors to examine the effect ensemble reranking has on relative accuracy as well as to evaluate the role of the absolute and relative ligand configurational entropy losses upon binding in affinity differences for structurally related inhibitors. Our results suggest that most thermodynamic parameters can be estimated using only a small fraction of the full configurational space, and we see significant improvement in relative accuracy when using an ensemble versus single-conformer approach to ligand ranking. We also find that using approximate metrics based on the single-conformation enthalpy differences between the global minimum energy configuration in the bound as well as unbound states also correlates well with experiment. Using a novel, additive entropy expansion based on conditional mutual information, we also analyze the source of ligand configurational entropy loss upon binding in terms of both uncoupled per degree of freedom losses as well as changes in coupling between inhibitor degrees of freedom. We estimate entropic free energy losses of approximately +24 kcal/mol, 12 kcal/mol of which stems from loss of translational and rotational entropy. Coupling effects contribute only a small fraction to the overall entropy change (1-2 kcal/mol) but suggest differences in how inhibitor dihedral angles couple to each other in the bound versus unbound states. The importance of accounting for flexibility in drug optimization and design is also discussed.
| S-EPMC3827837 | biostudies-literature
Project description:In most organisms, ribosomal RNA (rRNA) contributes to >85% of total RNA. Thus, to obtain useful information from RNA-sequencing (RNA-seq) analyses at reasonable sequencing depth, typically, mature polyadenylated transcripts are enriched or rRNA molecules are depleted. Targeted depletion of rRNA is particularly useful when studying transcripts lacking a poly(A) tail, such as some non-coding RNAs (ncRNAs), most bacterial RNAs and partially degraded or immature transcripts. While several commercially available kits allow effective rRNA depletion, their efficiency relies on a high degree of sequence homology between oligonucleotide probes and the target RNA. This restricts the use of such kits to a limited number of organisms with conserved rRNA sequences. In this study we describe the use of biotinylated oligos and streptavidin-coated paramagnetic beads for the efficient and specific depletion of trypanosomal rRNA. Our approach reduces the levels of the most abundant rRNA transcripts to less than 5% with minimal off-target effects. By adjusting the sequence of the oligonucleotide probes, our approach can be used to deplete rRNAs or other abundant transcripts independent of species. Thus, our protocol provides a useful alternative for rRNA removal where enrichment of polyadenylated transcripts is not an option and commercial kits for rRNA are not available.
| S-EPMC6706579 | biostudies-literature
Project description:Computationally obtaining structural parameters along a reaction coordinate is commonly performed with Kohn-Sham density functional theory which generally provides a good balance between speed and accuracy. However, CPU times still range from inconvenient to prohibitive, depending on the size of the system under study. Herein, the tight binding GFN2-xTB method [C. Bannwarth, S. Ehlert, S. Grimme, J. Chem. Theory Comput. 2019, 15, 1652] is investigated as an alternative to produce reasonable geometries along a reaction path, that is, reactant, product and transition state structures for a series of transformations involving gold complexes. A small mean error (1 kcal/mol) was found, with respect to an efficient composite hybrid-GGA exchange-correlation functional (PBEh-3c) paired with a double-ζ basis set, which is 2-3 orders of magnitude slower. The outlined protocol may serve as a rapid tool to probe the viability of proposed mechanistic pathways in the field of gold catalysis.
| S-EPMC8252628 | biostudies-literature
Project description:We define a new family of similarity and distance measures on graphs, and explore their theoretical properties in comparison to conventional distance metrics. These measures are defined by the solution(s) to an optimization problem which attempts find a map minimizing the discrepancy between two graph Laplacian exponential matrices, under norm-preserving and sparsity constraints. Variants of the distance metric are introduced to consider such optimized maps under sparsity constraints as well as fixed time-scaling between the two Laplacians. The objective function of this optimization is multimodal and has discontinuous slope, and is hence difficult for univariate optimizers to solve. We demonstrate a novel procedure for efficiently calculating these optima for two of our distance measure variants. We present numerical experiments demonstrating that (a) upper bounds of our distance metrics can be used to distinguish between lineages of related graphs; (b) our procedure is faster at finding the required optima, by as much as a factor of 103; and (c) the upper bounds satisfy the triangle inequality exactly under some assumptions and approximately under others. We also derive an upper bound for the distance between two graph products, in terms of the distance between the two pairs of factors. Additionally, we present several possible applications, including the construction of infinite "graph limits" by means of Cauchy sequences of graphs related to one another by our distance measure.
| S-EPMC8078789 | biostudies-literature
Project description:Many RNA-binding proteins have modular structures and are composed of multiple repeats of just a few basic domains that are arranged in various ways to satisfy their diverse functional requirements. Recent studies have investigated how different modules cooperate in regulating the RNA-binding specificity and the biological activity of these proteins. They have also investigated how multiple modules cooperate with enzymatic domains to regulate the catalytic activity of enzymes that act on RNA. These studies have shown how, for many RNA-binding proteins, multiple modules define the fundamental structural unit that is responsible for biological function.
| S-EPMC5507177 | biostudies-literature
Project description:PSEUDOMARKER is a software package that performs joint linkage and linkage disequilibrium analysis between a marker and a putative disease locus. A key feature of PSEUDOMARKER is that it can combine case-controls and pedigrees of varying structure into a single unified analysis. Thus it maximizes the full likelihood of the data over marker allele frequencies or conditional allele frequencies on disease and recombination fraction.The new version 2.0 uses the software package NOMAD to maximize likelihoods, resulting in generally comparable or better optima with many fewer evaluations of the likelihood functions.After being modified substantially to use modern optimization methods, PSEUDOMARKER version 2.0 is more robust and substantially faster than version 1.0. NOMAD may be useful in other bioinformatics problems where complex likelihood functions are optimized.
| S-EPMC3932042 | biostudies-literature
Project description:BACKGROUND: Analysis of sequence composition is a routine task in genome research. Organisms are characterized by their base composition, dinucleotide relative abundance, codon usage, and so on. Unique subsequences are markers of special interest in genome comparison, expression profiling, and genetic engineering. Relative to a random sequence of the same length, unique subsequences are overrepresented in real genomes. Shortest words absent from a genome have been addressed in two recent studies. RESULTS: We describe a new algorithm and software for the computation of absent words. It is more efficient than previous algorithms and easier to use. It directly computes unwords without the need to specify a length estimate. Moreover, it avoids the space requirements of index structures such as suffix trees and suffix arrays. Our implementation is available as an open source package. We compute unwords of human and mouse as well as some other organisms, covering a genome size range from 109 down to 105 bp. CONCLUSION: The new algorithm computes absent words for the human genome in 10 minutes on standard hardware, using only 2.5 Mb of space. This enables us to perform this type of analysis not only for the largest genomes available so far, but also for the emerging pan- and meta-genome data.
| S-EPMC2375138 | biostudies-literature