Browse
Submit Data
Databases
API
Help

Dataset Information

25 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Searching with iterated maps.

ABSTRACT: In many problems that require extensive searching, the solution can be described as satisfying two competing constraints, where satisfying each independently does not pose a challenge. As an alternative to tree-based and stochastic searching, for these problems we propose using an iterated map built from the projections to the two constraint sets. Algorithms of this kind have been the method of choice in a large variety of signal-processing applications; we show here that the scope of these algorithms is surprisingly broad, with applications as diverse as protein folding and Sudoku.

SUBMITTER: Elser V

PROVIDER: S-EPMC1766399 | biostudies-literature | 2007 Jan

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Searching with iterated maps.

Elser V V Rankenburg I I Thibault P P

Proceedings of the National Academy of Sciences of the United States of America 20070103 2

In many problems that require extensive searching, the solution can be described as satisfying two competing constraints, where satisfying each independently does not pose a challenge. As an alternative to tree-based and stochastic searching, for these problems we propose using an iterated map built from the projections to the two constraint sets. Algorithms of this kind have been the method of choice in a large variety of signal-processing applications; we show here that the scope of these algo ...[more]

PMID: 17202267

Similar Datasets

Accelerating multidimensional NMR and MRI experiments using iterated maps.

Project description:Techniques that accelerate data acquisition without sacrificing the advantages of fast Fourier transform (FFT) reconstruction could benefit a wide variety of magnetic resonance experiments. Here we discuss an approach for reconstructing multidimensional nuclear magnetic resonance (NMR) spectra and MR images from sparsely-sampled time domain data, by way of iterated maps. This method exploits the computational speed of the FFT algorithm and is done in a deterministic way, by reformulating any a priori knowledge or constraints into projections, and then iterating. In this paper we explain the motivation behind this approach, the formulation of the specific projections, the benefits of using a 'QUasi-Even Sampling, plus jiTter' (QUEST) sampling schedule, and various methods for handling noise. Applying the iterated maps method to real 2D NMR and 3D MRI of solids data, we show that it is flexible and robust enough to handle large data sets with significant noise and artifacts.

| S-EPMC4238918 | biostudies-literature

Accelerating 2D NMR relaxation dispersion experiments using iterated maps.

Project description:NMR relaxation dispersion experiments play a central role in exploring molecular motion over an important range of timescales, and are an example of a broader class of multidimensional NMR experiments that probe important biomolecules. However, resolving the spectral features of these experiments using the Fourier transform requires sampling the full Nyquist grid of data, making these experiments very costly in time. Practitioners often reduce the experiment time by omitting 1D experiments in the indirectly observed dimensions, and reconstructing the spectra using one of a variety of post-processing algorithms. In prior work, we described a fast, Fourier-based reconstruction method using iterated maps according to the Difference Map algorithm of Veit Elser (DiffMap). Here we describe coDiffMap, a new reconstruction method that is based on DiffMap, but which exploits the strong correlations between 2D data slices in a pseudo-3D experiment. We apply coDiffMap to reconstruct dispersion curves from an [Formula: see text] relaxation dispersion experiment, and demonstrate that the method provides fast reconstructions and accurate relaxation curves down to very low numbers of sparsely-sampled data points.

| S-EPMC7370911 | biostudies-literature

Inference for dynamic and latent variable models via iterated, perturbed Bayes maps.

Project description:Iterated filtering algorithms are stochastic optimization procedures for latent variable models that recursively combine parameter perturbations with latent variable reconstruction. Previously, theoretical support for these algorithms has been based on the use of conditional moments of perturbed parameters to approximate derivatives of the log likelihood function. Here, a theoretical approach is introduced based on the convergence of an iterated Bayes map. An algorithm supported by this theory displays substantial numerical improvement on the computational challenge of inferring parameters of a partially observed Markov process.

| S-EPMC4311819 | biostudies-other

Reaching the sparse-sampling limit for reconstructing a single peak in a 2D NMR spectrum using iterated maps.

Project description:Many of the ubiquitous experiments of biomolecular NMR, including [Formula: see text], [Formula: see text], and CEST, involve acquiring repeated 2D spectra under slightly different conditions. Such experiments are amenable to acceleration using non-uniform sampling spectral reconstruction methods that take advantage of prior information. We previously developed one such technique, an iterated maps method (DiffMap) that we successfully applied to 2D NMR spectra, including [Formula: see text] relaxation dispersion data. In that prior work, we took a top-down approach to reconstructing the 2D spectrum with a minimal number of sparse samples, reaching an undersampling fraction that appeared to leave some room for improvement. In this study, we develop an in-depth understanding of the action of the DiffMap algorithm, identifying the factors that cause reconstruction errors for different undersampling fractions. This improved understanding allows us to formulate a bottom-up approach to finding the lowest number of sparse samples required to accurately reconstruct individual spectral features with DiffMap. We also discuss the difficulty of extending this method to reconstructing many peaks at once, and suggest a way forward.

| S-EPMC7384587 | biostudies-literature

Filling gaps of genome scaffolds via probabilistic searching optical maps against assembly graph

Project description:Background Optical maps record locations of specific enzyme recognition sites within long genome fragments. This long-distance information enables aligning genome assembly contigs onto optical maps and ordering contigs into scaffolds. The generated scaffolds, however, often contain a large amount of gaps. To fill these gaps, a feasible way is to search genome assembly graph for the best-matching contig paths that connect boundary contigs of gaps. The combination of searching and evaluation procedures might be “searching followed by evaluation”, which is infeasible for long gaps, or “searching by evaluation”, which heavily relies on heuristics and thus usually yields unreliable contig paths. Results We here report an accurate and efficient approach to filling gaps of genome scaffolds with aids of optical maps. Using simulated data from 12 species and real data from 3 species, we demonstrate the successful application of our approach in gap filling with improved accuracy and completeness of genome scaffolds. Conclusion Our approach applies a sequential Bayesian updating technique to measure the similarity between optical maps and candidate contig paths. Using this similarity to guide path searching, our approach achieves higher accuracy than the existing “searching by evaluation” strategy that relies on heuristics. Furthermore, unlike the “searching followed by evaluation” strategy enumerating all possible paths, our approach prunes the unlikely sub-paths and extends the highly-probable ones only, thus significantly increasing searching efficiency. Supplementary Information The online version contains supplementary material available at 10.1186/s12859-021-04448-2.

| S-EPMC8557617 | biostudies-literature

Iterated crowdsourcing dilemma game.

Project description:The Internet has enabled the emergence of collective problem solving, also known as crowdsourcing, as a viable option for solving complex tasks. However, the openness of crowdsourcing presents a challenge because solutions obtained by it can be sabotaged, stolen, and manipulated at a low cost for the attacker. We extend a previously proposed crowdsourcing dilemma game to an iterated game to address this question. We enumerate pure evolutionarily stable strategies within the class of so-called reactive strategies, i.e., those depending on the last action of the opponent. Among the 4096 possible reactive strategies, we find 16 strategies each of which is stable in some parameter regions. Repeated encounters of the players can improve social welfare when the damage inflicted by an attack and the cost of attack are both small. Under the current framework, repeated interactions do not really ameliorate the crowdsourcing dilemma in a majority of the parameter space.

| S-EPMC3924214 | biostudies-other

A second-order iterated smoothing algorithm.

Project description:Simulation-based inference for partially observed stochastic dynamic models is currently receiving much attention due to the fact that direct computation of the likelihood is not possible in many practical situations. Iterated filtering methodologies enable maximization of the likelihood function using simulation-based sequential Monte Carlo filters. Doucet et al. (2013) developed an approximation for the first and second derivatives of the log likelihood via simulation-based sequential Monte Carlo smoothing and proved that the approximation has some attractive theoretical properties. We investigated an iterated smoothing algorithm carrying out likelihood maximization using these derivative approximations. Further, we developed a new iterated smoothing algorithm, using a modification of these derivative estimates, for which we establish both theoretical results and effective practical performance. On benchmark computational challenges, this method beat the first-order iterated filtering algorithm. The method's performance was comparable to a recently developed iterated filtering algorithm based on an iterated Bayes map. Our iterated smoothing algorithm and its theoretical justification provide new directions for future developments in simulation-based inference for latent variable models such as partially observed Markov process models.

| S-EPMC5573285 | biostudies-literature

Cyclic game dynamics driven by iterated reasoning.

Project description:Recent theories from complexity science argue that complex dynamics are ubiquitous in social and economic systems. These claims emerge from the analysis of individually simple agents whose collective behavior is surprisingly complicated. However, economists have argued that iterated reasoning--what you think I think you think--will suppress complex dynamics by stabilizing or accelerating convergence to Nash equilibrium. We report stable and efficient periodic behavior in human groups playing the Mod Game, a multi-player game similar to Rock-Paper-Scissors. The game rewards subjects for thinking exactly one step ahead of others in their group. Groups that play this game exhibit cycles that are inconsistent with any fixed-point solution concept. These cycles are driven by a "hopping" behavior that is consistent with other accounts of iterated reasoning: agents are constrained to about two steps of iterated reasoning and learn an additional one-half step with each session. If higher-order reasoning can be complicit in complex emergent dynamics, then cyclic and chaotic patterns may be endogenous features of real-world social and economic systems.

| S-EPMC3575333 | biostudies-literature

Experimental Evidence on Iterated Reasoning in Games.

Project description:We present experimental evidence on two forms of iterated reasoning in games, i.e. backward induction and interactive knowledge. Besides reliable estimates of the cognitive skills of the subjects, our design allows us to disentangle two possible explanations for the observed limits in performed iterated reasoning: Restrictions in subjects' cognitive abilities and their beliefs concerning the rationality of co-players. In comparison to previous literature, our estimates regarding subjects' skills in iterated reasoning are quite pessimistic. Also, we find that beliefs concerning the rationality of co-players are completely irrelevant in explaining the observed limited amount of iterated reasoning in the dirty faces game. In addition, it is demonstrated that skills in backward induction are a solid predictor for skills in iterated knowledge, which points to some generalized ability of the subjects in iterated reasoning.

| S-EPMC4552469 | biostudies-literature

Evolution of extortion in Iterated Prisoner's Dilemma games.

Project description:Iterated games are a fundamental component of economic and evolutionary game theory. They describe situations where two players interact repeatedly and have the ability to use conditional strategies that depend on the outcome of previous interactions, thus allowing for reciprocation. Recently, a new class of strategies has been proposed, so-called "zero-determinant" strategies. These strategies enforce a fixed linear relationship between one's own payoff and that of the other player. A subset of those strategies allows "extortioners" to ensure that any increase in one player's own payoff exceeds that of the other player by a fixed percentage. Here, we analyze the evolutionary performance of this new class of strategies. We show that in reasonably large populations, they can act as catalysts for the evolution of cooperation, similar to tit-for-tat, but that they are not the stable outcome of natural selection. In very small populations, however, extortioners hold their ground. Extortion strategies do particularly well in coevolutionary arms races between two distinct populations. Significantly, they benefit the population that evolves at the slower rate, an example of the so-called "Red King" effect. This may affect the evolution of interactions between host species and their endosymbionts.

| S-EPMC3637695 | 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