Browse
Submit Data
Databases
API
Help

Dataset Information

21 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Efficient computation of optimal actions.

ABSTRACT: 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.

SUBMITTER: Todorov E

PROVIDER: S-EPMC2705278 | biostudies-literature |

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Similar Datasets

Efficient computation of optimal oligo-RNA binding.

Project description: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 algorithm performs well in practice with the aid of a heuristic for large asymmetric loops. To demonstrate its speed and utility, we use bindigo to investigate the binding proclivities of U1 snRNA to mRNA donor splice sites.

| S-EPMC545450 | biostudies-literature

Efficient computation of spaced seeds.

Project description:BackgroundThe 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.FindingsSpEED 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.ConclusionMultiple 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

Efficient Computation of Geometries for Gold Complexes.

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

Graph diffusion distance: Properties and efficient computation.

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

PSEUDOMARKER 2.0: efficient computation of likelihoods using NOMAD.

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

Efficient computation of stochastic cell-size transient dynamics.

Project description:BACKGROUND:How small, fast-growing bacteria ensure tight cell-size distributions remains elusive. High-throughput measurement techniques have propelled efforts to build modeling tools that help to shed light on the relationships between cell size, growth and cycle progression. Most proposed models describe cell division as a discrete map between size at birth and size at division with stochastic fluctuations assumed. However, such models underestimate the role of cell size transient dynamics by excluding them. RESULTS:We propose an efficient approach for estimation of cell size transient dynamics. Our technique approximates the transient size distribution and statistical moment dynamics of exponential growing cells following an adder strategy with arbitrary precision. CONCLUSIONS:We approximate, up to arbitrary precision, the distribution of division times and size across time for the adder strategy in rod-shaped bacteria cells. Our approach is able to compute statistical moments like mean size and its variance from such distributions efficiently, showing close match with numerical simulations. Additionally, we observed that these distributions have periodic properties. Our approach further might shed light on the mechanisms behind gene product homeostasis.

| S-EPMC6933677 | biostudies-literature

Efficient computation of absent words in genomic sequences.

Project description:BackgroundAnalysis 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.ResultsWe 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.ConclusionThe 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

Efficient computation of spaced seed hashing with block indexing.

Project description:BackgroundSpaced-seeds, i.e. patterns in which some fixed positions are allowed to be wild-cards, play a crucial role in several bioinformatics applications involving substrings counting and indexing, by often providing better sensitivity with respect to k-mers based approaches. K-mers based approaches are usually fast, being based on efficient hashing and indexing that exploits the large overlap between consecutive k-mers. Spaced-seeds hashing is not as straightforward, and it is usually computed from scratch for each position in the input sequence. Recently, the FSH (Fast Spaced seed Hashing) approach was proposed to improve the time required for computation of the spaced seed hashing of DNA sequences with a speed-up of about 1.5 with respect to standard hashing computation.ResultsIn this work we propose a novel algorithm, Fast Indexing for Spaced seed Hashing (FISH), based on the indexing of small blocks that can be combined to obtain the hashing of spaced-seeds of any length. The method exploits the fast computation of the hashing of runs of consecutive 1 in the spaced seeds, that basically correspond to k-mer of the length of the run.ConclusionsWe run several experiments, on NGS data from simulated and synthetic metagenomic experiments, to assess the time required for the computation of the hashing for each position in each read with respect to several spaced seeds. In our experiments, FISH can compute the hashing values of spaced seeds with a speedup, with respect to the traditional approach, between 1.9x to 6.03x, depending on the structure of the spaced seeds.

| S-EPMC6266934 | biostudies-literature

Choosing efficient actions: Deciding where to walk.

Project description:Humans evolved to be endurance animals. Our ancestors were persistence hunters; they would chase animals, including gazelles, until they ran them into exhaustion. Put simply, people evolved in an ecological niche that selected for endurance and efficiency of locomotion. To locomote to any destination, one could take countless different paths, each requiring different amounts of energy. Because the ground is typically not flat or homogeneous, the straight direct path is often not the most energetically efficient. For hills below 14°, the direct straight path up the hill is the most energetically efficient. However, for hills above 14°, walkers would minimize their absolute energy expenditure by taking a zigzagged path so that their gradient of ascension is 14° [1]. In three experiments, we assessed the degree to which people make bioenergetically efficient decisions about locomotion through path selection. In Experiment 1, people were immersed into a virtual environment and adjusted the angle of ascension of a virtual path up hills of various gradients so that when taking the path, they would expend the least amount of energy when they reached the top. The second experiment was of a similar design, but was conducted in the real word. In the last experiment, in a virtual environment, participants choose between two paths up hills of various gradient, where these paths varied in the energy required for ascent. Participants made these judgements both before and after motor experience with gradient climbing on an incline trainer. For steep hills, we found that people choose much straighter paths over the bioenergetically optimal zigzagged paths. Motor experience did lead to higher probability for choosing optimal paths for steep hills, but lead to less optimal paths for shallower ones. These results show clearly that individuals show a straight path bias when deciding how to ascend hills.

| S-EPMC6762191 | biostudies-literature

Efficient and Flexible Computation of Many-Electron Wave Function Overlaps.

Project description:A new algorithm for the computation of the overlap between many-electron wave functions is described. This algorithm allows for the extensive use of recurring intermediates and thus provides high computational efficiency. Because of the general formalism employed, overlaps can be computed for varying wave function types, molecular orbitals, basis sets, and molecular geometries. This paves the way for efficiently computing nonadiabatic interaction terms for dynamics simulations. In addition, other application areas can be envisaged, such as the comparison of wave functions constructed at different levels of theory. Aside from explaining the algorithm and evaluating the performance, a detailed analysis of the numerical stability of wave function overlaps is carried out, and strategies for overcoming potential severe pitfalls due to displaced atoms and truncated wave functions are presented.

| S-EPMC4785508 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data