A hierarchical exact accelerated stochastic simulation algorithm.
Ontology highlight
ABSTRACT:
SUBMITTER: Orendorff D
PROVIDER: S-EPMC3531277 | biostudies-other | 2012 Dec
REPOSITORIES: biostudies-other
Similar Datasets
Project description:The Gillespie Stochastic Simulation Algorithm (GSSA) and its variants are cornerstone techniques to simulate reaction kinetics in situations where the concentration of the reactant is too low to allow deterministic techniques such as differential equations. The inherent limitations of the GSSA include the time required for executing a single run and the need for multiple runs for parameter sweep exercises due to the stochastic nature of the simulation. Even very efficient variants of GSSA are prohibitively expensive to compute and perform parameter sweeps. Here we present a novel variant of the exact GSSA that is amenable to acceleration by using graphics processing units (GPUs). We parallelize the execution of a single realization across threads in a warp (fine-grained parallelism). A warp is a collection of threads that are executed synchronously on a single multi-processor. Warps executing in parallel on different multi-processors (coarse-grained parallelism) simultaneously generate multiple trajectories. Novel data-structures and algorithms reduce memory traffic, which is the bottleneck in computing the GSSA. Our benchmarks show an 8×-120× performance gain over various state-of-the-art serial algorithms when simulating different types of models.
| S-EPMC3494724 | biostudies-literature
Project description:The "Tau-Leap" strategy for stochastic simulations of chemical reaction systems due to Gillespie and co-workers has had considerable impact on various applications. This strategy is reexamined with Chebyshev's inequality for random variables as it provides a rigorous probabilistic basis for a measured ?-leap thus adding significantly to simulation efficiency. It is also shown that existing strategies for simulation times have no probabilistic assurance that they satisfy the ?-leap criterion while the use of Chebyshev's inequality leads to a specified degree of certainty with which the ?-leap criterion is satisfied. This reduces the loss of sample paths which do not comply with the ?-leap criterion. The performance of the present algorithm is assessed, with respect to one discussed by Cao et al. (J. Chem. Phys.2006, 124, 044109), a second pertaining to binomial leap (Tian and Burrage J. Chem. Phys.2004, 121, 10356; Chatterjee et al. J. Chem. Phys.2005, 122, 024112; Peng et al. J. Chem. Phys.2007, 126, 224109), and a third regarding the midpoint Poisson leap (Peng et al., 2007; Gillespie J. Chem. Phys.2001, 115, 1716). The performance assessment is made by estimating the error in the histogram measured against that obtained with the so-called stochastic simulation algorithm. It is shown that the current algorithm displays notably less histogram error than its predecessor for a fixed computation time and, conversely, less computation time for a fixed accuracy. This computational advantage is an asset in repetitive calculations essential for modeling stochastic systems. The importance of stochastic simulations is derived from diverse areas of application in physical and biological sciences, process systems, and economics, etc. Computational improvements such as those reported herein are therefore of considerable significance.
| S-EPMC4299402 | biostudies-literature
Project description:Stochastic simulation of reaction-diffusion systems enables the investigation of stochastic events arising from the small numbers and heterogeneous distribution of molecular species in biological cells. Stochastic variations in intracellular microdomains and in diffusional gradients play a significant part in the spatiotemporal activity and behavior of cells. Although an exact stochastic simulation that simulates every individual reaction and diffusion event gives a most accurate trajectory of the system's state over time, it can be too slow for many practical applications. We present an accelerated algorithm for discrete stochastic simulation of reaction-diffusion systems designed to improve the speed of simulation by reducing the number of time-steps required to complete a simulation run. This method is unique in that it employs two strategies that have not been incorporated in existing spatial stochastic simulation algorithms. First, diffusive transfers between neighboring subvolumes are based on concentration gradients. This treatment necessitates sampling of only the net or observed diffusion events from higher to lower concentration gradients rather than sampling all diffusion events regardless of local concentration gradients. Second, we extend the non-negative Poisson tau-leaping method that was originally developed for speeding up nonspatial or homogeneous stochastic simulation algorithms. This method calculates each leap time in a unified step for both reaction and diffusion processes while satisfying the leap condition that the propensities do not change appreciably during the leap and ensuring that leaping does not cause molecular populations to become negative. Numerical results are presented that illustrate the improvement in simulation speed achieved by incorporating these two new strategies.
| S-EPMC3089647 | biostudies-other
Project description:MotivationAnalysis of the omics data with the help of machine learning (ML) methods is limited by small sample sizes and a large number of variables. One possible approach to deal with such data is using algorithms for feature selection and reducing the dataset to include only those variables that are related to the studied phenomena. Existing simulators of the omics data were mostly developed with the goal of improving the methods for generations of high-quality data, that correspond with the highest possible fidelity to the real level of molecular markers in the biological materials. The current study aims to simulate the data on a higher level of generalization. Such datasets can then be used to perform tests of the feature selection and ML algorithms on systems that have structures mimicking those of real data, but where the ground truth may be implanted by design. They can also be used to generate contrast variables with the desired correlation structure for the feature selection.ResultsWe proposed the algorithm for the reconstruction of the omic dataset that, with high fidelity, preserves the correlation structure of the original data with a reduced number of parameters. It is based on the hierarchical clustering of variables and uses principal components of the clusters. It reproduces well topological descriptors of the correlation structure. The correlation structure of the principal components of the clusters then is used to obtain datasets with correlation structures similar to the original data but not correlated with the original variables.Availability and implementationThe code and data is available at: https://github.com/p100mma/hcrs_omics.
| S-EPMC11373347 | biostudies-literature
Project description:In recent years there has been substantial growth in the development of algorithms for characterizing rare events in stochastic biochemical systems. Two such algorithms, the state-dependent weighted stochastic simulation algorithm (swSSA) and the doubly weighted SSA (dwSSA) are extensions of the weighted SSA (wSSA) by H. Kuwahara and I. Mura [J. Chem. Phys. 129, 165101 (2008)]. The swSSA substantially reduces estimator variance by implementing system state-dependent importance sampling (IS) parameters, but lacks an automatic parameter identification strategy. In contrast, the dwSSA provides for the automatic determination of state-independent IS parameters, thus it is inefficient for systems whose states vary widely in time. We present a novel modification of the dwSSA--the state-dependent doubly weighted SSA (sdwSSA)--that combines the strengths of the swSSA and the dwSSA without inheriting their weaknesses. The sdwSSA automatically computes state-dependent IS parameters via the multilevel cross-entropy method. We apply the method to three examples: a reversible isomerization process, a yeast polarization model, and a lac operon model. Our results demonstrate that the sdwSSA offers substantial improvements over previous methods in terms of both accuracy and efficiency.
| S-EPMC3264419 | biostudies-other
Project description:BackgroundAlthough oligonucleotide microarray technology is ubiquitous in genomic research, reproducibility and standardization of expression measurements still concern many researchers. Cross-hybridization between microarray probes and non-target ssDNA has been implicated as a primary factor in sensitivity and selectivity loss. Since hybridization is a chemical process, it may be modeled at a population-level using a combination of material balance equations and thermodynamics. However, the hybridization reaction network may be exceptionally large for commercial arrays, which often possess at least one reporter per transcript. Quantification of the kinetics and equilibrium of exceptionally large chemical systems of this type is numerically infeasible with customary approaches.ResultsIn this paper, we present a robust and computationally efficient algorithm for the simulation of hybridization processes underlying microarray assays. Our method may be utilized to identify the extent to which nucleic acid targets (e.g. cDNA) will cross-hybridize with probes, and by extension, characterize probe robustnessusing the information specified by MAGE-TAB. Using this algorithm, we characterize cross-hybridization in a modified commercial microarray assay.ConclusionsBy integrating stochastic simulation with thermodynamic prediction tools for DNA hybridization, one may robustly and rapidly characterize of the selectivity of a proposed microarray design at the probe and "system" levels. Our code is available at http://www.laurenzi.net.
| S-EPMC2805644 | biostudies-literature
Project description:BackgroundClinical practice of Chinese medicine requires little information for differentiation of Zang-fu patterns. This study is to test the impact of information amount on the diagnostic accuracy of pattern differentiation algorithm (PDA) using stochastic simulation of cases.MethodsA dataset with 69 Zang-fu single patterns was used with manifestations according to the Four Examinations, namely inspection (Ip), auscultation and olfaction (AO), inquiry (Iq) and palpation (P). A variable quantity of available information (N(%)) was randomly sampled to generate 100 true positive and 100 true negative manifestation profiles per pattern to which PDA was applied. Four runs of simulations were used according to the Four Examinations: Ip, Ip+AO, Ip+AO+Iq and Ip+AO+Iq+P. The algorithm performed pattern differentiation by ranking a list of diagnostic hypotheses by the amount of explained information F(%). Accuracy, sensitivity, specificity and negative and positive predictive values were calculated.ResultsUse the Four Examinations resulted in the best accuracy with the smallest cutoff value (N(%)= 28.5%), followed by Ip+AO+Iq (33.5%), Ip+AO (51.5%) and Ip (52.0%). All tested combinations provided concave-shaped curves for accuracy, indicating an optimal value subject to N(%-cutoff). Use of N(%-cutoff) as a secondary criterion resulted in 94.7% (94.3; 95.1) accuracy, 89.8% (89.1; 90.6) sensitivity, and 99.5% (99.3; 99.7) specificity with the Four Examinations.ConclusionPattern differentiation based on both explained and optimum available information (F(%) and N(%-cutoff)) is more accurate than using explained and available information without cutoff (F(%) and N(%)). Both F(%) and N(%-cutoff) should be used as PDA's objective criteria to perform Zang-fu single pattern differentiation.
| S-EPMC2806360 | biostudies-literature
Project description:We present the validation of the hybrid sSSA-SDPD method for advection-diffusion-reaction problems coupled to discrete biochemical systems, as presented in the publication "A hybrid smoothed dissipative particle dynamics (SDPD) spatial stochastic simulation algorithm (sSSA) for advection-diffusion-reaction problems" (Drawert et al., 2019). We validate 1D diffusion, and 2D diffusion cases against their analytical solutions. We present graphs and tables of data showing the error in the simulation method.
| S-EPMC6293021 | biostudies-literature
Project description:We present a discrete model of stochastic excitability by a low-dimensional set of delayed integral equations governing the probability in the rest state, the excited state, and the refractory state. The process is a random walk with discrete states and nonexponential waiting time distributions, which lead to the incorporation of memory kernels in the integral equations. We extend the equations of a single unit to the system of equations for an ensemble of globally coupled oscillators, derive the mean field equations, and investigate bifurcations of steady states. Conditions of destabilization are found, which imply oscillations of the mean fields in the stochastic ensemble. The relation between the mean field equations and the paradigmatic Kuramoto model is shown.
| S-EPMC2652551 | biostudies-other
Project description:In recent years we have witnessed a growth in sequencing yield, the number of samples sequenced, and as a result-the growth of publicly maintained sequence databases. The increase of data present all around has put high requirements on protein similarity search algorithms with two ever-opposite goals: how to keep the running times acceptable while maintaining a high-enough level of sensitivity. The most time consuming step of similarity search are the local alignments between query and database sequences. This step is usually performed using exact local alignment algorithms such as Smith-Waterman. Due to its quadratic time complexity, alignments of a query to the whole database are usually too slow. Therefore, the majority of the protein similarity search methods prior to doing the exact local alignment apply heuristics to reduce the number of possible candidate sequences in the database. However, there is still a need for the alignment of a query sequence to a reduced database. In this paper we present the SW#db tool and a library for fast exact similarity search. Although its running times, as a standalone tool, are comparable to the running times of BLAST, it is primarily intended to be used for exact local alignment phase in which the database of sequences has already been reduced. It uses both GPU and CPU parallelization and was 4-5 times faster than SSEARCH, 6-25 times faster than CUDASW++ and more than 20 times faster than SSW at the time of writing, using multiple queries on Swiss-prot and Uniref90 databases.
| S-EPMC4699916 | biostudies-literature