A Boolean algebra for genetic variants.
Ontology highlight
ABSTRACT: Motivation
Beyond identifying genetic variants, we introduce a set of Boolean relations, which allows for a comprehensive classification of the relations of every pair of variants by taking all minimal alignments into account. We present an efficient algorithm to compute these relations, including a novel way of efficiently computing all minimal alignments within the best theoretical complexity bounds.Results
We show that these relations are common, and many non-trivial, for variants of the CFTR gene in dbSNP. Ultimately, we present an approach for the storing and indexing of variants in the context of a database that enables efficient querying for all these relations.Availability and implementation
A Python implementation is available at https://github.com/mutalyzer/algebra/tree/v0.2.0 as well as an interface at https://mutalyzer.nl/algebra.
SUBMITTER: Vis JK
PROVIDER: S-EPMC9879725 | biostudies-literature | 2023 Jan
REPOSITORIES: biostudies-literature
Publications
A Boolean algebra for genetic variants.
Vis Jonathan K JK Santcroos Mark A MA Kosters Walter A WA Laros Jeroen F J JFJ
Bioinformatics (Oxford, England) 20230101 1
<h4>Motivation</h4>Beyond identifying genetic variants, we introduce a set of Boolean relations, which allows for a comprehensive classification of the relations of every pair of variants by taking all minimal alignments into account. We present an efficient algorithm to compute these relations, including a novel way of efficiently computing all minimal alignments within the best theoretical complexity bounds.<h4>Results</h4>We show that these relations are common, and many non-trivial, for vari ...[more]
Similar Datasets
Project description:In Information Retrieval (IR), Data Mining (DM), and Machine Learning (ML), similarity measures have been widely used for text clustering and classification. The similarity measure is the cornerstone upon which the performance of most DM and ML algorithms is completely dependent. Thus, till now, the endeavor in literature for an effective and efficient similarity measure is still immature. Some recently-proposed similarity measures were effective, but have a complex design and suffer from inefficiencies. This work, therefore, develops an effective and efficient similarity measure of a simplistic design for text-based applications. The measure developed in this work is driven by Boolean logic algebra basics (BLAB-SM), which aims at effectively reaching the desired accuracy at the fastest run time as compared to the recently developed state-of-the-art measures. Using the term frequency-inverse document frequency (TF-IDF) schema, the K-nearest neighbor (KNN), and the K-means clustering algorithm, a comprehensive evaluation is presented. The evaluation has been experimentally performed for BLAB-SM against seven similarity measures on two most-popular datasets, Reuters-21 and Web-KB. The experimental results illustrate that BLAB-SM is not only more efficient but also significantly more effective than state-of-the-art similarity measures on both classification and clustering tasks.
| S-EPMC8330432 | biostudies-literature
Project description:Among the promising approaches for implementing high-performance computing, reconfigurable logic gates and logic-in-memory (LIM) approaches have been drawing increased research attention. These allow for improved functional scaling of a chip, owing to the improved functionality per unit area. Although numerous studies have been conducted independently for either reconfigurable logic or LIM units, attempts to construct a hybrid structure based on reconfigurable logic and LIM units remain relatively rare. In this study, we merge reconfigurable logic gates and LIM units to achieve a universal logic-in-memory (ULIM) cell for enabling all basic Boolean logic operations and data storage in a single cell. A ULIM cell consisting of silicon memory devices with reconfigurable n- and p-program modes can reconfigure logic operations within the complete set of Boolean logic operations. Moreover, the ULIM cell exhibits memory behaviors for storing output logic values without supply voltages for a certain period, resulting in zero static power consumption. Hence, this study provides a way to realize high-performance electronics by utilizing the silicon devices with a hybrid function of reconfigurable logic and LIM.
| S-EPMC9684131 | biostudies-literature
Project description:BackgroundA key problem in the analysis of mathematical models of molecular networks is the determination of their steady states. The present paper addresses this problem for Boolean network models, an increasingly popular modeling paradigm for networks lacking detailed kinetic information. For small models, the problem can be solved by exhaustive enumeration of all state transitions. But for larger models this is not feasible, since the size of the phase space grows exponentially with the dimension of the network. The dimension of published models is growing to over 100, so that efficient methods for steady state determination are essential. Several methods have been proposed for large networks, some of them heuristic. While these methods represent a substantial improvement in scalability over exhaustive enumeration, the problem for large networks is still unsolved in general.ResultsThis paper presents an algorithm that consists of two main parts. The first is a graph theoretic reduction of the wiring diagram of the network, while preserving all information about steady states. The second part formulates the determination of all steady states of a Boolean network as a problem of finding all solutions to a system of polynomial equations over the finite number system with two elements. This problem can be solved with existing computer algebra software. This algorithm compares favorably with several existing algorithms for steady state determination. One advantage is that it is not heuristic or reliant on sampling, but rather determines algorithmically and exactly all steady states of a Boolean network. The code for the algorithm, as well as the test suite of benchmark networks, is available upon request from the corresponding author.ConclusionsThe algorithm presented in this paper reliably determines all steady states of sparse Boolean networks with up to 1000 nodes. The algorithm is effective at analyzing virtually all published models even those of moderate connectivity. The problem for large Boolean networks with high average connectivity remains an open problem.
| S-EPMC4230806 | biostudies-literature
Project description:We determine stability and attractor properties of random Boolean genetic network models with canalyzing rules for a variety of architectures. For all power law, exponential, and flat in-degree distributions, we find that the networks are dynamically stable. Furthermore, for architectures with few inputs per node, the dynamics of the networks is close to critical. In addition, the fraction of genes that are active decreases with the number of inputs per node. These results are based upon investigating ensembles of networks using analytical methods. Also, for different in-degree distributions, the numbers of fixed points and cycles are calculated, with results intuitively consistent with stability analysis; fewer inputs per node implies more cycles, and vice versa. There are hints that genetic networks acquire broader degree distributions with evolution, and hence our results indicate that for single cells, the dynamics should become more stable with evolution. However, such an effect is very likely compensated for by multicellular dynamics, because one expects less stability when interactions among cells are included. We verify this by simulations of a simple model for interactions among cells.
| S-EPMC534611 | biostudies-literature
Project description:Relational algebra (RA) comprises a basis of important operations, sufficient to power state-of-the-art reasoning engines for Datalog and related logic-programming languages. Parallel RA implementations can thus play a significant role in extracting parallelism inherent in a wide variety of analytic problems. In general, bottom-up logical inference can be implemented as fixed-point iteration over RA kernels; relations dynamically accumulate new tuples of information according to a set of rules until no new tuples can be discovered from previously inferred tuples and relevant rules (RA kernels). While this strategy has been quite successful in single-node contexts, it poses unique challenges when distributed over many-node, networked clusters—especially regarding how the work-load is balanced across available compute resources. In this paper, we identify two fundamental kinds of load imbalance and present a strategy to address each. We investigate both spatial load imbalance—imbalance across each relation (across compute nodes)—and temporal load imbalance–imbalance in tuples produced across fixed-point iterations. For spatial balancing, we implement refinement and consolidation procedures. For temporal balancing, we implement a technique that permits the residual workload from a busy iteration to roll over to a new iteration. In sum, these techniques permit fully dynamic load-balancing of relational algebra that is robust to changes across time.
| S-EPMC7295339 | biostudies-literature
Project description:A Boolean model is a simple, discrete and dynamic model without the need to consider the effects at the intermediate levels. However, little effort has been made into constructing activation, inhibition, and protein decay networks, which could indicate the direct roles of a gene (or its synthesized protein) as an activator or inhibitor of a target gene. Therefore, we propose to focus on the general Boolean functions at the subfunction level taking into account the effectiveness of protein decay, and further split the subfunctions into the activation and inhibition domains. As a consequence, we developed a novel data-driven Boolean model; namely, the Fundamental Boolean Model (FBM), to draw insights into gene activation, inhibition, and protein decay. This novel Boolean model provides an intuitive definition of activation and inhibition pathways and includes mechanisms to handle protein decay issues. To prove the concept of the novel model, we implemented a platform using R language, called FBNNet. Our experimental results show that the proposed FBM could explicitly display the internal connections of the mammalian cell cycle between genes separated into the connection types of activation, inhibition and protein decay. Moreover, the method we proposed to infer the gene regulatory networks for the novel Boolean model can be run in parallel and; hence, the computation cost is affordable. Finally, the novel Boolean model and related Fundamental Boolean Networks (FBNs) could show significant trajectories in genes to reveal how genes regulated each other over a given period. This new feature could facilitate further research on drug interventions to detect the side effects of a newly-proposed drug.
| S-EPMC6167558 | biostudies-literature
Project description:MotivationBiological processes are complex systems with distinct behaviour. Despite the growing amount of available data, knowledge is sparse and often insufficient to investigate the complex regulatory behaviour of these systems. Moreover, different cellular phenotypes are possible under varying conditions. Mathematical models attempt to unravel these mechanisms by investigating the dynamics of regulatory networks. Therefore, a major challenge is to combine regulations and phenotypical information as well as the underlying mechanisms. To predict regulatory links in these models, we established an approach called CANTATA to support the integration of information into regulatory networks and retrieve potential underlying regulations. This is achieved by optimizing both static and dynamic properties of these networks.ResultsInitial results show that the algorithm predicts missing interactions by recapitulating the known phenotypes while preserving the original topology and optimizing the robustness of the model. The resulting models allow for hypothesizing about the biological impact of certain regulatory dependencies.Availability and implementationSource code of the application, example files and results are available at https://github.com/sysbio-bioinf/Cantata.Supplementary informationSupplementary data are available at Bioinformatics online.
| S-EPMC9620829 | biostudies-literature
Project description:BackgroundRobert Rosen's Metabolism-Replacement, or (M,R), system can be represented as a compact network structure with a single source and three products derived from that source in three consecutive reactions. (M,R) has been claimed to be non-reducible to its components and algorithmically non-computable, in the sense of not being evaluable as a function by a Turing machine. If (M,R)-like structures are present in real biological networks, this suggests that many biological networks will be non-computable, with implications for those branches of systems biology that rely on in silico modelling for predictive purposes.ResultsWe instantiate (M,R) using the process algebra Bio-PEPA, and discuss the extent to which our model represents a true realization of (M,R). We observe that under some starting conditions and parameter values, stable states can be achieved. Although formal demonstration of algorithmic computability remains elusive for (M,R), we discuss the extent to which our Bio-PEPA representation of (M,R) allows us to sidestep Rosen's fundamental objections to computational systems biology.ConclusionsWe argue that the behaviour of (M,R) in Bio-PEPA shows life-like properties.
| S-EPMC3879122 | biostudies-literature
Project description:BackgroundSuperenhancers are crucial structural genomic elements determining cell fate, and they are also involved in the determination of several diseases, such as cancer or neurodegeneration. Although there are pipelines which use independent pieces of software to predict the presence of superenhancers from genome-wide chromatin marks or DNA-interaction protein binding sites, there is not yet an integrated software tool that processes automatically algebra combinations of raw data sequencing into a comprehensive final annotated report of predicted superenhancers.ResultsWe have developed NaviSE, a user-friendly streamlined tool which performs a fully-automated parallel processing of genome-wide epigenomics data from sequencing files into a final report, built with a comprehensive set of annotated files that are navigated through a graphic user interface dynamically generated by NaviSE. NaviSE also implements an 'epigenomics signal algebra' that allows the combination of multiple activation and repression epigenomics signals. NaviSE provides an interactive chromosomal landscaping of the locations of superenhancers, which can be navigated to obtain annotated information about superenhancer signal profile, associated genes, gene ontology enrichment analysis, motifs of transcription factor binding sites enriched in superenhancers, graphs of the metrics evaluating the superenhancers quality, protein-protein interaction networks and enriched metabolic pathways among other features. We have parallelised the most time-consuming tasks achieving a reduction up to 30% for a 15 CPUs machine. We have optimized the default parameters of NaviSE to facilitate its use. NaviSE allows different entry levels of data processing, from sra-fastq files to bed files; and unifies the processing of multiple replicates. NaviSE outperforms the more time-consuming processes required in a non-integrated pipeline. Alongside its high performance, NaviSE is able to provide biological insights, predicting cell type specific markers, such as SOX2 and ZIC3 in embryonic stem cells, CDK5R1 and REST in neurons and CD86 and TLR2 in monocytes.ConclusionsNaviSE is a user-friendly streamlined solution for superenhancer analysis, annotation and navigation, requiring only basic computer and next generation sequencing knowledge. NaviSE binaries and documentation are available at: https://sourceforge.net/projects/navise-superenhancer/ .
| S-EPMC5461685 | biostudies-literature
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