Maximizing gerrymandering through ising model optimization.
Ontology highlight
ABSTRACT:
SUBMITTER: Okamoto Y
PROVIDER: S-EPMC8655093 | biostudies-literature |
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:This paper provides a new (second) way, which is completely different from Shor's algorithm, to show the optimistic potential of a D-Wave quantum computer for deciphering RSA and successfully factoring all integers within 10000. Our method significantly reduced the local field coefficient [Formula: see text] and coupling term coefficient [Formula: see text] by more than 33% and 26%, respectively, of those of Ising model, which can further improve the stability of qubit chains and improve the upper bound of integer factorization. In addition, our results obtained the best index (20-bit integer (1028171)) of quantum computing for deciphering RSA via the quantum computing software environment provided by D-Wave. Furthermore, Shor's algorithm requires approximately 40 qubits to factor the integer 1028171, which is far beyond the capacity of universal quantum computers. Thus, post quantum cryptography should further consider the potential of the D-Wave quantum computer for deciphering the RSA cryptosystem in future.
| S-EPMC7188840 | biostudies-literature
Project description:Genomic selection (GS) has become an increasingly popular tool in plant breeding programs, propelled by declining genotyping costs, an increase in computational power, and rediscovery of the best linear unbiased prediction methodology over the past two decades. This development has led to an accumulation of extensive historical datasets with genotypic and phenotypic information, triggering the question of how to best utilize these datasets. Here, we investigate whether all available data or a subset should be used to calibrate GS models for across-year predictions in a 7-year dataset of a commercial hybrid sunflower breeding program. We employed a multi-objective optimization approach to determine the ideal years to include in the training set (TRS). Next, for a given combination of TRS years, we further optimized the TRS size and its genetic composition. We developed the Min_GRM size optimization method which consistently found the optimal TRS size, reducing dimensionality by 20% with an approximately 1% loss in predictive ability. Additionally, the Tails_GEGVs algorithm displayed potential, outperforming the use of all data by using just 60% of it for grain yield, a high-complexity, low-heritability trait. Moreover, maximizing the genetic diversity of the TRS resulted in a consistent predictive ability across the entire range of genotypic values in the test set. Interestingly, the Tails_GEGVs algorithm, due to its ability to leverage heterogeneity, enhanced predictive performance for key hybrids with extreme genotypic values. Our study provides new insights into the optimal utilization of historical data in plant breeding programs, resulting in improved GS model predictive ability.
| S-EPMC10943787 | biostudies-literature
Project description:A prominent approach to solving combinatorial optimization problems on parallel hardware is Ising machines, i.e., hardware implementations of networks of interacting binary spin variables. Most Ising machines leverage second-order interactions although important classes of optimization problems, such as satisfiability problems, map more seamlessly to Ising networks with higher-order interactions. Here, we demonstrate that higher-order Ising machines can solve satisfiability problems more resource-efficiently in terms of the number of spin variables and their connections when compared to traditional second-order Ising machines. Further, our results show on a benchmark dataset of Boolean k-satisfiability problems that higher-order Ising machines implemented with coupled oscillators rapidly find solutions that are better than second-order Ising machines, thus, improving the current state-of-the-art for Ising machines.
| S-EPMC10533504 | biostudies-literature
Project description:BackgroundFor years, US medical schools have relied on community-based, private clinicians to educate medical students. There has been a steady decline in the number of physicians willing to take on medical students in their clinical practices. Recent issues related to the pandemic raise questions about how many patients students should see to have a meaningful clinical experience.MethodsAs part of a 16-week longitudinal clinical experience, medical students spend 2 days each week in a family medicine or internal medicine clinic. As repetition enhances learning, maximizing the number of patients students see is important. Using a mixed integer linear program, we sought to determine the optimal schedule that maximizes the number of patients whom students see during a rotation. Patient visits were collected from January to April 2018 for clinics used by the medical school. By maximizing the minimum number of patients per learner over all non-empty day-clinic combinations, we deliver equitable rotation plans based on our assumptions.ResultsFor this pilot study, multiple experiments were performed with different numbers of students assigned to clinics. Each experiment also generated a weekly rotation plan for a given student. Based on this optimization model, the minimum number of patients per student over 16 weeks was 87 (3 patients per day) and actually increased the number of students who could be assigned to one of the clinics from 1 student per rotation to 8 students.ConclusionsThe mixed integer linear program assigned more students to clinics that have more total visits in order to achieve the optimal and fairest learning quality. In addition, by conducting various experiments on different numbers of students, we observed that we were able to allocate more students without affecting the number of patients students see.
| S-EPMC8741226 | biostudies-literature
Project description:Quantum computers and simulators may offer significant advantages over their classical counterparts, providing insights into quantum many-body systems and possibly improving performance for solving exponentially hard problems, such as optimization and satisfiability. Here, we report the implementation of a low-depth Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum simulator. We estimate the ground-state energy of the Transverse Field Ising Model with long-range interactions with tunable range, and we optimize the corresponding combinatorial classical problem by sampling the QAOA output with high-fidelity, single-shot, individual qubit measurements. We execute the algorithm with both an exhaustive search and closed-loop optimization of the variational parameters, approximating the ground-state energy with up to 40 trapped-ion qubits. We benchmark the experiment with bootstrapping heuristic methods scaling polynomially with the system size. We observe, in agreement with numerics, that the QAOA performance does not degrade significantly as we scale up the system size and that the runtime is approximately independent from the number of qubits. We finally give a comprehensive analysis of the errors occurring in our system, a crucial step in the path forward toward the application of the QAOA to more general problem instances.
| S-EPMC7568299 | biostudies-literature
Project description:There has been a lot of work fitting Ising models to multivariate binary data in order to understand the conditional dependency relationships between the variables. However, additional covariates are frequently recorded together with the binary data, and may influence the dependence relationships. Motivated by such a dataset on genomic instability collected from tumor samples of several types, we propose a sparse covariate dependent Ising model to study both the conditional dependency within the binary data and its relationship with the additional covariates. This results in subject-specific Ising models, where the subject's covariates influence the strength of association between the genes. As in all exploratory data analysis, interpretability of results is important, and we use ?1 penalties to induce sparsity in the fitted graphs and in the number of selected covariates. Two algorithms to fit the model are proposed and compared on a set of simulated data, and asymptotic results are established. The results on the tumor dataset and their biological significance are discussed in detail.
| S-EPMC4425428 | biostudies-literature
Project description:The bulk and surface refractive index sensitivities of LSPR biosensors, consisting of coupled plasmonic nanosphere and nano-ellipsoid dimers, were investigated by simulations using the boundary element method (BEM). The enhancement factor, defined as the ratio of plasmon extinction peak shift of multi-particle and single-particle arrangements caused by changes in the refractive index of the environment, was used to quantify the effect of coupling on the increased sensitivity of the dimers. The bulk refractive index sensitivity (RIS) was obtained by changing the dielectric medium surrounding the nanoparticles, while the surface sensitivity was modeled by depositing dielectric layers on the nanoparticle in an increasing thickness. The results show that by optimizing the interparticle gaps for a given layer thickness, up to ~80% of the optical response range of the nanoparticles can be utilized by confining the plasmon field between the particles, which translates into an enhancement of ~3-4 times compared to uncoupled, single particles with the same shape and size. The results also show that in these cases, the surface sensitivity enhancement is significantly higher than the bulk RI sensitivity enhancement (e.g., 3.2 times vs. 1.8 times for nanospheres with a 70 nm diameter), and thus the sensors' response for molecular interactions is higher than their RIS would indicate. These results underline the importance of plasmonic coupling in the optimization of nanoparticle arrangements for biosensor applications. The interparticle gap should be tailored with respect to the size of the used receptor/target molecules to maximize the molecular sensitivity, and the presented methodology can effectively aid the optimization of fabrication technologies.
| S-EPMC8699530 | biostudies-literature
Project description:Long-range synchrony from short-range interactions is a familiar pattern in biological and physical systems, many of which share a common set of 'universal' properties at the point of synchronization. Common biological systems of coupled oscillators have been shown to be members of the Ising universality class, meaning that the very simple Ising model replicates certain spatial statistics of these systems at stationarity. This observation is useful because it reveals which aspects of spatial pattern arise independently of the details governing local dynamics, resulting in both deeper understanding of and a simpler baseline model for biological synchrony. However, in many situations a system's dynamics are of greater interest than their static spatial properties. Here, we ask whether a dynamical Ising model can replicate universal and non-universal features of ecological systems, using noisy coupled metapopulation models with two-cycle dynamics as a case study. The standard Ising model makes unrealistic dynamical predictions, but the Ising model with memory corrects this by using an additional parameter to reflect the tendency for local dynamics to maintain their phase of oscillation. By fitting the two parameters of the Ising model with memory to simulated ecological dynamics, we assess the correspondence between the Ising and ecological models in several of their features (location of the critical boundary in parameter space between synchronous and asynchronous dynamics, probability of local phase changes and ability to predict future dynamics). We find that the Ising model with memory is reasonably good at representing these properties of ecological metapopulations. The correspondence between these models creates the potential for the simple and well-known Ising class of models to become a valuable tool for understanding complex biological systems.
| S-EPMC7653388 | biostudies-literature
Project description:Interdisciplinary communication is becoming a crucial component of the present scientific environment. Theoretical models developed in diverse disciplines often may be successfully employed in solving seemingly unrelated problems that can be reduced to similar mathematical formulation. The Ising model has been proposed in statistical physics as a simplified model for analysis of magnetic interactions and structures of ferromagnetic substances. Here, we present an application of the one-dimensional, linear Ising model to affected-sib-pair (ASP) analysis in genetics. By analyzing simulated genetics data, we show that the simplified Ising model with only nearest-neighbor interactions between genetic markers has statistical properties comparable to much more complex algorithms from genetics analysis, such as those implemented in the Allegro and Mapmaker-Sibs programs. We also adapt the model to include epistatic interactions and to demonstrate its usefulness in detecting modifier loci with weak individual genetic contributions. A reanalysis of data on type 1 diabetes detects several susceptibility loci not previously found by other methods of analysis.
| S-EPMC1226070 | biostudies-literature
Project description:In the polyomino puzzle, the aim is to fill a finite space using several polyomino pieces with no overlaps or blanks. Because it is an NP-complete combinatorial optimization problem, various probabilistic and approximated approaches have been applied to find solutions. Several previous studies embedded the polyomino puzzle in a QUBO problem, where the original objective function and constraints are transformed into the Hamiltonian function of the simulated Ising model. A solution to the puzzle is obtained by searching for a ground state of Hamiltonian by simulating the dynamics of the multiple-spin system. However, previous methods could solve only tiny polyomino puzzles considering a few combinations because their Hamiltonian designs were not efficient. We propose an improved Hamiltonian design that introduces new constraints and guiding terms to weakly encourage favorable spins and pairs in the early stages of computation. The proposed model solves the pentomino puzzle represented by approximately 2000 spins with >90% probability. Additionally, we extended the method to a generalized problem where each polyomino piece could be used zero or more times and solved it with approximately 100% probability. The proposed method also appeared to be effective for the 3D polycube puzzle, which is similar to applications in fragment-based drug discovery.
| S-EPMC8947422 | biostudies-literature