Browse
Submit Data
Databases
API
Help

Dataset Information

0 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

A continuous-time MaxSAT solver with high analog performance.

ABSTRACT: Many real-life optimization problems can be formulated in Boolean logic as MaxSAT, a class of problems where the task is finding Boolean assignments to variables satisfying the maximum number of logical constraints. Since MaxSAT is NP-hard, no algorithm is known to efficiently solve these problems. Here we present a continuous-time analog solver for MaxSAT and show that the scaling of the escape rate, an invariant of the solver's dynamics, can predict the maximum number of satisfiable constraints, often well before finding the optimal assignment. Simulating the solver, we illustrate its performance on MaxSAT competition problems, then apply it to two-color Ramsey number R(m, m) problems. Although it finds colorings without monochromatic 5-cliques of complete graphs on N???42 vertices, the best coloring for N?=?43 has two monochromatic 5-cliques, supporting the conjecture that R(5, 5)?=?43. This approach shows the potential of continuous-time analog dynamical systems as algorithms for discrete optimization.

SUBMITTER: Molnar B

PROVIDER: S-EPMC6242876 | biostudies-other | 2018 Nov

REPOSITORIES: biostudies-other

ACCESS DATA

Json Xml

Publications

A continuous-time MaxSAT solver with high analog performance.

Molnár Botond B Molnár Ferenc F Varga Melinda M Toroczkai Zoltán Z Ercsey-Ravasz Mária M

Nature communications 20181119 1

Many real-life optimization problems can be formulated in Boolean logic as MaxSAT, a class of problems where the task is finding Boolean assignments to variables satisfying the maximum number of logical constraints. Since MaxSAT is NP-hard, no algorithm is known to efficiently solve these problems. Here we present a continuous-time analog solver for MaxSAT and show that the scaling of the escape rate, an invariant of the solver's dynamics, can predict the maximum number of satisfiable constraint ...[more]

PMID: 30451849

Similar Datasets

Enhancing high-fidelity nonlinear solver with reduced order model.

Project description:We propose the use of reduced order modeling (ROM) to reduce the computational cost and improve the convergence rate of nonlinear solvers of full order models (FOM) for solving partial differential equations. In this study, a novel ROM-assisted approach is developed to improve the computational efficiency of FOM nonlinear solvers by using ROM's prediction as an initial guess. We hypothesize that the nonlinear solver will take fewer steps to the converged solutions with an initial guess that is closer to the real solutions. To evaluate our approach, four physical problems with varying degrees of nonlinearity in flow and mechanics have been tested: Richards' equation of water flow in heterogeneous porous media, a contact problem in a hyperelastic material, two-phase flow in layered porous media, and fracture propagation in a homogeneous material. Overall, our approach maintains the FOM's accuracy while speeding up nonlinear solver by 18-73% (through suitable ROM-assisted FOMs). More importantly, the proximity of ROM's prediction to the solution space leads to the improved convergence of FOMs that would have otherwise diverged with default initial guesses. We demonstrate that the ROM's accuracy can impact the computational efficiency with more accurate ROM solutions, resulting in a better cost reduction. We also illustrate that this approach could be used in many FOM discretizations (e.g., finite volume, finite element, or a combination of those). Since our ROMs are data-driven and non-intrusive, the proposed procedure can easily lend itself to any nonlinear physics-based problem.

| S-EPMC9684583 | biostudies-literature

The Genome Solver Project: Faculty Training and Student Performance Gains in Bioinformatics.

Project description:Bioinformatics brings together biology, mathematics, statistics, and computer science to analyze biological sequence information. Anyone with a computer, access to the Internet, and basic training in this field can contribute to genomics research. Yet many biology faculty feel they lack training in the use of bioinformatics tools and therefore include little bioinformatics content in their courses. To overcome this challenge, the Genome Solver Project was created to empower undergraduate faculty by offering training and resources for creating hands-on bioinformatics course materials. In this study, we show the results of one survey completed directly after the workshop and a further follow-up survey to gain insight into the impact the workshop had on faculty willingness to include bioinformatics content in their courses and what challenges they still faced. We also measured student performance at five different institutions using a 20-question multiple-choice quiz delivered before and after bioinformatics instruction. Data collected from 640 students at these five schools demonstrated student performance increased, suggesting that bioinformatics training workshops can be an effective means of encouraging faculty to engage in bioinformatics instruction and positively influence student learning.

| S-EPMC6508904 | biostudies-literature

Communication: An exact short-time solver for the time-dependent Schrodinger equation.

Project description:The short-time integrator for propagating the time-dependent Schrödinger equation, which is exact to machine's round off accuracy when the Hamiltonian of the system is time-independent, was applied to solve dynamics processes. This integrator has the old Cayley's form [i.e., the Padé (1,1) approximation], but is implemented in a spectrally transformed Hamiltonian which was first introduced by Chen and Guo. Two examples are presented for illustration, including calculations of the collision energy-dependent probability passing over a barrier, and interaction process between pulse laser and the I(2) diatomic molecule.

| S-EPMC3045215 | biostudies-other

Continuous production of ultratough semiconducting polymer fibers with high electronic performance.

Project description:Conjugated polymers have demonstrated promising optoelectronic properties, but their brittleness and poor mechanical characteristics have hindered their fabrication into durable fibers and textiles. Here, we report a universal approach to continuously producing highly strong, ultratough conjugated polymer fibers using a flow-enhanced crystallization (FLEX) method. These fibers exhibit one order of magnitude higher tensile strength (>200 megapascals) and toughness (>80 megajoules per cubic meter) than traditional semiconducting polymer fibers and films, outperforming many synthetic fibers, ready for scalable production. These fibers also exhibit unique strain-enhanced electronic properties and exceptional performance when used as stretchable conductors, thermoelectrics, transistors, and sensors. This work not only highlights the influence of fluid mechanical effects on the crystallization and mechanical properties of conjugated polymers but also opens up exciting possibilities for integrating these functional fibers into wearable electronics.

| S-EPMC10990280 | biostudies-literature

Performance of a new real-time continuous glucose monitoring system: A multicenter pilot study.

Project description:Aims/introductionThe present study aimed to investigate the performance of a new real-time continuous glucose monitoring system.Materials and methodsInterstitial glucose levels were monitored for 7 days in 63 patients with type 1 or type 2 diabetes using the Medtrum A6 TouchCare® CGM System. Venous blood was collected on a randomized day of the wear period. Plasma glucose levels were measured as reference values.ResultsAmong 1,678 paired sensor-reference values, 90.5% (95% confidence interval 89.1-91.9%) were within ±20%/20 mg/dL of the reference values, with a mean absolute relative difference of 9.1 ± 8.7% (95% CI: 8.9-9.2%). The percentages of paired sensor-reference values falling within zone A and B of the Clarke error grid analysis (EGA) and the type 1 diabetes consensus EGA were 99.1 and 99.8%. Continuous EGA showed that the percentages of accurate readings, benign errors, and erroneous readings were 89.9, 6.3 and 3.8%, respectively. Surveillance EGA showed that 90.6, 9.2, and 0.2% of sensor-reference values with no, slight and lower moderate risk, respectively. The mean absolute relative difference was 16.6, and 96.0% of the sensor values fell within zones A and B of the consensus EGA for hypoglycemia. More than 85% of sensor values were within ±20%/20 mg/dL of reference values, the mean absolute relative difference was <11, and >99.5% of the sensor values fell in zones A and B of the consensus EGA.ConclusionsThe Medtrum real-time continuous glucose monitoring system was numerically and clinically accurate over a large glucose range across 7 days of wear.

| S-EPMC5835467 | biostudies-literature

High-performance time-resolved fluorescence by direct waveform recording.

Project description:We describe a high-performance time-resolved fluorescence (HPTRF) spectrometer that dramatically increases the rate at which precise and accurate subnanosecond-resolved fluorescence emission waveforms can be acquired in response to pulsed excitation. The key features of this instrument are an intense (1 μJ/pulse), high-repetition rate (10 kHz), and short (1 ns full width at half maximum) laser excitation source and a transient digitizer (0.125 ns per time point) that records a complete and accurate fluorescence decay curve for every laser pulse. For a typical fluorescent sample containing a few nanomoles of dye, a waveform with a signal/noise of about 100 can be acquired in response to a single laser pulse every 0.1 ms, at least 10(5) times faster than the conventional method of time-correlated single photon counting, with equal accuracy and precision in lifetime determination for lifetimes as short as 100 ps. Using standard single-lifetime samples, the detected signals are extremely reproducible, with waveform precision and linearity to within 1% error for single-pulse experiments. Waveforms acquired in 0.1 s (1000 pulses) with the HPTRF instrument were of sufficient precision to analyze two samples having different lifetimes, resolving minor components with high accuracy with respect to both lifetime and mole fraction. The instrument makes possible a new class of high-throughput time-resolved fluorescence experiments that should be especially powerful for biological applications, including transient kinetics, multidimensional fluorescence, and microplate formats.

| S-EPMC2980540 | biostudies-other

The fast continuous wavelet transformation (fCWT) for real-time, high-quality, noise-resistant time-frequency analysis.

Project description:The spectral analysis of signals is currently either dominated by the speed-accuracy trade-off or ignores a signal's often non-stationary character. Here we introduce an open-source algorithm to calculate the fast continuous wavelet transform (fCWT). The parallel environment of fCWT separates scale-independent and scale-dependent operations, while utilizing optimized fast Fourier transforms that exploit downsampled wavelets. fCWT is benchmarked for speed against eight competitive algorithms, tested on noise resistance and validated on synthetic electroencephalography and in vivo extracellular local field potential data. fCWT is shown to have the accuracy of CWT, to have 100 times higher spectral resolution than algorithms equal in speed, to be 122 times and 34 times faster than the reference and fastest state-of-the-art implementations and we demonstrate its real-time performance, as confirmed by the real-time analysis ratio. fCWT provides an improved balance between speed and accuracy, which enables real-time, wide-band, high-quality, time-frequency analysis of non-stationary noisy signals.

| S-EPMC10766549 | biostudies-literature

Low-voltage high-performance flexible digital and analog circuits based on ultrahigh-purity semiconducting carbon nanotubes.

Project description:Carbon nanotube (CNT) thin-film transistor (TFT) is a promising candidate for flexible and wearable electronics. However, it usually suffers from low semiconducting tube purity, low device yield, and the mismatch between p- and n-type TFTs. Here, we report low-voltage and high-performance digital and analog CNT TFT circuits based on high-yield (19.9%) and ultrahigh purity (99.997%) polymer-sorted semiconducting CNTs. Using high-uniformity deposition and pseudo-CMOS design, we demonstrated CNT TFTs with good uniformity and high performance at low operation voltage of 3 V. We tested forty-four 2-µm channel 5-stage ring oscillators on the same flexible substrate (1,056 TFTs). All worked as expected with gate delays of 42.7 ± 13.1 ns. With these high-performance TFTs, we demonstrated 8-stage shift registers running at 50 kHz and the first tunable-gain amplifier with 1,000 gain at 20 kHz. These results show great potentials of using solution-processed CNT TFTs for large-scale flexible electronics.

| S-EPMC6517392 | biostudies-literature

Performance of a Factory-Calibrated Real-Time Continuous Glucose Monitoring System Utilizing an Automated Sensor Applicator.

Project description:BackgroundThis study assessed the accuracy of a factory-calibrated 10-day real-time continuous glucose monitoring (CGM) system (G6), which includes an automated sensor applicator.MethodsSeventy-six participants with insulin-treated diabetes were enrolled at four U.S. sites as part of a larger study of G6 system performance. In-clinic visits for frequent comparative blood glucose measurements using a reference instrument (YSI) were conducted on days 1, 4-5, 7, and/or 10 of system use. Accuracy evaluation included the proportion of CGM values that were within ±20% of YSI reference value for glucose levels >100 mg/dL and ±20 mg/dL for YSI glucose levels ≤100 mg/dL (%20/20), the analogous %15/15 and %30/30, and the mean absolute relative difference (MARD) between temporally matched CGM and YSI values. Participants calibrated the systems once daily. Raw sensor data were reprocessed using assigned sensor codes and a factory-calibration algorithm.ResultsReprocessed data from 62 participants (25 adults and 37 children and adolescents of ages 6-17 years; 3532 YSI-CGM pairs) were analyzed. The G6 system's overall %20/20 was 93.9% (adults, 92.5%; children and adolescents, 96.2%), its %15/15 was 83.3% (adults, 78.3%; children and adolescents, 91.1%), and its MARD was 9.0% (adults, 9.8%; children and adolescents, 7.7%). Overall day-1 %20/20 accuracy was 92.2%, %15/15 was 81.5%, and MARD was 9.3%. Accuracy was maintained across 10 days of use and various glucose concentration ranges in both adults and children and adolescents.ConclusionsThe G6 system utilizing an automated sensor applicator provides accurate glucose readings in adults and children and adolescents throughout the 10-day sensor life.

| S-EPMC6422005 | biostudies-literature

Three-Dimensional Bi-Continuous Nanoporous Gold/Nickel Foam Supported MnO2 for High Performance Supercapacitors.

Project description:A three-dimensional bi-continuous nanoporous gold (NPG)/nickel foam is developed though the electrodeposition of a gold-tin alloy on Ni foam and subsequent chemical dealloying of tin. The newly-designed 3D metal structure is used to anchor MnO2 nanosheets for high-performance supercapacitors. The formed ternary composite electrodes exhibit significantly-enhanced capacitance performance, rate capability, and excellent cycling stability. A specific capacitance of 442?Fg-1 is achieved at a scan rate of 5?mV?s-1 and a relatively high mass loading of 865??g?cm-2. After 2500 cycles, only a 1% decay is found at a scan rate of 50?mV?s-1. A high power density of 3513?W?kg-1 and an energy density of 25.73?Wh?kg-1 are realized for potential energy storage devices. The results demonstrate that the NPG/nickel foam hybrid structure significantly improves the dispersibility of MnO2 and makes it promising for practical energy storage applications.

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