Optimal amnesic probabilistic automata or how to learn and classify proteins in linear time and space.

Statistical modeling of sequences is a central paradigm of machine learning that finds multiple uses in computational molecular biology and many other domains. The probabilistic automata typically built in these contexts are subtended by uniform, fixed-memory Markov models. In practice, such automata tend to be unnecessarily bulky and computationally imposing both during their synthesis and use. Recently, D. Ron, Y. Singer, and N. Tishby built much more compact, tree-shaped variants of probabilistic automata under the assumption of an underlying Markov process of variable memory length. These variants, called Probabilistic Suffix Trees (PSTs) were subsequently adapted by G. Bejerano and G. Yona and applied successfully to learning and prediction of protein families. The process of learning the automaton from a given training set S of sequences requires theta(Ln2) worst-case time, where n is the total length of the sequences in S and L is the length of a longest substring of S to be considered for a candidate state in the automaton. Once the automaton is built, predicting the likelihood of a query sequence of m characters may cost time theta(m2) in the worst case. The main contribution of this paper is to introduce automata equivalent to PSTs but having the following properties: Learning the automaton, for any L, takes O (n) time. Prediction of a string of m symbols by the automaton takes O (m) time. Along the way, the paper presents an evolving learning scheme and addresses notions of empirical probability and related efficient computation, which is a by-product possibly of more general interest.     

Differential dependence on DNA ligase of type II restriction enzymes: a practical way toward ligase-free DNA automaton

DNA computing study is a new paradigm in computer science and biological computing fields. As one of DNA computing approaches, DNA automaton is composed of the hardware, input DNA molecule and state transition molecules. By now restriction enzymes are key hardware for DNA computing automaton. It has been found that DNA computing efficiency may be independent on DNA ligases when type IIS restriction enzymes like FokI are used as hardware. In this study, we compared FokI with four other distinct enzymes HgaI, BsmFI, BbsI, and BseMII, and found their differential independence on T4 DNA ligase when performing automaton reactions. Since DNA automaton is a potential powerful tool to tackle gene relationship in genomic network scale, the feasible ligase-free DNA automaton may set an initial base to develop functional DNA automata for various DNA technology development and implications in genetics study in the near future.     

Combinatorial Properties of Some Cellular Automata Related to the Mosaic Cycle Concept

A cellular automaton that is related to the "mosaic cycle concept" is considered. We explain why such automata sustain very often, but not always, n-periodic trajectories (n being the number of states of the automaton). Our work is a first step in the direction of a theory of these type of automata which might be useful in modeling mosaic successions.     

Reliability of pattern separation by the cerebellar mossy fiber — granule cell system

As a simple example of a neuronal network in which synaptic connectivity among neurons is probabilistic, Marr's model for the granular layer of cat cerebellar cortex is examined. The mean and variance are computed for the fraction of granule cells activated, and for the extent of pattern separation by granule cells, for various mossy fiber inputs and various values of connectivity and electrical parameters of the network structure. Results suggest different functions for the network, and different optimal ranges for its parameters, depending on whether Golgi cells are present or absent. The model network does not perform the functions originally prescribed for it with high reliability.     

Predictability in Cellular Automata

Modelled as finite homogeneous Markov chains, probabilistic cellular automata with local transition probabilities in (0, 1) always posses a stationary distribution. This result alone is not very helpful when it comes to predicting the final configuration; one needs also a formula connecting the probabilities in the stationary distribution to some intrinsic feature of the lattice configuration. Previous results on the asynchronous cellular automata have showed that such feature really exists. It is the number of zero-one borders within the automaton''s binary configuration. An exponential formula in the number of zero-one borders has been proved for the 1-D, 2-D and 3-D asynchronous automata with neighborhood three, five and seven, respectively. We perform computer experiments on a synchronous cellular automaton to check whether the empirical distribution obeys also that theoretical formula. The numerical results indicate a perfect fit for neighbourhood three and five, which opens the way for a rigorous proof of the formula in this new, synchronous case.     

Evolved cellular automata for protein secondary structure prediction imitate the determinants for folding observed in nature

We demonstrate the first application of cellular automata to the secondary structure predictions of proteins. Cellular automata use localized interactions to simulate global phenomena, which resembles the protein folding problem where individual residues interact locally to define the global protein conformation. The protein's amino acid sequence was input into the cellular automaton and rules for updating states were evolved using a genetic algorithm. An optimized accuracy (Q3) for the RS126 and CB513 dataset of 58.21% and 56.51%, respectively, could be obtained. Thus, the current work demonstrates the applicability of a rather simple algorithm on a problem as complex as protein secondary structure prediction.     

Interacting with an artificial partner: modeling the role of emotional aspects

In this paper we introduce a simple model based on probabilistic finite state automata to describe an emotional interaction between a robot and a human user, or between simulated agents. Based on the agent’s personality, attitude, and nature, and on the emotional inputs it receives, the model will determine the next emotional state displayed by the agent itself. The probabilistic and time-varying nature of the model yields rich and dynamic interactions, and an autonomous adaptation to the interlocutor. In addition, a reinforcement learning technique is applied to have one agent drive its partner’s behavior toward desired states. The model may also be used as a tool for behavior analysis, by extracting high probability patterns of interaction and by resorting to the ergodic properties of Markov chains. An early stage part of this work was presented at the 11th International Conference on Knowledge-Based and Intelligent Information and Engineering Systems (KES 2007).     

Symbolic reachable set computation of piecewise affine hybrid automata and its application to biological modelling: Delta-Notch protein signalling

Hybrid automata are an eminently suitable modelling framework for biological protein regulatory networks, as the protein concentration dynamics inside each biological cell are modelled using linear differential equations; inputs activate or deactivate these continuous dynamics through discrete switches, which themselves are controlled by protein concentrations reaching given thresholds. This paper proposes an iterative refinement algorithm for computing discrete abstractions of a class of hybrid automata with piecewise affine continuous dynamics and forced discrete transitions, defined completely in terms of symbolic variables and parameters. Furthermore, these discrete abstractions are utilised to compute symbolic parametric backward reachable sets from the equilibria of the hybrid automata, that are guaranteed to be exact or conservative under-approximations. The algorithm is then implemented using MATLAB and QEPCAD, to compute reachable sets for the biologically observed equilibria of the multiple cell Delta-Notch protein signalling automaton with symbolic parameters. The results are analysed to show that novel, non-intuitive, and biologically interesting properties can be deduced from the reachability computation, thus demonstrating the utility of the algorithm.     

A hierarchical classification of first-order recurrent neural networks

We provide a decidable hierarchical classification of first-order recurrent neural networks made up of McCulloch and Pitts cells. This classification is achieved by proving an equivalence result between such neural networks and deterministic Büuchi automata, and then translating the Wadge classification theory from the abstract machine to the neural network context. The obtained hierarchy of neural networks is proved to have width 2 and height omega + 1, and a decidability procedure of this hierarchy is provided. Notably, this classification is shown to be intimately related to the attractive properties of the considered networks.     

Complex sensory-motor sequence learning based on recurrent state representation and reinforcement learning

 A novel neural network model is presented that learns by trial-and-error to reproduce complex sensory-motor sequences. One subnetwork, corresponding to the prefrontal cortex (PFC), is responsible for generating unique patterns of activity that represent the continuous state of sequence execution. A second subnetwork, corresponding to the striatum, associates these state-encoding patterns with the correct response at each point in the sequence execution. From a neuroscience perspective, the model is based on the known cortical and subcortical anatomy of the primate oculomotor system. From a theoretical perspective, the architecture is similar to that of a finite automaton in which outputs and state transitions are generated as a function of inputs and the current state. Simulation results for complex sequence reproduction and sequence discrimination are presented. Received: 21 July 1994/Accepted in revised form: 21 March 1995     

Automata with hierarchical control and evolutionary learning

We propose an automata-theoretical framework for structured hierarchical control, in terms of rules and meta-rules, for sequences of moves on a graph. This leads to a notion of a "universal" hierarchically structured automaton mu which can move on a given graph in such a way as to emulate any automaton which moves on that graph in response to inputs. This emulation is achieved via a mapping of the inputs in the given automaton to those of mu, and we think of such a mapping as an encoding of the given automaton. We see in several examples that efficient encodings of graph-search algorithms correspond to their natural hierarchical structure (in terms of rules and meta-rules), and this leads one to a precise notion of the "depth" of an automaton which moves on a given graph. By way of application, we discuss a proposed structure of a series of stochastic neural networks which can learn, by example, to encode a given sequence of moves on a graph, so that the encoding obtained is structurally the "natural" one for the given sequence of moves. Thus, such a learning system would perform both structural pattern recognition (in terms of "patterns" of moves), and encoding based on a desired outcome.     

Stochastic automaton models for the temporal pattern discrimination of nerve impulse sequences

The application of stochastic automata to the input-output relations of single neurons is considered. For this, some stochastic properties of temporal pattern discrimination in single synaptic cells are used to suggest stochastic automaton models. The models have only three possible states, the active, the absolute refractory and the relative refractory states, which are sufficient for temporal pattern sensitivity. From such an application, it was found that the temporal pattern discriminating structures in the models are similar to those used for experimental data and computer simulation (real-time neuron models). Extensions related to temporal pattern learning are discussed.     

Algebraic properties of automata associated to Petri nets and applications to computation in biological systems

Biochemical and genetic regulatory networks are often modeled by Petri nets. We study the algebraic structure of the computations carried out by Petri nets from the viewpoint of algebraic automata theory. Petri nets comprise a formalized graphical modeling language, often used to describe computation occurring within biochemical and genetic regulatory networks, but the semantics may be interpreted in different ways in the realm of automata. Therefore, there are several different ways to turn a Petri net into a state-transition automaton. Here, we systematically investigate different conversion methods and describe cases where they may yield radically different algebraic structures. We focus on the existence of group components of the corresponding transformation semigroups, as these reflect symmetries of the computation occurring within the biological system under study. Results are illustrated by applications to the Petri net modelling of intermediary metabolism. Petri nets with inhibition are shown to be computationally rich, regardless of the particular interpretation method. Along these lines we provide a mathematical argument suggesting a reason for the apparent all-pervasiveness of inhibitory connections in living systems.     

Empirical and deterministic accuracies of across-population genomic prediction

Background

Differences in linkage disequilibrium and in allele substitution effects of QTL (quantitative trait loci) may hinder genomic prediction across populations. Our objective was to develop a deterministic formula to estimate the accuracy of across-population genomic prediction, for which reference individuals and selection candidates are from different populations, and to investigate the impact of differences in allele substitution effects across populations and of the number of QTL underlying a trait on the accuracy.

Methods

A deterministic formula to estimate the accuracy of across-population genomic prediction was derived based on selection index theory. Moreover, accuracies were deterministically predicted using a formula based on population parameters and empirically calculated using simulated phenotypes and a GBLUP (genomic best linear unbiased prediction) model. Phenotypes of 1033 Holstein-Friesian, 105 Groninger White Headed and 147 Meuse-Rhine-Yssel cows were simulated by sampling 3000, 300, 30 or 3 QTL from the available high-density SNP (single nucleotide polymorphism) information of three chromosomes, assuming a correlation of 1.0, 0.8, 0.6, 0.4, or 0.2 between allele substitution effects across breeds. The simulated heritability was set to 0.95 to resemble the heritability of deregressed proofs of bulls.

Results

Accuracies estimated with the deterministic formula based on selection index theory were similar to empirical accuracies for all scenarios, while accuracies predicted with the formula based on population parameters overestimated empirical accuracies by ~25 to 30%. When the between-breed genetic correlation differed from 1, i.e. allele substitution effects differed across breeds, empirical and deterministic accuracies decreased in proportion to the genetic correlation. Using a multi-trait model, it was possible to accurately estimate the genetic correlation between the breeds based on phenotypes and high-density genotypes. The number of QTL underlying the simulated trait did not affect the accuracy.

Conclusions

The deterministic formula based on selection index theory estimated the accuracy of across-population genomic predictions well. The deterministic formula using population parameters overestimated the across-population genomic accuracy, but may still be useful because of its simplicity. Both formulas could accommodate for genetic correlations between populations lower than 1. The number of QTL underlying a trait did not affect the accuracy of across-population genomic prediction using a GBLUP method.