Browse
Submit Data
Databases
API
Help

Dataset Information

0 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs.

ABSTRACT: BACKGROUND:The problem of enumerating bubbles with length constraints in directed graphs arises in transcriptomics where the question is to identify all alternative splicing events present in a sample of mRNAs sequenced by RNA-seq. RESULTS:We present a new algorithm for enumerating bubbles with length constraints in weighted directed graphs. This is the first polynomial delay algorithm for this problem and we show that in practice, it is faster than previous approaches. CONCLUSION:This settles one of the main open questions from Sacomoto et al. (BMC Bioinform 13:5, 2012). Moreover, the new algorithm allows us to deal with larger instances and possibly detect longer alternative splicing events.

SUBMITTER: Sacomoto G

PROVIDER: S-EPMC4483228 | biostudies-literature | 2015

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs.

Sacomoto Gustavo G Lacroix Vincent V Sagot Marie-France MF

Algorithms for molecular biology : AMB 20150627

<h4>Background</h4>The problem of enumerating bubbles with length constraints in directed graphs arises in transcriptomics where the question is to identify all alternative splicing events present in a sample of mRNAs sequenced by RNA-seq.<h4>Results</h4>We present a new algorithm for enumerating bubbles with length constraints in weighted directed graphs. This is the first polynomial delay algorithm for this problem and we show that in practice, it is faster than previous approaches.<h4>Conclus ...[more]

PMID: 26120359

Similar Datasets

Efficient enumeration of monocyclic chemical graphs with given path frequencies.

Project description:BackgroundThe enumeration of chemical graphs (molecular graphs) satisfying given constraints is one of the fundamental problems in chemoinformatics and bioinformatics because it leads to a variety of useful applications including structure determination and development of novel chemical compounds.ResultsWe consider the problem of enumerating chemical graphs with monocyclic structure (a graph structure that contains exactly one cycle) from a given set of feature vectors, where a feature vector represents the frequency of the prescribed paths in a chemical compound to be constructed and the set is specified by a pair of upper and lower feature vectors. To enumerate all tree-like (acyclic) chemical graphs from a given set of feature vectors, Shimizu et al. and Suzuki et al. proposed efficient branch-and-bound algorithms based on a fast tree enumeration algorithm. In this study, we devise a novel method for extending these algorithms to enumeration of chemical graphs with monocyclic structure by designing a fast algorithm for testing uniqueness. The results of computational experiments reveal that the computational efficiency of the new algorithm is as good as those for enumeration of tree-like chemical compounds.ConclusionsWe succeed in expanding the class of chemical graphs that are able to be enumerated efficiently.

| S-EPMC4049473 | biostudies-literature

A polynomial algorithm for best-subset selection problem.

Project description:Best-subset selection aims to find a small subset of predictors, so that the resulting linear model is expected to have the most desirable prediction accuracy. It is not only important and imperative in regression analysis but also has far-reaching applications in every facet of research, including computer science and medicine. We introduce a polynomial algorithm, which, under mild conditions, solves the problem. This algorithm exploits the idea of sequencing and splicing to reach a stable solution in finite steps when the sparsity level of the model is fixed but unknown. We define an information criterion that helps the algorithm select the true sparsity level with a high probability. We show that when the algorithm produces a stable optimal solution, that solution is the oracle estimator of the true parameters with probability one. We also demonstrate the power of the algorithm in several numerical studies.

| S-EPMC7777147 | biostudies-literature

Analyzing microarray data with transitive directed acyclic graphs

Project description:Test compound one, 5,6-benzoflavone (BNF), was known to act through both the Ah receptor and Nrf2 receptor pathways, while test compounds two and three, 3H-1,2-dithiole-3-thione (D3T) and 4-methyl-5-pyrazinyl-3H-1,2-dithiole-3-thione (OLT), were known to act through the Nrf2 receptor pathway. Furthermore, D3T is known to be more potent and efficacious than OLT for Nrf2 activation. OLT has been shown to exhibit 20-50% of the efficacy of D3T for inhibition of alfatoxin-induced heptic foci. Nonetheless, because OLT is an approved drug, it is currently being evaluated in human phase II intervention trials of biomarkers of alfatoxin-related hepatocellular carcinoma. More recently, BNF was shown to be an effective chemopreventive agent in the rat mammary carcinogen model, inhibiting 7,12-dimethylbenz(a)anthracene DNA adduct formation in liver and mammary cells by 96 and 83% respectively. We used microarrays to study the structure activities that lie within the test compounds. Keywords: treatment effect study

2008-12-30 | GSE8880 | GEO

Polynomial-time quantum algorithm for the simulation of chemical dynamics.

Project description:The computational cost of exact methods for quantum simulation using classical computers grows exponentially with system size. As a consequence, these techniques can be applied only to small systems. By contrast, we demonstrate that quantum computers could exactly simulate chemical reactions in polynomial time. Our algorithm uses the split-operator approach and explicitly simulates all electron-nuclear and interelectronic interactions in quadratic time. Surprisingly, this treatment is not only more accurate than the Born-Oppenheimer approximation but faster and more efficient as well, for all reactions with more than about four atoms. This is the case even though the entire electronic wave function is propagated on a grid with appropriately short time steps. Although the preparation and measurement of arbitrary states on a quantum computer is inefficient, here we demonstrate how to prepare states of chemical interest efficiently. We also show how to efficiently obtain chemically relevant observables, such as state-to-state transition probabilities and thermal reaction rates. Quantum computers using these techniques could outperform current classical computers with 100 qubits.

| S-EPMC2596249 | biostudies-literature

Evidence synthesis for constructing directed acyclic graphs (ESC-DAGs): a novel and systematic method for building directed acyclic graphs.

Project description:BackgroundDirected acyclic graphs (DAGs) are popular tools for identifying appropriate adjustment strategies for epidemiological analysis. However, a lack of direction on how to build them is problematic. As a solution, we propose using a combination of evidence synthesis strategies and causal inference principles to integrate the DAG-building exercise within the review stages of research projects. We demonstrate this idea by introducing a novel protocol: 'Evidence Synthesis for Constructing Directed Acyclic Graphs' (ESC-DAGs)'.MethodsESC-DAGs operates on empirical studies identified by a literature search, ideally a novel systematic review or review of systematic reviews. It involves three key stages: (i) the conclusions of each study are 'mapped' into a DAG; (ii) the causal structures in these DAGs are systematically assessed using several causal inference principles and are corrected accordingly; (iii) the resulting DAGs are then synthesised into one or more 'integrated DAGs'. This demonstration article didactically applies ESC-DAGs to the literature on parental influences on offspring alcohol use during adolescence.ConclusionsESC-DAGs is a practical, systematic and transparent approach for developing DAGs from background knowledge. These DAGs can then direct primary data analysis and DAG-based sensitivity analysis. ESC-DAGs has a modular design to allow researchers who are experienced DAG users to both use and improve upon the approach. It is also accessible to researchers with limited experience of DAGs or evidence synthesis.

| S-EPMC7124493 | biostudies-literature

Prediction of recombinant <i>Mycobacterium tuberculosis</i> α-crystallin oligomer chaperone activity using polynomial graphs.

Project description:Background: Mycobacterial α-crystallin (Acr) is a chaperone that prevents misfolding of proteins when Mycobacterium tuberculosis is found in a latent form in the host tissue. Methods: Using insulin as a model substrate and utilizing polynomial graphs, we attempted to predict molecular-level interactions that are a function of the oligomeric state of the recombinant protein. The chaperone activity of the recombinant oligomeric Acr was measured at 60°C with Acr samples obtained before gel filtration chromatography and compared with a gel-filtered sample. Results: The polynomial graphs constructed showed improved molecular coverage of the insulin B chain by the oligomer. The 2 nd order coefficient is the one that changes with the oligomeric ratio of Acr and improves chaperone activity. Polynomial analysis suggested that it could be a useful parameter to predict chaperone activity for potential in vitro batches of M. tuberculosis Acr based on the dynamic nature of the association and disassociation of oligomers. Conclusions: The results showed that coverage of insulin B chain improved with higher ratio of 9-mer as compared to lower ratios. This was shown by both simulation plots and actual assay data. The polynomial graphs showed increase in the 2 nd order coefficient, thus suggesting the important role of oligomerisation in improved molecular coverage of insulin B chain.

| S-EPMC7327723 | biostudies-literature

Phasertng: directed acyclic graphs for crystallographic phasing.

Project description:Crystallographic phasing strategies increasingly require the exploration and ranking of many hypotheses about the number, types and positions of atoms, molecules and/or molecular fragments in the unit cell, each with only a small chance of being correct. Accelerating this move has been improvements in phasing methods, which are now able to extract phase information from the placement of very small fragments of structure, from weak experimental phasing signal or from combinations of molecular replacement and experimental phasing information. Describing phasing in terms of a directed acyclic graph allows graph-management software to track and manage the path to structure solution. The crystallographic software supporting the graph data structure must be strictly modular so that nodes in the graph are efficiently generated by the encapsulated functionality. To this end, the development of new software, Phasertng, which uses directed acyclic graphs natively for input/output, has been initiated. In Phasertng, the codebase of Phaser has been rebuilt, with an emphasis on modularity, on scripting, on speed and on continuing algorithm development. As a first application of phasertng, its advantages are demonstrated in the context of phasertng.xtricorder, a tool to analyse and triage merged data in preparation for molecular replacement or experimental phasing. The description of the phasing strategy with directed acyclic graphs is a generalization that extends beyond the functionality of Phasertng, as it can incorporate results from bioinformatics and other crystallographic tools, and will facilitate multifaceted search strategies, dynamic ranking of alternative search pathways and the exploitation of machine learning to further improve phasing strategies.

| S-EPMC7787104 | biostudies-literature

Directed Acyclic Graphs for Oral Disease Research.

Project description:Directed acyclic graphs (DAGs) are nonparametric graphical tools used to depict causal relations in the epidemiologic assessment of exposure-outcome associations. Although their use in dental research was first advocated in 2002, DAGs have yet to be widely adopted in this field. DAGs help identify threats to causal inference such as confounders, bias due to subject selection, and inappropriate handling of missing data. DAGs can also inform the data analysis strategy based on relations among variables depicted on it. This article uses the example of a study of temporomandibular disorders (TMDs), investigating causal effects of facial injury on subsequent risk of TMD. We illustrate how DAGs can be used to identify 1) potential confounders, 2) mediators and the consequences of attempt to estimate direct causal effects, 3) colliders and the consequences of conditioning on colliders, and 4) variables that are simultaneously mediators and confounders and the consequences of adjustment for such variables. For example, one DAG shows that statistical adjustment for the pressure pain threshold would necessarily bias the causal relation between facial injury and TMD. Finally, we discuss the usefulness of DAGs during study design, subject selection, and choosing variables to be measured in a study.

| S-EPMC4935832 | biostudies-literature

MagNet: A Neural Network for Directed Graphs.

Project description:The prevalence of graph-based data has spurred the rapid development of graph neural networks (GNNs) and related machine learning algorithms. Yet, despite the many datasets naturally modeled as directed graphs, including citation, website, and traffic networks, the vast majority of this research focuses on undirected graphs. In this paper, we propose MagNet, a GNN for directed graphs based on a complex Hermitian matrix known as the magnetic Laplacian. This matrix encodes undirected geometric structure in the magnitude of its entries and directional information in their phase. A "charge" parameter attunes spectral information to variation among directed cycles. We apply our network to a variety of directed graph node classification and link prediction tasks showing that MagNet performs well on all tasks and that its performance exceeds all other methods on a majority of such tasks. The underlying principles of MagNet are such that it can be adapted to other GNN architectures.

| S-EPMC9425115 | biostudies-literature

Enumerating consistent sub-graphs of directed acyclic graphs: an insight into biomedical ontologies.

Project description:MotivationModern problems of concept annotation associate an object of interest (gene, individual, text document) with a set of interrelated textual descriptors (functions, diseases, topics), often organized in concept hierarchies or ontologies. Most ontology can be seen as directed acyclic graphs (DAGs), where nodes represent concepts and edges represent relational ties between these concepts. Given an ontology graph, each object can only be annotated by a consistent sub-graph; that is, a sub-graph such that if an object is annotated by a particular concept, it must also be annotated by all other concepts that generalize it. Ontologies therefore provide a compact representation of a large space of possible consistent sub-graphs; however, until now we have not been aware of a practical algorithm that can enumerate such annotation spaces for a given ontology.ResultsWe propose an algorithm for enumerating consistent sub-graphs of DAGs. The algorithm recursively partitions the graph into strictly smaller graphs until the resulting graph becomes a rooted tree (forest), for which a linear-time solution is computed. It then combines the tallies from graphs created in the recursion to obtain the final count. We prove the correctness of this algorithm, propose several practical accelerations, evaluate it on random graphs and then apply it to characterize four major biomedical ontologies. We believe this work provides valuable insights into the complexity of concept annotation spaces and its potential influence on the predictability of ontological annotation.Availability and implementationhttps://github.com/shawn-peng/counting-consistent-sub-DAG.Supplementary informationSupplementary data are available at Bioinformatics online.

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