The Glasgow Subgraph Solver: Using Constraint Programming to Tackle Hard Subgraph Isomorphism Problem Variants
Ontology highlight
ABSTRACT:
SUBMITTER: Gadducci F
PROVIDER: S-EPMC7314700 | biostudies-literature | 2020 May
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:BackgroundGraphs can represent biological networks at the molecular, protein, or species level. An important query is to find all matches of a pattern graph to a target graph. Accomplishing this is inherently difficult (NP-complete) and the efficiency of heuristic algorithms for the problem may depend upon the input graphs. The common aim of existing algorithms is to eliminate unsuccessful mappings as early as and as inexpensively as possible.ResultsWe propose a new subgraph isomorphism algorithm which applies a search strategy to significantly reduce the search space without using any complex pruning rules or domain reduction procedures. We compare our method with the most recent and efficient subgraph isomorphism algorithms (VFlib, LAD, and our C++ implementation of FocusSearch which was originally distributed in Modula2) on synthetic, molecules, and interaction networks data. We show a significant reduction in the running time of our approach compared with these other excellent methods and show that our algorithm scales well as memory demands increase.ConclusionsSubgraph isomorphism algorithms are intensively used by biochemical tools. Our analysis gives a comprehensive comparison of different software approaches to subgraph isomorphism highlighting their weaknesses and strengths. This will help researchers make a rational choice among methods depending on their application. We also distribute an open-source package including our system and our own C++ implementation of FocusSearch together with all the used datasets (http://ferrolab.dmi.unict.it/ri.html). In future work, our findings may be extended to approximate subgraph isomorphism algorithms.
| S-EPMC3633016 | biostudies-literature
Project description:Recent advances in neuroscience have enabled the exploration of brain structure at the level of individual synaptic connections. These connectomics datasets continue to grow in size and complexity; methods to search for and identify interesting graph patterns offer a promising approach to quickly reduce data dimensionality and enable discovery. These graphs are often too large to be analyzed manually, presenting significant barriers to searching for structure and testing hypotheses. We combine graph database and analysis libraries with an easy-to-use neuroscience grammar suitable for rapidly constructing queries and searching for subgraphs and patterns of interest. Our approach abstracts many of the computer science and graph theory challenges associated with nanoscale brain network analysis and allows scientists to quickly conduct research at scale. We demonstrate the utility of these tools by searching for motifs on simulated data and real public connectomics datasets, and we share simple and complex structures relevant to the neuroscience community. We contextualize our findings and provide case studies and software to motivate future neuroscience exploration.
| S-EPMC8219732 | biostudies-literature
Project description:Tailored physical systems were recently exploited to rapidly solve hard computational challenges, such as spin simulators, combinatorial optimization, and focusing through scattering media. Here, we address the phase retrieval problem where an object is reconstructed from its scattered intensity distribution. This is a key problem in many applications, ranging from x-ray imaging to astrophysics, and currently, it lacks efficient direct reconstruction methods: The widely used indirect iterative algorithms are inherently slow. We present an optical approach based on a digital degenerate cavity laser, whose most probable lasing mode rapidly and efficiently reconstructs the object. Our experimental results suggest that the gain competition between the many lasing modes acts as a highly parallel computer that could rapidly solve the phase retrieval problem. Our approach applies to most two-dimensional objects with known compact support, including complex-valued objects, and can be generalized to imaging through scattering media and other hard computational tasks.
| S-EPMC6777974 | biostudies-literature
Project description:Chemical reactions are rearrangements of chemical bonds. Each atom in an educt molecule thus appears again in a specific position of one of the reaction products. This bijection between educt and product atoms is not reported by chemical reaction databases, however, so that the "Atom Mapping Problem" of finding this bijection is left as an important computational task for many practical applications in computational chemistry and systems biology. Elementary chemical reactions feature a cyclic imaginary transition state (ITS) that imposes additional restrictions on the bijection between educt and product atoms that are not taken into account by previous approaches. We demonstrate that Constraint Programming is well-suited to solving the Atom Mapping Problem in this setting. The performance of our approach is evaluated for a manually curated subset of chemical reactions from the KEGG database featuring various ITS cycle layouts and reaction mechanisms.
| S-EPMC4256833 | biostudies-other
Project description:Pneumomediastinum is a relatively rare and usually a self-limiting condition in infants. However, it can lead to tension pneumomediastinum or pneumothorax, which may rapidly become life-threatening. Therefore, its timely and accurate detection is important and close follow-up to resolution is needed. Ultrasound can be used as a real-time problem solver to accurately diagnose pneumomediastinum in an infant and should be encouraged as a radiation-free adjunct imaging modality when radiography cannot provide a definite diagnosis. We present a case of a 13-month-old preterm girl with bronchopulmonary dysplasia and acute respiratory infection who presented with sudden respiratory failure due to spontaneous pneumomediastinum. Pneumomediastinum was eventually diagnosed with ultrasound, after chest radiography performed during the on-call hours was misinterpreted because not all typical radiographic signs of pneumomediastinum were present.
| S-EPMC8421572 | biostudies-literature
Project description:Quantum annealing is a proposed combinatorial optimization technique meant to exploit quantum mechanical effects such as tunneling and entanglement. Real-world quantum annealing-based solvers require a combination of annealing and classical pre- and post-processing; at this early stage, little is known about how to partition and optimize the processing. This article presents an experimental case study of quantum annealing and some of the factors involved in real-world solvers, using a 504-qubit D-Wave Two machine and the graph isomorphism problem. To illustrate the role of classical pre-processing, a compact Hamiltonian is presented that enables a reduced Ising model for each problem instance. On random N-vertex graphs, the median number of variables is reduced from N(2) to fewer than N log2 N and solvable graph sizes increase from N = 5 to N = 13. Additionally, error correction via classical post-processing majority voting is evaluated. While the solution times are not competitive with classical approaches to graph isomorphism, the enhanced solver ultimately classified correctly every problem that was mapped to the processor and demonstrated clear advantages over the baseline approach. The results shed some light on the nature of real-world quantum annealing and the associated hybrid classical-quantum solvers.
| S-EPMC4459189 | biostudies-other
Project description:Miocene baleen whales were highly diverse and included tens of genera. However, their taxonomy and phylogeny, as well as relationships with living whales, are still a subject of controversy. Here, "Mesocetus" argillarius, a poorly known specimen from Denmark, is redescribed with a focus on the cranial anatomy. It was found to represent not only a new genus, Tranatocetus gen. nov., but also a new family; Tranatocetidae. The whales of this family have the rostral bones either overriding or dividing the frontals; the rostral bones are contacting the parietals and nasals dividing the maxillae on the vertex; the occipital shield is dorsoventrally bent. The tympanic bulla is particularly characteristic of this family featuring a short, narrow anterior portion with a rounded or squared anterior end and a wider and higher posterior portion that is swollen in the posteroventral area. A phylogenetic analysis including 51 taxa supports a monophyletic group comprising most Neogene and modern whales, with Tranatocetidae being possibly closer related to Balaenopteridae (rorquals) than to Cetotheriidae. Tranatocetidae exhibit a charahteristic bulla shape. In fact, all Neogene and modern mysticete families examined have a unique shape of the tympanic bulla that is diagnostic at family-level. Inclusion of problematic taxa like Tranatocetus argillarius in phylogenies brings new understanding of the distribution and diagnostic value of character traits. This underlines the need for re-examination of earlier described specimens in the light of the wealth of new information published in later years.
| S-EPMC4558012 | biostudies-literature
Project description:BackgroundThe protein structure prediction problem is one of the most challenging problems in biological sciences. Many approaches have been proposed using database information and/or simplified protein models. The protein structure prediction problem can be cast in the form of an optimization problem. Notwithstanding its importance, the problem has very seldom been tackled by Constraint Logic Programming, a declarative programming paradigm suitable for solving combinatorial optimization problems.ResultsConstraint Logic Programming techniques have been applied to the protein structure prediction problem on the face-centered cube lattice model. Molecular dynamics techniques, endowed with the notion of constraint, have been also exploited. Even using a very simplified model, Constraint Logic Programming on the face-centered cube lattice model allowed us to obtain acceptable results for a few small proteins. As a test implementation their (known) secondary structure and the presence of disulfide bridges are used as constraints. Simplified structures obtained in this way have been converted to all atom models with plausible structure. Results have been compared with a similar approach using a well-established technique as molecular dynamics.ConclusionsThe results obtained on small proteins show that Constraint Logic Programming techniques can be employed for studying protein simplified models, which can be converted into realistic all atom models. The advantage of Constraint Logic Programming over other, much more explored, methodologies, resides in the rapid software prototyping, in the easy way of encoding heuristics, and in exploiting all the advances made in this research area, e.g. in constraint propagation and its use for pruning the huge search space.
| S-EPMC539352 | biostudies-literature
Project description:MotivationRNA thermometers (RNATs) are cis-regulatory elements that change secondary structure upon temperature shift. Often involved in the regulation of heat shock, cold shock and virulence genes, RNATs constitute an interesting potential resource in synthetic biology, where engineered RNATs could prove to be useful tools in biosensors and conditional gene regulation.ResultsSolving the 2-temperature inverse folding problem is critical for RNAT engineering. Here we introduce RNAiFold2T, the first Constraint Programming (CP) and Large Neighborhood Search (LNS) algorithms to solve this problem. Benchmarking tests of RNAiFold2T against existent programs (adaptive walk and genetic algorithm) inverse folding show that our software generates two orders of magnitude more solutions, thus allowing ample exploration of the space of solutions. Subsequently, solutions can be prioritized by computing various measures, including probability of target structure in the ensemble, melting temperature, etc. Using this strategy, we rationally designed two thermosensor internal ribosome entry site (thermo-IRES) elements, whose normalized cap-independent translation efficiency is approximately 50% greater at 42 °C than 30 °C, when tested in reticulocyte lysates. Translation efficiency is lower than that of the wild-type IRES element, which on the other hand is fully resistant to temperature shift-up. This appears to be the first purely computational design of functional RNA thermoswitches, and certainly the first purely computational design of functional thermo-IRES elements.AvailabilityRNAiFold2T is publicly available as part of the new release RNAiFold3.0 at https://github.com/clotelab/RNAiFold and http://bioinformatics.bc.edu/clotelab/RNAiFold, which latter has a web server as well. The software is written in C ++ and uses OR-Tools CP search engine.Contactclote@bc.eduSupplementary informationSupplementary data are available at Bioinformatics online.
| S-EPMC4908349 | biostudies-literature
Project description:Abstract Consciousness presents a “hard problem” to scholars. At stake is how the physical body gives rise to subjective experience. Why consciousness is “hard”, however, is uncertain. One possibility is that the challenge arises from ontology—because consciousness is a special property/substance that is irreducible to the physical. Here, I show how the “hard problem” emerges from two intuitive biases that lie deep within human psychology: Essentialism and Dualism. To determine whether a subjective experience is transformative, people judge whether the experience pertains to one’s essence, and per Essentialism, one’s essence lies within one’s body. Psychological states that seem embodied (e.g., “color vision” ∼ eyes) can thus give rise to transformative experience. Per intuitive Dualism, however, the mind is distinct from the body, and epistemic states (knowledge and beliefs) seem particularly ethereal. It follows that conscious perception (e.g., “seeing color”) ought to seem more transformative than conscious knowledge (e.g., knowledge of how color vision works). Critically, the transformation arises precisely because the conscious perceptual experience seems readily embodied (rather than distinct from the physical body, as the ontological account suggests). In line with this proposal, five experiments show that, in laypeople’s view (a) experience is transformative only when it seems anchored in the human body; (b) gaining a transformative experience effects a bodily change; and (c) the magnitude of the transformation correlates with both (i) the perceived embodiment of that experience, and (ii) with Dualist intuitions, generally. These results cannot solve the ontological question of whether consciousness is distinct from the physical. But they do suggest that the roots of the “hard problem” are partly psychological.
| S-EPMC10449398 | biostudies-literature