Controlled synthesis of target strings in a class of splicing systems

This article presents an approach for synthesizing target strings in a class of computational models of DNA recombination. The computational models are formalized as splicing systems in the context of formal languages. Given a splicing system (of a restricted type) and a target string to be synthesized, we construct (i) a rule-embedded splicing automaton that recognizes languages containing strings embedded with symbols representing splicing rules, and (ii) an automaton that implicitly recognizes the target string. By manipulating these two automata, we extract all rule sequences that lead to the production of the target string (if that string belongs to the splicing language). An algorithm for synthesizing a certain type of target strings based on such rule sequences is presented.     

A modified Ising model of Barabási–Albert network with gene-type spins

The central question of systems biology is to understand how individual components of a biological system such as genes or proteins cooperate in emerging phenotypes resulting in the evolution of diseases. As living cells are open systems in quasi-steady state type equilibrium in continuous exchange with their environment, computational techniques that have been successfully applied in statistical thermodynamics to describe phase transitions may provide new insights to the emerging behavior of biological systems. Here we systematically evaluate the translation of computational techniques from solid-state physics to network models that closely resemble biological networks and develop specific translational rules to tackle problems unique to living systems. We focus on logic models exhibiting only two states in each network node. Motivated by the apparent asymmetry between biological states where an entity exhibits boolean states i.e. is active or inactive, we present an adaptation of symmetric Ising model towards an asymmetric one fitting to living systems here referred to as the modified Ising model with gene-type spins. We analyze phase transitions by Monte Carlo simulations and propose a mean-field solution of a modified Ising model of a network type that closely resembles a real-world network, the Barabási–Albert model of scale-free networks. We show that asymmetric Ising models show similarities to symmetric Ising models with the external field and undergoes a discontinuous phase transition of the first-order and exhibits hysteresis. The simulation setup presented herein can be directly used for any biological network connectivity dataset and is also applicable for other networks that exhibit similar states of activity. The method proposed here is a general statistical method to deal with non-linear large scale models arising in the context of biological systems and is scalable to any network size.

     

Lewis Carroll's Doublets Net of English Words: Network Heterogeneity in a Complex System

Lewis Carroll''s English word game Doublets is represented as a system of networks with each node being an English word and each connectivity edge confirming that its two ending words are equal in letter length, but different by exactly one letter. We show that this system, which we call the Doublets net, constitutes a complex body of linguistic knowledge concerning English word structure that has computable multiscale features. Distributed morphological, phonological and orthographic constraints and the language''s local redundancy are seen at the node level. Phonological communities are seen at the network level. And a balancing act between the language''s global efficiency and redundancy is seen at the system level. We develop a new measure of intrinsic node-to-node distance and a computational algorithm, called community geometry, which reveal the implicit multiscale structure within binary networks. Because the Doublets net is a modular complex cognitive system, the community geometry and computable multi-scale structural information may provide a foundation for understanding computational learning in many systems whose network structure has yet to be fully analyzed.     

Matching Rules for Collective Behaviors on Complex Networks: Optimal Configurations for Vibration Frequencies of Networked Harmonic Oscillators

The structure-dynamics-function has become one of central problems in modern sciences, and it is a great challenge to unveil the organization rules for different dynamical processes on networks. In this work, we study the vibration spectra of the classical mass spring model with different masses on complex networks, and pay our attention to how the mass spatial configuration influences the second-smallest vibrational frequency () and the largest one (). For random networks, we find that becomes maximal and becomes minimal if the node degrees are point-to-point-positively correlated with the masses. In these cases, we call it point-to-point matching. Moreover, becomes minimal under the condition that the heaviest mass is placed on the lowest-degree vertex, and is maximal as long as the lightest mass is placed on the highest-degree vertex, and in both cases all other masses can be arbitrarily settled. Correspondingly, we call it single-point matching. These findings indicate that the matchings between the node dynamics (parameter) and the node position rule the global systems dynamics, and sometimes only one node is enough to control the collective behaviors of the whole system. Therefore, the matching rules might be the common organization rules for collective behaviors on networks.     

The Rutgers Computational Grid: A Distributed Linux PC Cluster

The Rutgers Computational Grid (RCG) project is aimed at providing high throughput performance to Rutgers university faculty and students. The RCG employs dual processor PCs, with Pentium II and III processors, as computational nodes, running the Linux RedHat operating system. The Load Sharing Facility (LSF) scheduling system from Platform Computing is used for job control and monitoring. The nodes are grouped into subclusters physically located in several departments and controlled by a single master node through LSF. The hardware and software used in RCG are described. Utilization and performance issues, including parallel performance, are discussed based on the experience of the first two years of RCG operation.     

RNA secondary structure mediates alternative 3'ss selection in Saccharomyces cerevisiae

Alternative splicing is the mechanism by which different combinations of exons in the pre-mRNA give rise to distinct mature mRNAs. This process is mediated by splicing factors that bind the pre-mRNA and affect the recognition of its splicing signals. Saccharomyces species lack many of the regulatory factors present in metazoans. Accordingly, it is generally assumed that the amount of alternative splicing is limited. However, there is recent compelling evidence that yeast have functional alternative splicing, mainly in response to environmental conditions. We have previously shown that sequence and structure properties of the pre-mRNA could explain the selection of 3' splice sites (ss) in Saccharomyces cerevisiae. In this work, we extend our previous observations to build a computational classifier that explains most of the annotated 3'ss in the CDS and 5' UTR of this organism. Moreover, we show that the same rules can explain the selection of alternative 3'ss. Experimental validation of a number of predicted alternative 3'ss shows that their usage is low compared to annotated 3'ss. The majority of these alternative 3'ss introduce premature termination codons (PTCs), suggesting a role in expression regulation. Furthermore, a genome-wide analysis of the effect of temperature, followed by experimental validation, yields only a small number of changes, indicating that this type of regulation is not widespread. Our results are consistent with the presence of alternative 3'ss selection in yeast mediated by the pre-mRNA structure, which can be responsive to external cues, like temperature, and is possibly related to the control of gene expression.     

Multiset splicing systems

We consider splicing systems reflecting two important aspects of the behaviour of DNA molecules in nature or in laboratory experiments which so far have not been studied in the literature. We examine the effect of splicing rules applied to finite multisets of words using sequential and different types of parallel derivation strategies and compare the sets of words or sets of multisets which can be obtained.     

Computational mate choice: theory and empirical evidence

The present review is based on the thesis that mate choice results from information-processing mechanisms governed by computational rules and that, to understand how females choose their mates, we should identify which are the sources of information and how they are used to make decisions. We describe mate choice as a three-step computational process and for each step we present theories and review empirical evidence. The first step is a perceptual process. It describes the acquisition of evidence, that is, how females use multiple cues and signals to assign an attractiveness value to prospective mates (the preference function hypothesis). The second step is a decisional process. It describes the construction of the decision variable (DV), which integrates evidence (private information by direct assessment), priors (public information), and value (perceived utility) of prospective mates into a quantity that is used by a decision rule (DR) to produce a choice. We make the assumption that females are optimal Bayesian decision makers and we derive a formal model of DV that can explain the effects of preference functions, mate copying, social context, and females' state and condition on the patterns of mate choice. The third step of mating decision is a deliberative process that depends on the DRs. We identify two main categories of DRs (absolute and comparative rules), and review the normative models of mate sampling tactics associated to them. We highlight the limits of the normative approach and present a class of computational models (sequential-sampling models) that are based on the assumption that DVs accumulate noisy evidence over time until a decision threshold is reached. These models force us to rethink the dichotomy between comparative and absolute decision rules, between discrimination and recognition, and even between rational and irrational choice. Since they have a robust biological basis, we think they may represent a useful theoretical tool for behavioural ecologist interested in integrating proximate and ultimate causes of mate choice.     

Dynamic Artificial Neural Networks with Affective Systems

Artificial neural networks (ANNs) are processors that are trained to perform particular tasks. We couple a computational ANN with a simulated affective system in order to explore the interaction between the two. In particular, we design a simple affective system that adjusts the threshold values in the neurons of our ANN. The aim of this paper is to demonstrate that this simple affective system can control the firing rate of the ensemble of neurons in the ANN, as well as to explore the coupling between the affective system and the processes of long term potentiation (LTP) and long term depression (LTD), and the effect of the parameters of the affective system on its performance. We apply our networks with affective systems to a simple pole balancing example and briefly discuss the effect of affective systems on network performance.     

Mutations and Lethality in Simulated Prebiotic Networks

The Graded Autocatalysis Replication Domain (GARD) model describes an origin of life scenario which involves non-covalent compositional assemblies, made of monomeric mutually catalytic molecules. GARD constitutes an alternative to informational biopolymers as a mechanism of primordial inheritance. In the present work, we examined the effect of mutations, one of the most fundamental mechanisms for evolution, in the context of the networks of mutual interaction within GARD prebiotic assemblies. We performed a systematic analysis analogous to single and double gene deletions within GARD. While most deletions have only a small effect on both growth rate and molecular composition of the assemblies, ~10% of the deletions caused lethality, or sometimes showed enhanced fitness. Analysis of 14 different network properties on 2,000 different GARD networks indicated that lethality usually takes place when the deleted node has a high molecular count, or when it is a catalyst for such node. A correlation was also found between lethality and node degree centrality, similar to what is seen in real biological networks. Addressing double knockout mutations, our results demonstrate the occurrence of both synthetic lethality and extragenic suppression within GARD networks, and convey an attempt to correlate synthetic lethality to network node-pair properties. The analyses presented help establish GARD as a workable alternative prebiotic scenario, suggesting that life may have begun with large molecular networks of low fidelity, that later underwent evolutionary compaction and fidelity augmentation.     

Association pattern mining of intron retention events in human based on hybrid learning machine

Alternative splicing is a main component of protein diversity, and aberrant splicing is known to be one of the main causes of genetic disorders such as cancer. Many statistical and computational approaches have identified several major factors that determine the splicing event, such as exon/intron length, splice site strength, and density of splicing enhancers or silencers. These factors may be correlated with one another and thus result in a specific type of splicing, but there has not been a systematic approach to extracting comprehensible association patterns. Here, we attempted to understand the decision making process of the learning machine on intron retention event. We adopted a hybrid learning machine approach using a random forest and association rule mining algorithm to determine the governing factors of intron retention events and their combined effect on decision-making processes. By quantifying all candidate features into five category values, we enhanced the understandability of generated rules. The interesting features found by the random forest algorithm are that only the adenine- and thymine-based triplets such as ATA, TTA, and ATT, but not the known intronic splicing enhancer GGG triplet is shown the significant features. The rules generated by the association rule mining algorithm also show that constitutive introns are generally characterized by high adenine- and thymine-based triplet frequency (level 3 and above), 3' and 5' splice site scores, exonic splicing silencer scores, and intron length, whereas retained introns are characterized by low-level counterpart scores.     

Reverse Engineering Boolean Networks: From Bernoulli Mixture Models to Rule Based Systems

A Boolean network is a graphical model for representing and analyzing the behavior of gene regulatory networks (GRN). In this context, the accurate and efficient reconstruction of a Boolean network is essential for understanding the gene regulation mechanism and the complex relations that exist therein. In this paper we introduce an elegant and efficient algorithm for the reverse engineering of Boolean networks from a time series of multivariate binary data corresponding to gene expression data. We call our method ReBMM, i.e., reverse engineering based on Bernoulli mixture models. The time complexity of most of the existing reverse engineering techniques is quite high and depends upon the indegree of a node in the network. Due to the high complexity of these methods, they can only be applied to sparsely connected networks of small sizes. ReBMM has a time complexity factor, which is independent of the indegree of a node and is quadratic in the number of nodes in the network, a big improvement over other techniques and yet there is little or no compromise in accuracy. We have tested ReBMM on a number of artificial datasets along with simulated data derived from a plant signaling network. We also used this method to reconstruct a network from real experimental observations of microarray data of the yeast cell cycle. Our method provides a natural framework for generating rules from a probabilistic model. It is simple, intuitive and illustrates excellent empirical results.     

Discovering adaptation-capable biological network structures using control-theoretic approaches

Constructing biological networks capable of performing specific biological functionalities has been of sustained interest in synthetic biology. Adaptation is one such ubiquitous functional property, which enables every living organism to sense a change in its surroundings and return to its operating condition prior to the disturbance. In this paper, we present a generic systems theory-driven method for designing adaptive protein networks. First, we translate the necessary qualitative conditions for adaptation to mathematical constraints using the language of systems theory, which we then map back as ‘design requirements’ for the underlying networks. We go on to prove that a protein network with different input–output nodes (proteins) needs to be at least of third-order in order to provide adaptation. Next, we show that the necessary design principles obtained for a three-node network in adaptation consist of negative feedback or a feed-forward realization. We argue that presence of a particular class of negative feedback or feed-forward realization is necessary for a network of any size to provide adaptation. Further, we claim that the necessary structural conditions derived in this work are the strictest among the ones hitherto existed in the literature. Finally, we prove that the capability of producing adaptation is retained for the admissible motifs even when the output node is connected with a downstream system in a feedback fashion. This result explains how complex biological networks achieve robustness while keeping the core motifs unchanged in the context of a particular functionality. We corroborate our theoretical results with detailed and thorough numerical simulations. Overall, our results present a generic, systematic and robust framework for designing various kinds of biological networks.     

Minigene reporter for identification and analysis of cis elements and trans factors affecting pre-mRNA splicing

All human genes contain a diverse array of cis-acting elements within introns and exons that are required for correct and efficient precursor messenger RNA (pre-mRNA) splicing. Recent computational analyses predict that most human exons contain elements required for splicing coinciding with an appreciation for the high frequency with which mutations that disruption pre-mRNA splicing cause disease. Minigenes provide a means to directly determine whether disease-causing mutations or single nucleotide polymorphisms (SNPs) affect splicing efficiency. Minigenes have also been instrumental in investigations of alternative splicing to identify cis elements required for cell-specific splicing events, demonstrating regulation of individual splicing events by specific RNA binding proteins, and correlating binding of these splicing regulators with splicing regulation. Here we present a versatile minigene plasmid vector designed for rapid cloning and analysis of cis elements and trans-acting factors that influence splicing efficiency or regulate cell-specific splicing. Ubiquitous expression and unique restriction sites allow for straightforward replacement of a variety of gene segments to analyze the effects of nucleotide substitutions on splicing, to identify tissue-specific regulatory elements, or to determine responsiveness to coexpressed proteins or small molecules.     

Evolution of Alternative Splicing Regulation: Changes in Predicted Exonic Splicing Regulators Are Not Associated with Changes in Alternative Splicing Levels in Primates

Alternative splicing is tightly regulated in a spatio-temporal and quantitative manner. This regulation is achieved by a complex interplay between spliceosomal (trans) factors that bind to different sequence (cis) elements. cis-elements reside in both introns and exons and may either enhance or silence splicing. Differential combinations of cis-elements allows for a huge diversity of overall splicing signals, together comprising a complex ‘splicing code’. Many cis-elements have been identified, and their effects on exon inclusion levels demonstrated in reporter systems. However, the impact of interspecific differences in these elements on the evolution of alternative splicing levels has not yet been investigated at genomic level. Here we study the effect of interspecific differences in predicted exonic splicing regulators (ESRs) on exon inclusion levels in human and chimpanzee. For this purpose, we compiled and studied comprehensive datasets of predicted ESRs, identified by several computational and experimental approaches, as well as microarray data for changes in alternative splicing levels between human and chimpanzee. Surprisingly, we found no association between changes in predicted ESRs and changes in alternative splicing levels. This observation holds across different ESR exon positions, exon lengths, and 5′ splice site strengths. We suggest that this lack of association is mainly due to the great importance of context for ESR functionality: many ESR-like motifs in primates may have little or no effect on splicing, and thus interspecific changes at short-time scales may primarily occur in these effectively neutral ESRs. These results underscore the difficulties of using current computational ESR prediction algorithms to identify truly functionally important motifs, and provide a cautionary tale for studies of the effect of SNPs on splicing in human disease.     

Network Reconstruction Using Nonparametric Additive ODE Models

Network representations of biological systems are widespread and reconstructing unknown networks from data is a focal problem for computational biologists. For example, the series of biochemical reactions in a metabolic pathway can be represented as a network, with nodes corresponding to metabolites and edges linking reactants to products. In a different context, regulatory relationships among genes are commonly represented as directed networks with edges pointing from influential genes to their targets. Reconstructing such networks from data is a challenging problem receiving much attention in the literature. There is a particular need for approaches tailored to time-series data and not reliant on direct intervention experiments, as the former are often more readily available. In this paper, we introduce an approach to reconstructing directed networks based on dynamic systems models. Our approach generalizes commonly used ODE models based on linear or nonlinear dynamics by extending the functional class for the functions involved from parametric to nonparametric models. Concomitantly we limit the complexity by imposing an additive structure on the estimated slope functions. Thus the submodel associated with each node is a sum of univariate functions. These univariate component functions form the basis for a novel coupling metric that we define in order to quantify the strength of proposed relationships and hence rank potential edges. We show the utility of the method by reconstructing networks using simulated data from computational models for the glycolytic pathway of Lactocaccus Lactis and a gene network regulating the pluripotency of mouse embryonic stem cells. For purposes of comparison, we also assess reconstruction performance using gene networks from the DREAM challenges. We compare our method to those that similarly rely on dynamic systems models and use the results to attempt to disentangle the distinct roles of linearity, sparsity, and derivative estimation.     

Predicting biological networks from genomic data

Continuing improvements in DNA sequencing technologies are providing us with vast amounts of genomic data from an ever-widening range of organisms. The resulting challenge for bioinformatics is to interpret this deluge of data and place it back into its biological context. Biological networks provide a conceptual framework with which we can describe part of this context, namely the different interactions that occur between the molecular components of a cell. Here, we review the computational methods available to predict biological networks from genomic sequence data and discuss how they relate to high-throughput experimental methods.     

Network analysis of reverse phase protein expression data: characterizing protein signatures in acute myeloid leukemia cytogenetic categories t(8;21) and inv(16)

Acute myeloid leukemia (AML) patients present with cancerous cells originating from bone marrow. Proteomic data on AML patient cells provides critical information on the key molecules associated with the disease. Here, we introduce a new computational approach to identify complex patterns in protein signaling from reverse phase protein array data. We analyzed the expression of 203 proteins in cells taken from AML patients. Dominant overlapping protein networks between subtypes of AML patients were characterized computationally, through a paired t-test approach looking at relative protein expression. In the first application of this method, we compared recurrent cytogenetic abnormalities inv(16) and t(8;21), both affecting core-binding factor (CBFβ), to normal CD34(+) cells and to each other. Six hundred seventy-eight sets of proteins were identified as significantly different in both inv(16) and t(8;21) compared to controls, at the Bonferroni number, α < 2.44 × 10(-6) . We strengthened our predictions by comparing results to those obtained using lasso regression analysis. Signaling networks were constructed from the protein pairs that were significantly different in the t-test and lasso regression analysis. Predicted networks were also compared to known networks from public protein-protein interaction and signaling databases. By characterizing unique "protein signatures" through this rapid computational analysis, and placing them in the context of canonical biological networks, we identify signaling pathways distinct to subcategories of AML patients.     

A neural network approach to approximating MAP in belief networks

Bayesian belief networks (BBN) are a widely studied graphical model for representing uncertainty and probabilistic interdependence among variables. One of the factors that restricts the model's wide acceptance in practical applications is that the general inference with BBN is NP-hard. This is also true for the maximum a posteriori probability (MAP) problem, which is to find the most probable joint value assignment to all uninstantiated variables, given instantiation of some variables in a BBN. To circumvent the difficulty caused by MAP's computational complexity, we suggest in this paper a neural network approximation approach. With this approach, a BBN is treated as a neural network without any change or transformation of the network structure, and the node activation functions are derived based on an energy function defined over a given BBN. Three methods are developed. They are the hill-climbing style discrete method, the simulated annealing method, and the continuous method based on the mean field theory. All three methods are for BBN of general structures, with the restriction that nodes of BBN are binary variables. In addition, rules for applying these methods to noisy-or networks are also developed, which may lead to more efficient computation in some cases. These methods' convergence is analyzed, and their validity tested through a series of computer experiments with two BBN of moderate size and complexity. Although additional theoretical and empirical work is needed, the analysis and experiments suggest that this approach may lead to effective and accurate approximation for MAP problems.