Fast and Exact Continuous Collision Detection with Bernstein Sign Classification.
Ontology highlight
ABSTRACT:
SUBMITTER: Tang M
PROVIDER: S-EPMC4283478 | biostudies-literature | 2014 Nov
REPOSITORIES: biostudies-literature
Publications
Fast and Exact Continuous Collision Detection with Bernstein Sign Classification.
Tang Min M Tong Ruofeng R Wang Zhendong Z Manocha Dinesh D
ACM transactions on graphics 20141101 6
We present fast algorithms to perform accurate CCD queries between triangulated models. Our formulation uses properties of the Bernstein basis and Bézier curves and reduces the problem to evaluating signs of polynomials. We present a geometrically exact CCD algorithm based on the exact geometric computation paradigm to perform reliable Boolean collision queries. Our algorithm is more than an order of magnitude faster than prior exact algorithms. We evaluate its performance for cloth and FEM simu ...[more]
Similar Datasets
Project description:We derive a rigorous, quantum mechanical map of fermionic creation and annihilation operators to continuous Cartesian variables that exactly reproduces the matrix structure of the many-fermion problem. We show how our scheme can be used to map a general many-fermion Hamiltonian and then consider two specific models that encode the fundamental physics of many fermionic systems, the Anderson impurity and Hubbard models. We use these models to demonstrate how efficient mappings of these Hamiltonians can be constructed using a judicious choice of index ordering of the fermions. This development provides an alternative exact route to calculate the static and dynamical properties of fermionic systems and sets the stage to exploit the quantum-classical and semiclassical hierarchies to systematically derive methods offering a range of accuracies, thus enabling the study of problems where the fermionic degrees of freedom are coupled to complex anharmonic nuclear motion and spins which lie beyond the reach of most currently available methods.
| S-EPMC6113338 | biostudies-literature
Project description:Kraken is an ultrafast and highly accurate program for assigning taxonomic labels to metagenomic DNA sequences. Previous programs designed for this task have been relatively slow and computationally expensive, forcing researchers to use faster abundance estimation programs, which only classify small subsets of metagenomic data. Using exact alignment of k-mers, Kraken achieves classification accuracy comparable to the fastest BLAST program. In its fastest mode, Kraken classifies 100 base pair reads at a rate of over 4.1 million reads per minute, 909 times faster than Megablast and 11 times faster than the abundance estimation program MetaPhlAn. Kraken is available at http://ccb.jhu.edu/software/kraken/.
| S-EPMC4053813 | biostudies-other
Project description:Young drivers are a high-risk group for vehicle crashes due to inexperience in detecting an impending collision and are one group that may benefit from perceptual learning (PL) training. The present study assessed whether PL could be used to improve performance in collision detection. Ten college-aged subjects participated in the first experiment, which consisted of seven 1-hr sessions conducted on separate days. Thresholds at three observer/object speeds were measured prior to training using a two-alternative forced choice procedure during which they indicated whether an approaching object would result in a collision or noncollision event. Participants were then trained near threshold at one of these speeds for 5 days. After training, participants showed a significant reduction in the time needed to detect a collision at the trained speed. This improvement was also found to transfer to the higher observer speed condition. A second experiment was conducted to determine whether this improvement was due to training near threshold or whether this improvement was merely due to practice with the task. Training with stimuli well above threshold showed no significant improvement in performance, indicating that the improvement seen in the first experiment was not solely due to task practice.
| S-EPMC4525693 | biostudies-literature
Project description:BackgroundSolutions to stochastic Boolean models are usually estimated by Monte Carlo simulations, but as the state space of these models can be enormous, there is an inherent uncertainty about the accuracy of Monte Carlo estimates and whether simulations have reached all attractors. Moreover, these models have timescale parameters (transition rates) that the probability values of stationary solutions depend on in complex ways, raising the necessity of parameter sensitivity analysis. We address these two issues by an exact calculation method for this class of models.ResultsWe show that the stationary probability values of the attractors of stochastic (asynchronous) continuous time Boolean models can be exactly calculated. The calculation does not require Monte Carlo simulations, instead it uses graph theoretical and matrix calculation methods previously applied in the context of chemical kinetics. In this version of the asynchronous updating framework the states of a logical model define a continuous time Markov chain and for a given initial condition the stationary solution is fully defined by the right and left nullspace of the master equation's kinetic matrix. We use topological sorting of the state transition graph and the dependencies between the nullspaces and the kinetic matrix to derive the stationary solution without simulations. We apply this calculation to several published Boolean models to analyze the under-explored question of the effect of transition rates on the stationary solutions and show they can be sensitive to parameter changes. The analysis distinguishes processes robust or, alternatively, sensitive to parameter values, providing both methodological and biological insights.ConclusionUp to an intermediate size (the biggest model analyzed is 23 nodes) stochastic Boolean models can be efficiently solved by an exact matrix method, without using Monte Carlo simulations. Sensitivity analysis with respect to the model's timescale parameters often reveals a small subset of all parameters that primarily determine the stationary probability of attractor states.
| S-EPMC7291460 | biostudies-literature
Project description:In analysis of multi-component complex systems, such as neural systems, identifying groups of units that share similar functionality will aid understanding of the underlying structures of the system. To find such a grouping, it is useful to evaluate to what extent the units of the system are separable. Separability or inseparability can be evaluated by quantifying how much information would be lost if the system were partitioned into subsystems, and the interactions between the subsystems were hypothetically removed. A system of two independent subsystems are completely separable without any loss of information while a system of strongly interacted subsystems cannot be separated without a large loss of information. Among all the possible partitions of a system, the partition that minimizes the loss of information, called the Minimum Information Partition (MIP), can be considered as the optimal partition for characterizing the underlying structures of the system. Although the MIP would reveal novel characteristics of the neural system, an exhaustive search for the MIP is numerically intractable due to the combinatorial explosion of possible partitions. Here, we propose a computationally efficient search to precisely identify the MIP among all possible partitions by exploiting the submodularity of the measure of information loss, when the measure of information loss is submodular. Submodularity is a mathematical property of set functions which is analogous to convexity in continuous functions. Mutual information is one such submodular information loss function, and is a natural choice for measuring the degree of statistical dependence between paired sets of random variables. By using mutual information as a loss function, we show that the search for MIP can be performed in a practical order of computational time for a reasonably large system (N = 100 ∼ 1000). We also demonstrate that MIP search allows for the detection of underlying global structures in a network of nonlinear oscillators.
| S-EPMC6133274 | biostudies-literature
Project description:MotivationThe estimation of phylogenetic trees is a major part of many biological dataset analyses, but maximum likelihood approaches are NP-hard and Bayesian MCMC methods do not scale well to even moderate-sized datasets. Supertree methods, which are used to construct trees from trees computed on subsets, are critically important tools for enabling the statistical estimation of phylogenies for large and potentially heterogeneous datasets. Supertree estimation is itself NP-hard, and no current supertree method has sufficient accuracy and scalability to provide good accuracy on the large datasets that supertree methods were designed for, containing thousands of species and many subset trees.ResultsWe present FastRFS, a new method based on a dynamic programming method we have developed to find an exact solution to the Robinson-Foulds Supertree problem within a constrained search space. FastRFS has excellent accuracy in terms of criterion scores and topological accuracy of the resultant trees, substantially improving on competing methods on a large collection of biological and simulated data. In addition, FastRFS is extremely fast, finishing in minutes on even very large datasets, and in under an hour on a biological dataset with 2228 species.Availability and implementationFastRFS is available on github at https://github.com/pranjalv123/FastRFS.Contactwarnow@illinois.edu.Supplementary informationSupplementary data are available at Bioinformatics online.
| S-EPMC5870905 | biostudies-literature
Project description:Carbapenemase-producing organisms (CPOs) are Gram-negative bacteria that are typically resistant to most or all antibiotics and are responsible for a global pandemic of high mortality. Rapid, accurate detection of CPOs and the classification of their carbapenemases are valuable tools for reducing the mortality of the CPO-associated infections, preventing the spread of CPOs, and optimizing use of new ?-lactamase inhibitor combinations such as ceftazidime/avibactam, meropenem/vaborbactam and imipenem/relebactam. The current study evaluated the performance of CPO Complete, a novel, manual, phenotypic carbapenemase detection and classification test. The test was evaluated for sensitivity and specificity against 262 CPO isolates of Enterobacteriaceae, Pseudomonas aeruginosa and Acinetobacter baumannii and 67 non-CPO isolates. It was also evaluated for carbapenemase classification accuracy against 205 CPOs that produced a single carbapenemase class. The test exhibited 100% sensitivity 98.5% specificity for carbapenemase detection within 90 minutes and detected 74.1% of carbapenemases within 10 minutes. In the classification evaluation, 99.0% of carbapenemases were correctly classified for isolates that produced a single carbapenemase. The test is technically simple and has potential for adaptation to automated instruments. With lyophilized kit storage at temperatures up to 38°C, the CPO Complete test has the potential to provide rapid, accurate carbapenemase detection and classification in both limited resource and technologically advanced laboratories.
| S-EPMC6905549 | biostudies-literature
Project description:In this study nanopore sequencing was applied to obtain sparse DNA methylation profiles from pediatric CNS tumor samples. A neural network was used to classify the tumor based on the obtained methylation profile.
2023-08-08 | GSE237874 | GEO
Project description:Recently, with the increased number of robots entering numerous manufacturing fields, a considerable wealth of literature has appeared on the theme of physical human-robot interaction using data from proprioceptive sensors (motor or/and load side encoders). Most of the studies have then the accurate dynamic model of a robot for granted. In practice, however, model identification and observer design proceeds collision detection. To the best of our knowledge, no previous study has systematically investigated each aspect underlying physical human-robot interaction and the relationship between those aspects. In this paper, we bridge this gap by first reviewing the literature on model identification, disturbance estimation and collision detection, and discussing the relationship between the three, then by examining the practical sides of model-based collision detection on a case study conducted on UR10e. We show that the model identification step is critical for accurate collision detection, while the choice of the observer should be mostly based on computation time and the simplicity and flexibility of tuning. It is hoped that this study can serve as a roadmap to equip industrial robots with basic physical human-robot interaction capabilities.
| S-EPMC7805958 | biostudies-literature
Project description:For testing with paired data (eg, twins randomized between two treatments), a simple test is the sign test, where we test if the distribution of the sign of the differences in responses between the two treatments within pairs is more often positive (favoring one treatment) or negative (favoring the other). When the responses are binary, this reduces to a McNemar-type test, and the calculations are the same. Although it is easy to calculate an exact P-value by conditioning on the total number of discordant pairs, the accompanying confidence interval on a parameter of interest (proportion positive minus proportion negative) is not straightforward. Effect estimates and confidence intervals are important for interpretation because it is possible that the treatment helps a very small proportion of the population yet gives a highly significant effect. We construct a confidence interval that is compatible with an exact sign test, meaning the 100 (1-α)% interval excludes the null hypothesis of equality of proportions if and only if the associated exact sign test rejects at level α . We conjecture that the proposed confidence intervals guarantee nominal coverage, and we support that conjecture with extensive numerical calculations, but we have no mathematical proof to show guaranteed coverage. We have written and made available the function mcnemarExactDP in the exact2x2 R package and the function signTest in the asht R package to perform the methods described in this article.
| S-EPMC9447366 | biostudies-literature