Browse
Submit Data
Databases
API
Help

Dataset Information

2 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

SPABBATS: A pathway-discovery method based on Boolean satisfiability that facilitates the characterization of suppressor mutants.

ABSTRACT:

Background

Several computational methods exist to suggest rational genetic interventions that improve the productivity of industrial strains. Nonetheless, these methods are less effective to predict possible genetic responses of the strain after the intervention. This problem requires a better understanding of potential alternative metabolic and regulatory pathways able to counteract the targeted intervention.

Results

Here we present SPABBATS, an algorithm based on Boolean satisfiability (SAT) that computes alternative metabolic pathways between input and output species in a reconstructed network. The pathways can be constructed iteratively in order of increasing complexity. SPABBATS allows the accumulation of intermediates in the pathways, which permits discovering pathways missed by most traditional pathway analysis methods. In addition, we provide a proof of concept experiment for the validity of the algorithm. We deleted the genes for the glutamate dehydrogenases of the Gram-positive bacterium Bacillus subtilis and isolated suppressor mutant strains able to grow on glutamate as single carbon source. Our SAT approach proposed candidate alternative pathways which were decisive to pinpoint the exact mutation of the suppressor strain.

Conclusions

SPABBATS is the first application of SAT techniques to metabolic problems. It is particularly useful for the characterization of metabolic suppressor mutants and can be used in a synthetic biology setting to design new pathways with specific input-output requirements.

SUBMITTER: Florez LA

PROVIDER: S-EPMC3024933 | biostudies-literature |

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Similar Datasets

Efficient solution of Boolean satisfiability problems with digital memcomputing.

Project description:Boolean satisfiability is a propositional logic problem of interest in multiple fields, e.g., physics, mathematics, and computer science. Beyond a field of research, instances of the SAT problem, as it is known, require efficient solution methods in a variety of applications. It is the decision problem of determining whether a Boolean formula has a satisfying assignment, believed to require exponentially growing time for an algorithm to solve for the worst-case instances. Yet, the efficient solution of many classes of Boolean formulae eludes even the most successful algorithms, not only for the worst-case scenarios, but also for typical-case instances. Here, we introduce a memory-assisted physical system (a digital memcomputing machine) that, when its non-linear ordinary differential equations are integrated numerically, shows evidence for polynomially-bounded scalability while solving "hard" planted-solution instances of SAT, known to require exponential time to solve in the typical case for both complete and incomplete algorithms. Furthermore, we analytically demonstrate that the physical system can efficiently solve the SAT problem in continuous time, without the need to introduce chaos or an exponentially growing energy. The efficiency of the simulations is related to the collective dynamical properties of the original physical system that persist in the numerical integration to robustly guide the solution search even in the presence of numerical errors. We anticipate our results to broaden research directions in physics-inspired computing paradigms ranging from theory to application, from simulation to hardware implementation.

| S-EPMC7665037 | biostudies-literature

Artificial dragonfly algorithm in the Hopfield neural network for optimal Exact Boolean k satisfiability representation.

Project description:This study proposes a novel hybrid computational approach that integrates the artificial dragonfly algorithm (ADA) with the Hopfield neural network (HNN) to achieve an optimal representation of the Exact Boolean kSatisfiability (EBkSAT) logical rule. The primary objective is to investigate the effectiveness and robustness of the ADA algorithm in expediting the training phase of the HNN to attain an optimized EBkSAT logic representation. To assess the performance of the proposed hybrid computational model, a specific Exact Boolean kSatisfiability problem is constructed, and simulated data sets are generated. The evaluation metrics employed include the global minimum ratio (GmR), root mean square error (RMSE), mean absolute percentage error (MAPE), and network computational time (CT) for EBkSAT representation. Comparative analyses are conducted between the results obtained from the proposed model and existing models in the literature. The findings demonstrate that the proposed hybrid model, ADA-HNN-EBkSAT, surpasses existing models in terms of accuracy and computational time. This suggests that the ADA algorithm exhibits effective compatibility with the HNN for achieving an optimal representation of the EBkSAT logical rule. These outcomes carry significant implications for addressing intricate optimization problems across diverse domains, including computer science, engineering, and business.

| S-EPMC10519610 | biostudies-literature

Predicting the satisfiability of Boolean formulas by incorporating gated recurrent unit (GRU) in the Transformer framework.

Project description:The Boolean satisfiability (SAT) problem exhibits different structural features in various domains. Neural network models can be used as more generalized algorithms that can be learned to solve specific problems based on different domain data than traditional rule-based approaches. How to accurately identify these structural features is crucial for neural networks to solve the SAT problem. Currently, learning-based SAT solvers, whether they are end-to-end models or enhancements to traditional heuristic algorithms, have achieved significant progress. In this article, we propose TG-SAT, an end-to-end framework based on Transformer and gated recurrent neural network (GRU) for predicting the satisfiability of SAT problems. TG-SAT can learn the structural features of SAT problems in a weakly supervised environment. To capture the structural information of the SAT problem, we encodes a SAT problem as an undirected graph and integrates GRU into the Transformer structure to update the node embeddings. By computing cross-attention scores between literals and clauses, a weighted representation of nodes is obtained. The model is eventually trained as a classifier to predict the satisfiability of the SAT problem. Experimental results demonstrate that TG-SAT achieves a 2%-5% improvement in accuracy on random 3-SAT problems compared to NeuroSAT. It also outperforms in SR(N), especially in handling more complex SAT problems, where our model achieves higher prediction accuracy.

| S-EPMC11323027 | biostudies-literature

affy_aba_ath1-Characterization of aba3-1 suppressor mutants

Project description:affy_aba_ath1 - affy_aba_ath1 - In order to identify new genes implicated in ABA signalisation pathways, we have carried out a screen for suppressor mutants of the ABA deficient mutant aba3-1. Infrared thermography was used to identify plants whose cold leaf phenotype was reverted. The transcriptome analysis of four recessive suppressor mutants was undertaken to determine which genes are differentially expressed compared to the wild type or aba3-1. Such genes could represent the mutated gene itself or indicate signalling or response pathways affected by the mutation-comparison of four suppressor mutants (g-radiation induced) to wild type and the ABA deficient mutant aba3-1 Keywords: wt vs mutant comparison

2008-09-01 | GSE7961 | GEO

Analysis and practical guideline of constraint-based boolean method in genetic network inference.

Project description:Boolean-based method, despite of its simplicity, would be a more attractive approach for inferring a network from high-throughput expression data if its effectiveness has not been limited by high false positive prediction. In this study, we explored factors that could simply be adjusted to improve the accuracy of inferring networks. Our work focused on the analysis of the effects of discretisation methods, biological constraints, and stringency of boolean function assignment on the performance of boolean network, including accuracy, precision, specificity and sensitivity, using three sets of microarray time-series data. The study showed that biological constraints have pivotal influence on the network performance over the other factors. It can reduce the variation in network performance resulting from the arbitrary selection of discretisation methods and stringency settings. We also presented the master boolean network as an approach to establish the unique solution for boolean analysis. The information acquired from the analysis was summarised and deployed as a general guideline for an efficient use of boolean-based method in the network inference. In the end, we provided an example of the use of such a guideline in the study of Arabidopsis circadian clock genetic network from which much interesting biological information can be inferred.

| S-EPMC3260258 | biostudies-literature

A Boolean approach for novel hypoxia-related gene discovery.

Project description:Hypoxia plays a major role in the etiology and pathogenesis of most of the leading causes of morbidity and mortality, whether cardiovascular diseases, cancer, respiratory diseases or stroke. Despite active research on hypoxia-signaling pathways, the understanding of regulatory mechanisms, especially in specific tissues, still remain elusive. With the accessibility of thousands of potentially diverse genomic datasets, computational methods are utilized to generate new hypotheses. Here we utilized Boolean implication relationship, a powerful method to probe symmetrically and asymmetrically related genes, to identify novel hypoxia related genes. We used a well-known hypoxia-responsive gene, VEGFA, with very large human expression datasets (n = 25,955) to identify novel hypoxia-responsive candidate gene/s. Further, we utilized in-vitro analysis using human endothelial cells exposed to 1% O2 environment for 2, 8, 24 and 48 hours to validate top candidate genes. Out of the top candidate genes (n = 19), 84% genes were previously reported as hypoxia related, validating our results. However, we identified FAM114A1 as a novel candidate gene significantly upregulated in the endothelial cells at 8, 24 and 48 hours of 1% O2 environment. Additional evidence, particularly the localization of intronic miRNA and numerous HREs further support and strengthen our finding. Current results on FAM114A1 provide an example demonstrating the utility of powerful computational methods, like Boolean implications, in playing a major role in hypothesis building and discovery.

| S-EPMC9409593 | biostudies-literature

A novel mutual information-based Boolean network inference method from time-series gene expression data.

Project description:BackgroundInferring a gene regulatory network from time-series gene expression data in systems biology is a challenging problem. Many methods have been suggested, most of which have a scalability limitation due to the combinatorial cost of searching a regulatory set of genes. In addition, they have focused on the accurate inference of a network structure only. Therefore, there is a pressing need to develop a network inference method to search regulatory genes efficiently and to predict the network dynamics accurately.ResultsIn this study, we employed a Boolean network model with a restricted update rule scheme to capture coarse-grained dynamics, and propose a novel mutual information-based Boolean network inference (MIBNI) method. Given time-series gene expression data as an input, the method first identifies a set of initial regulatory genes using mutual information-based feature selection, and then improves the dynamics prediction accuracy by iteratively swapping a pair of genes between sets of the selected regulatory genes and the other genes. Through extensive simulations with artificial datasets, MIBNI showed consistently better performance than six well-known existing methods, REVEAL, Best-Fit, RelNet, CST, CLR, and BIBN in terms of both structural and dynamics prediction accuracy. We further tested the proposed method with two real gene expression datasets for an Escherichia coli gene regulatory network and a fission yeast cell cycle network, and also observed better results using MIBNI compared to the six other methods.ConclusionsTaken together, MIBNI is a promising tool for predicting both the structure and the dynamics of a gene regulatory network.

| S-EPMC5298315 | biostudies-literature

A Near-Optimal Control Method for Stochastic Boolean Networks.

Project description:One of the ultimate goals in systems biology is to develop control strategies to find efficient medical treatments. One step towards this goal is to develop methods for changing the state of a cell into a desirable state. We propose an efficient method that determines combinations of network perturbations to direct the system towards a predefined state. The method requires a set of control actions such as the silencing of a gene or the disruption of the interaction between two genes. An optimal control policy defined as the best intervention at each state of the system can be obtained using existing methods. However, these algorithms are computationally prohibitive for models with tens of nodes. Our method generates control actions that approximates the optimal control policy with high probability with a computational efficiency that does not depend on the size of the state space. Our C++ code is available at https://github.com/boaguilar/SDDScontrol.

| S-EPMC8208226 | biostudies-literature

Therapeutic target discovery using Boolean network attractors: improvements of kali.

Project description:In a previous article, an algorithm for identifying therapeutic targets in Boolean networks modelling pathological mechanisms was introduced. In the present article, the improvements made on this algorithm, named kali, are described. These improvements are (i) the possibility to work on asynchronous Boolean networks, (ii) a finer assessment of therapeutic targets and (iii) the possibility to use multivalued logic. kali assumes that the attractors of a dynamical system, such as a Boolean network, are associated with the phenotypes of the modelled biological system. Given a logic-based model of pathological mechanisms, kali searches for therapeutic targets able to reduce the reachability of the attractors associated with pathological phenotypes, thus reducing their likeliness. kali is illustrated on an example network and used on a biological case study. The case study is a published logic-based model of bladder tumorigenesis from which kali returns consistent results. However, like any computational tool, kali can predict but cannot replace human expertise: it is a supporting tool for coping with the complexity of biological systems in the field of drug discovery.

| S-EPMC5830779 | biostudies-literature

A novel constrained genetic algorithm-based Boolean network inference method from steady-state gene expression data.

Project description:MotivationIt is a challenging problem in systems biology to infer both the network structure and dynamics of a gene regulatory network from steady-state gene expression data. Some methods based on Boolean or differential equation models have been proposed but they were not efficient in inference of large-scale networks. Therefore, it is necessary to develop a method to infer the network structure and dynamics accurately on large-scale networks using steady-state expression.ResultsIn this study, we propose a novel constrained genetic algorithm-based Boolean network inference (CGA-BNI) method where a Boolean canalyzing update rule scheme was employed to capture coarse-grained dynamics. Given steady-state gene expression data as an input, CGA-BNI identifies a set of path consistency-based constraints by comparing the gene expression level between the wild-type and the mutant experiments. It then searches Boolean networks which satisfy the constraints and induce attractors most similar to steady-state expressions. We devised a heuristic mutation operation for faster convergence and implemented a parallel evaluation routine for execution time reduction. Through extensive simulations on the artificial and the real gene expression datasets, CGA-BNI showed better performance than four other existing methods in terms of both structural and dynamics prediction accuracies. Taken together, CGA-BNI is a promising tool to predict both the structure and the dynamics of a gene regulatory network when a highest accuracy is needed at the cost of sacrificing the execution time.Availability and implementationSource code and data are freely available at https://github.com/csclab/CGA-BNI.Supplementary informationSupplementary data are available at Bioinformatics online.

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