Parameterized Complexity of
Ontology highlight
ABSTRACT:
SUBMITTER: Gasieniec L
PROVIDER: S-EPMC7254919 | biostudies-literature | 2020 Apr
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:In electron diffraction, thermal atomic motion produces incoherent scattering over a relatively wide angular range, which appears as a diffuse background that is usually subtracted from measurements of Bragg spot intensities in structure solution methods. The transfer of electron flux from Bragg spots to diffuse scatter is modelled using complex scattering factors f + if' in the Bloch wave methodology. In a two-beam Einstein model the imaginary `absorptive' scattering factor f' can be obtained by the evaluation of an integral containing f over all possible scattering angles. While more sophisticated models of diffuse scatter are widely used in the electron microscopy community, it is argued in this paper that this simple model is appropriate for current structure solution and refinement methods. The two-beam model is a straightforward numerical calculation, but even this simplistic approach can become time consuming for simulations of materials with large numbers of atoms in the unit cell and/or many incident beam orientations. Here, a parameterized form of f' is provided for 103 elements as neutral, spherical atoms that reduces calculation time considerably.
| S-EPMC10913675 | biostudies-literature
Project description:MotivationSequencing long reads presents novel challenges to mapping. One such challenge is low sequence similarity between the reads and the reference, due to high sequencing error and mutation rates. This occurs, e.g., in a cancer tumor, or due to differences between strains of viruses or bacteria. A key idea in mapping algorithms is to sketch sequences with their minimizers. Recently, syncmers were introduced as an alternative sketching method that is more robust to mutations and sequencing errors.ResultsWe introduce parameterized syncmer schemes (PSS), a generalization of syncmers, and provide a theoretical analysis for multi-parameter schemes. By combining PSS with downsampling or minimizers we can achieve any desired compression and window guarantee. We implemented the use of PSS in the popular minimap2 and Winnowmap2 mappers. In tests on simulated and real long-read data from a variety of genomes, the PSS-based algorithms, with scheme parameters selected on the basis of our theoretical analysis, reduced unmapped reads by 20-60% at high compression while usually using less memory. The advantage was more pronounced at low sequence identity. At sequence identity of 75% and medium compression, PSS-minimap had only 37% as many unmapped reads, and 8% fewer of the reads that did map were incorrectly mapped. Even at lower compression and error rates, PSS-based mapping mapped more reads than the original minimizer-based mappers as well as mappers using the original syncmer schemes. We conclude that using PSS can improve mapping of long reads in a wide range of settings.
| S-EPMC9645665 | biostudies-literature
Project description:The geometric designs of MEMS devices can profoundly impact their physical properties and eventual performances. However, it is challenging for researchers to rationally consider a large number of possible designs, as it would be very time- and resource-consuming to study all these cases using numerical simulation. In this paper, we report the use of deep learning techniques to accelerate the MEMS design cycle by quickly and accurately predicting the physical properties of numerous design candidates with vastly different geometric features. Design candidates are represented in a nonparameterized, topologically unconstrained form using pixelated black-and-white images. After sufficient training, a deep neural network can quickly calculate the physical properties of interest with good accuracy without using conventional numerical tools such as finite element analysis. As an example, we apply our deep learning approach in the prediction of the modal frequency and quality factor of disk-shaped microscale resonators. With reasonable training, our deep learning neural network becomes a high-speed, high-accuracy calculator: it can identify the flexural mode frequency and the quality factor 4.6 × 103 times and 2.6 × 104 times faster, respectively, than conventional numerical simulation packages, with good accuracies of 98.8 ± 1.6% and 96.8 ± 3.1%, respectively. When simultaneously predicting the frequency and the quality factor, up to ~96.0% of the total computation time can be saved during the design process. The proposed technique can rapidly screen over thousands of design candidates and promotes experience-free and data-driven MEMS structural designs.
| S-EPMC9424241 | biostudies-literature
Project description:In this paper, we leverage over-parameterization to design regularization-free algorithms for the high-dimensional single index model and provide theoretical guarantees for the induced implicit regularization phenomenon. Specifically, we study both vector and matrix single index models where the link function is nonlinear and unknown, the signal parameter is either a sparse vector or a low-rank symmetric matrix, and the response variable can be heavy-tailed. To gain a better understanding of the role played by implicit regularization without excess technicality, we assume that the distribution of the covariates is known a priori. For both the vector and matrix settings, we construct an over-parameterized least-squares loss function by employing the score function transform and a robust truncation step designed specifically for heavy-tailed data. We propose to estimate the true parameter by applying regularization-free gradient descent to the loss function. When the initialization is close to the origin and the stepsize is sufficiently small, we prove that the obtained solution achieves minimax optimal statistical rates of convergence in both the vector and matrix cases. In addition, our experimental results support our theoretical findings and also demonstrate that our methods empirically outperform classical methods with explicit regularization in terms of both ℓ2-statistical rate and variable selection consistency.
| S-EPMC10977662 | biostudies-literature
Project description:In this paper, we discuss parameterized algorithms for variants of the partial vertex cover problem. Recall that in the classical vertex cover problem (VC), we are given a graph
| S-EPMC7254907 | biostudies-literature
Project description:PurposeTo develop a tool to produce accurate, well-validated x-ray spectra for standalone use or for use in an open-access x-ray/CT simulation tool. Spectrum models will be developed for tube voltages in the range of 80 kVp through 140 kVp and for anode takeoff angles in the range of 5° to 9°.MethodsSpectra were initialized based on physics models, then refined using empirical measurements, as follows. A new spectrum-parameterization method was developed, including 13 spline knots to represent the bremsstrahlung component and 4 values to represent characteristic lines. Initial spectra at 80, 100, 120, and 140 kVp and at takeoff angles from 5° to 9° were produced using physics-based spectrum estimation tools XSPECT and SpekPy. Empirical experiments were systematically designed with careful selection of attenuator materials and thicknesses, and by reducing measurement contamination from scatter to <1%. Measurements were made on a 64-row CT scanner using the scanner's detector and using multiple layers of polymethylmethacrylate (PMMA), aluminum, titanium, tin, and neodymium. Measurements were made at 80, 100, 120, and 140 kVp and covering the entire 64-row detector (takeoff angles from 5° to 9°); a total of 6,144 unique measurements were made. After accounting for the detector's energy response, parameterized representations of the initial spectra were refined for best agreement with measurements using two proposed optimization schemes: based on modulation and based on gradient descent. X-ray transmission errors were computed for measurements vs calculations using the nonoptimized and optimized spectra. Half-value, tenth-value, and hundredth-value layers for PMMA, Al, and Ti were calculated.ResultsSpectra before and after parameterization were in excellent agreement (e.g., R2 values of 0.995 and 0.997). Empirical measurements produced smoothly varying curves with x-ray transmission covering a range of up to 3.5 orders of magnitude. Spectra from the two optimization schemes, compared with the unoptimized physic-based spectra, each improved agreement with measurements by twofold through tenfold, for both postlog transmission data and for fractional value layers.ConclusionThe resulting well-validated spectra are appropriate for use in the open-access x-ray/CT simulator under development, the x-ray-based Cancer Imaging Toolkit (XCIST), or for standalone use. These spectra can be readily interpolated to produce spectra at arbitrary kVps over the range of 80 to 140 kVp and arbitrary takeoff angles over the range of 5° to 9°. Furthermore, interpolated spectra over these ranges can be obtained by applying the standalone Matlab function available at https://github.com/xcist/documentation/blob/master/XCISTspectrum.m.
| S-EPMC8140990 | biostudies-literature
Project description:For modeling count data, the Conway-Maxwell-Poisson (CMP) distribution is a popular generalization of the Poisson distribution due to its ability to characterize data over- or under-dispersion. While the classic parameterization of the CMP has been well-studied, its main drawback is that it is does not directly model the mean of the counts. This is mitigated by using a mean-parameterized version of the CMP distribution. In this work, we are concerned with the setting where count data may be comprised of subpopulations, each possibly having varying degrees of data dispersion. Thus, we propose a finite mixture of mean-parameterized CMP distributions. An EM algorithm is constructed to perform maximum likelihood estimation of the model, while bootstrapping is employed to obtain estimated standard errors. A simulation study is used to demonstrate the flexibility of the proposed mixture model relative to mixtures of Poissons and mixtures of negative binomials. An analysis of dog mortality data is presented.Supplementary informationThe online version contains supplementary material available at 10.1007/s00362-023-01452-x.
| S-EPMC10197059 | biostudies-literature
Project description:Learning from demonstration (LfD) enables a robot to emulate natural human movement instead of merely executing preprogrammed behaviors. This article presents a hierarchical LfD structure of task-parameterized models for object movement tasks, which are ubiquitous in everyday life and could benefit from robotic support. Our approach uses the task-parameterized Gaussian mixture model (TP-GMM) algorithm to encode sets of demonstrations in separate models that each correspond to a different task situation. The robot then maximizes its expected performance in a new situation by either selecting a good existing model or requesting new demonstrations. Compared to a standard implementation that encodes all demonstrations together for all test situations, the proposed approach offers four advantages. First, a simply defined distance function can be used to estimate test performance by calculating the similarity between a test situation and the existing models. Second, the proposed approach can improve generalization, e.g., better satisfying the demonstrated task constraints and speeding up task execution. Third, because the hierarchical structure encodes each demonstrated situation individually, a wider range of task situations can be modeled in the same framework without deteriorating performance. Last, adding or removing demonstrations incurs low computational load, and thus, the robot's skill library can be built incrementally. We first instantiate the proposed approach in a simulated task to validate these advantages. We then show that the advantages transfer to real hardware for a task where naive participants collaborated with a Willow Garage PR2 robot to move a handheld object. For most tested scenarios, our hierarchical method achieved significantly better task performance and subjective ratings than both a passive model with only gravity compensation and a single TP-GMM encoding all demonstrations.
| S-EPMC6914968 | biostudies-literature
Project description:Peripheral nerve stimulation is an effective treatment for various neurological disorders. The method of activation and stimulation parameters used impact the efficacy of the therapy, which emphasizes the need for tools to model this behavior. Computational modeling of nerve stimulation has proven to be a useful tool for estimating stimulation thresholds, optimizing electrode design, and exploring previously untested stimulation methods. Despite their utility, these tools require access to and familiarity with several pieces of specialized software. A simpler, streamlined process would increase accessibility significantly. We developed an open-source, parameterized model with a simple online user interface that allows user to adjust up to 36 different parameters (https://nervestimlab.utdallas.edu). The model accurately predicts fiber activation thresholds for nerve and electrode combinations reported in literature. Additionally, it replicates characteristic differences between stimulation methods, such as lower thresholds with monopolar stimulation as compared to tripolar stimulation. The model predicted that the difference in threshold between monophasic and biphasic waveforms, a well-characterized phenomenon, is not present during stimulation with bipolar electrodes.In vivotesting on the rat sciatic nerve validated this prediction, which has not been previously reported. The accuracy of the model when compared to previous experiments, as well as the ease of use and accessibility to generate testable hypotheses, indicate that this software may represent a useful tool for a variety of nerve stimulation applications.
| S-EPMC9533340 | biostudies-literature
Project description:We consider parameterized concurrent systems consisting of a finite but unknown number of components, obtained by replicating a given set of finite state automata.
| S-EPMC7439742 | biostudies-literature