Generalizing HMMs to Continuous Time for Fast Kinetics: Hidden Markov Jump Processes

The hidden Markov model (HMM) is a framework for time series analysis widely applied to single-molecule experiments. Although initially developed for applications outside the natural sciences, the HMM has traditionally been used to interpret signals generated by physical systems, such as single molecules, evolving in a discrete state space observed at discrete time levels dictated by the data acquisition rate. Within the HMM framework, transitions between states are modeled as occurring at the end of each data acquisition period and are described using transition probabilities. Yet, whereas measurements are often performed at discrete time levels in the natural sciences, physical systems evolve in continuous time according to transition rates. It then follows that the modeling assumptions underlying the HMM are justified if the transition rates of a physical process from state to state are small as compared to the data acquisition rate. In other words, HMMs apply to slow kinetics. The problem is, because the transition rates are unknown in principle, it is unclear, a priori, whether the HMM applies to a particular system. For this reason, we must generalize HMMs for physical systems, such as single molecules, because these switch between discrete states in “continuous time”. We do so by exploiting recent mathematical tools developed in the context of inferring Markov jump processes and propose the hidden Markov jump process. We explicitly show in what limit the hidden Markov jump process reduces to the HMM. Resolving the discrete time discrepancy of the HMM has clear implications: we no longer need to assume that processes, such as molecular events, must occur on timescales slower than data acquisition and can learn transition rates even if these are on the same timescale or otherwise exceed data acquisition rates.     

Bayesian estimators for conditional hazard functions

This article introduces a new Bayesian approach to the analysis of right-censored survival data. The hazard rate of interest is modeled as a product of conditionally independent stochastic processes corresponding to (1) a baseline hazard function and (2) a regression function representing the temporal influence of the covariates. These processes jump at times that form a time-homogeneous Poisson process and have a pairwise dependency structure for adjacent values. The two processes are assumed to be conditionally independent given their jump times. Features of the posterior distribution, such as the mean covariate effects and survival probabilities (conditional on the covariate), are evaluated using the Metropolis-Hastings-Green algorithm. We illustrate our methodology by an application to nasopharynx cancer survival data.     

A Discrete Fruit Fly Optimization Algorithm for the Traveling Salesman Problem

The fruit fly optimization algorithm (FOA) is a newly developed bio-inspired algorithm. The continuous variant version of FOA has been proven to be a powerful evolutionary approach to determining the optima of a numerical function on a continuous definition domain. In this study, a discrete FOA (DFOA) is developed and applied to the traveling salesman problem (TSP), a common combinatorial problem. In the DFOA, the TSP tour is represented by an ordering of city indices, and the bio-inspired meta-heuristic search processes are executed with two elaborately designed main procedures: the smelling and tasting processes. In the smelling process, an effective crossover operator is used by the fruit fly group to search for the neighbors of the best-known swarm location. During the tasting process, an edge intersection elimination (EXE) operator is designed to improve the neighbors of the non-optimum food location in order to enhance the exploration performance of the DFOA. In addition, benchmark instances from the TSPLIB are classified in order to test the searching ability of the proposed algorithm. Furthermore, the effectiveness of the proposed DFOA is compared to that of other meta-heuristic algorithms. The results indicate that the proposed DFOA can be effectively used to solve TSPs, especially large-scale problems.     

ABC-X: a generalized,automatically configurable artificial bee colony framework

The artificial bee colony (ABC) algorithm is a popular metaheuristic that was originally conceived for tackling continuous function optimization tasks. Over the last decade, a large number of variants of ABC have been proposed, making it by now a well-studied swarm intelligence algorithm. Typically, in a paper on algorithmic variants of ABC algorithms, one or at most two of its algorithmic components are modified. Possible changes include variations on the search equations, the selection of candidate solutions to be explored, or the adoption of features from other algorithmic techniques. In this article, we propose to follow a different direction and to build a generalized ABC algorithm, which we call ABC-X. ABC-X collects algorithmic components available from known ABC algorithms into a common algorithm framework that allows not only to instantiate known ABC variants but, more importantly, also many ABC algorithm variants that have never been explored before in the literature. Automatic algorithm configuration techniques can generate from this template new ABC variants that perform better than known ABC algorithms, even when their numerical parameters are fine-tuned using the same automatic configuration process.     

Models of dispersal in biological systems

In order to provide a general framework within which the dispersal of cells or organisms can be studied, we introduce two stochastic processes that model the major modes of dispersal that are observed in nature. In the first type of movement, which we call the position jump or kangaroo process, the process comprises a sequence of alternating pauses and jumps. The duration of a pause is governed by a waiting time distribution, and the direction and distance traveled during a jump is fixed by the kernel of an integral operator that governs the spatial redistribution. Under certain assumptions concerning the existence of limits as the mean step size goes to zero and the frequency of stepping goes to infinity the process is governed by a diffusion equation, but other partial differential equations may result under different assumptions. The second major type of movement leads to what we call a velocity jump process. In this case the motion consists of a sequence of runs separated by reorientations, during which a new velocity is chosen. We show that under certain assumptions this process leads to a damped wave equation called the telegrapher's equation. We derive explicit expressions for the mean squared displacement and other experimentally observable quantities. Several generalizations, including the incorporation of a resting time between movements, are also studied. The available data on the motion of cells and other organisms is reviewed, and it is shown how the analysis of such data within the framework provided here can be carried out.Supported in part by NIH Grant #GM 29123 and by NSF Grant #DMS-8301840Supported in part by NSF Grant #DMS-8301840Supported in part by the DFG Heisenberg Program     

A neutral model of edge effects

In this paper a spatially implicit neutral model for explaining the edge effects between habitats is proposed. To analyze this model we use two different approaches: a discrete approach that is based on the Master equation for a one step jump process and a continuous approach based on the approximation of the discrete jump process with the Kolmogorov-Fokker-Planck forward and backward equations. The discrete and continuous approaches are applied to analyze the species abundance distributions and the time to species extinction. Moreover, with the aid of the continuous approach a realistic classification of the behavior of species in local communities is developed. The species abundance dynamics at the edge between two distinct habitats is compared with those located in the homogeneous interior habitats using species abundance distributions and the first time to species extinction. We show that the structure of the links between local community and the metacommunity plays an important role on species persistence. Specifically, species at the edge between two distinct metacommunities have higher extinction rate than those in the interior habitats connected only to one metacommunity. Moreover, the same species might be persistent in the homogeneous interior habitat, but its probability of extinction from the edge local community could be very high.     

Mathematical models of eye movements in reading: a possible role for autonomous saccades

 An efficient method for the exact numerical simulation of semi-Markov processes is used to study minimal models of the control of eye movements in reading. When we read a text, typical sequences of fixations form a rather complicated trajectory – almost like a random walk. Mathematical models of eye movement control can account for this behavior using stochastic transition rules between few discrete internal states, which represent combinations of certain stages of lexical access and saccade programs. We show that experimentally observed fixation durations can be explained by residence-time-dependent transition probabilities. Stochastic processes with this property are known as semi-Markov processes. For our numerical simulations we use the minimal process method (Gillespie algorithm), which is an exact and efficient simulation algorithm for this class of stochastic processes. Within this mathematical framework, we study different forms of coupling between eye movements and shifts of covert attention in reading. Our model lends support to the existence of autonomous saccades, i.e., the hypothesis that initiations of saccades are not completely determined by lexical access processes. Received: 21 March 2000 / Accepted in revised form: 10 January 2001     

Continuous hidden process model for time series expression experiments

MOTIVATION: When analyzing expression experiments, researchers are often interested in identifying the set of biological processes that are up- or down-regulated under the experimental condition studied. Current approaches, including clustering expression profiles and averaging the expression profiles of genes known to participate in specific processes, fail to provide an accurate estimate of the activity levels of many biological processes. RESULTS: We introduce a probabilistic continuous hidden process Model (CHPM) for time series expression data. CHPM can simultaneously determine the most probable assignment of genes to processes and the level of activation of these processes over time. To estimate model parameters, CHPM uses multiple time series datasets and incorporates prior biological knowledge. Applying CHPM to yeast expression data, we show that our algorithm produces more accurate functional assignments for genes compared to other expression analysis methods. The inferred process activity levels can be used to study the relationships between biological processes. We also report new biological experiments confirming some of the process activity levels predicted by CHPM. AVAILABILITY: A Java implementation is available at http:\\www.cs.cmu.edu\~yanxins\chpm. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.     

A discrete space model for continuous space dispersal processes

The simulation of dispersal processes in landscapes over large spatial extents is challenging because of the large difference in geographical scale between overwhelmingly dominant localised dispersal events, and rare long-distance dispersal events which typically drive overall rates of spread. While localised dispersal may point to high resolution individual level models, long-distance dispersal events are likely to involve much coarser grid-based models. In this paper we propose a discrete space (i.e., grid-based) model for dispersal processes in continuous space. We start by illustrating the behaviour of continuous space walks when their movement is discretised to a grid. The importance of short time period cell-to-cell moves which return a walk to its previous grid cell location is identified. A conceptual model which uses a Markov chain buffer phase between cells to replicate the observed behaviour of discretised continuous space walks is proposed. Analysis of the Markov chain shows that it can be parameterised using just two parameters in addition to the dispersal kernel. An algorithm for implementation of the proposed model is presented. Empirical results demonstrate that the proposed mechanism produces good matches to continuous space dispersal processes with both exponential and heavy-tailed dispersal kernels.     

Hybrid simulation of cellular behavior

MOTIVATION: To be valuable to biological or biomedical research, in silico methods must be scaled to complex pathways and large numbers of interacting molecular species. The correct method for performing such simulations, discrete event simulation by Monte Carlo generation, is computationally costly for large complex systems. Approximation of molecular behavior by continuous models fails to capture stochastic behavior that is essential to many biological phenomena. RESULTS: We present a novel approach to building hybrid simulations in which some processes are simulated discretely, while other processes are handled in a continuous simulation by differential equations. This approach preserves the stochastic behavior of cellular pathways, yet enables scaling to large populations of molecules. We present an algorithm for synchronizing data in a hybrid simulation and discuss the trade-offs in such simulation. We have implemented the hybrid simulation algorithm and have validated it by simulating the statistical behavior of the well-known lambda phage switch. Hybrid simulation provides a new method for exploring the sources and nature of stochastic behavior in cells.     

A Multi-stage Representation of Cell Proliferation as a Markov Process

The stochastic simulation algorithm commonly known as Gillespie’s algorithm (originally derived for modelling well-mixed systems of chemical reactions) is now used ubiquitously in the modelling of biological processes in which stochastic effects play an important role. In well-mixed scenarios at the sub-cellular level it is often reasonable to assume that times between successive reaction/interaction events are exponentially distributed and can be appropriately modelled as a Markov process and hence simulated by the Gillespie algorithm. However, Gillespie’s algorithm is routinely applied to model biological systems for which it was never intended. In particular, processes in which cell proliferation is important (e.g. embryonic development, cancer formation) should not be simulated naively using the Gillespie algorithm since the history-dependent nature of the cell cycle breaks the Markov process. The variance in experimentally measured cell cycle times is far less than in an exponential cell cycle time distribution with the same mean.Here we suggest a method of modelling the cell cycle that restores the memoryless property to the system and is therefore consistent with simulation via the Gillespie algorithm. By breaking the cell cycle into a number of independent exponentially distributed stages, we can restore the Markov property at the same time as more accurately approximating the appropriate cell cycle time distributions. The consequences of our revised mathematical model are explored analytically as far as possible. We demonstrate the importance of employing the correct cell cycle time distribution by recapitulating the results from two models incorporating cellular proliferation (one spatial and one non-spatial) and demonstrating that changing the cell cycle time distribution makes quantitative and qualitative differences to the outcome of the models. Our adaptation will allow modellers and experimentalists alike to appropriately represent cellular proliferation—vital to the accurate modelling of many biological processes—whilst still being able to take advantage of the power and efficiency of the popular Gillespie algorithm.     

A numerical algorithm for investigating the role of the motor-cargo linkage in molecular motor-driven transport

We extend the numerical algorithm developed by Wang et al. (2003. J. Theor. Biol. 221, 491-511) for studying biomolecular transport processes to include the linkage that connects molecular motors to their cargo. The new algorithm is used to investigate how the stiffness of the linkage affects the average velocity, effective diffusion coefficient, and randomness parameter. Three different models for molecular motors are considered: (1) a discrete stepping motor (2) a motor moving in a tilted-periodic potential and (3) a motor driven by a flashing potential. We demonstrate that a flexible motor-cargo linkage can make inferences on motor behavior based on measurements of the cargo's position difficult. We also show that even for the case of a tilted-periodic potential there exists an optimal stiffness of the linkage at which transport is maximized. The MATLAB code used in this paper is available at: http://www.unc.edu/approximatelytelston/code/.     

Simultaneous saccharification and continuous fermentation of sludge-containing mash for bioethanol production by Saccharomyces cerevisiae CHFY0321

A continuous process was employed to improve the volumetric productivity of bioethanol production from cassava mash containing sludge and to simplify the process of ethanol production from cassava. After raw cassava powder was liquefied, it was used directly in a continuous process without sludge filtration or saccharification. A fermentor consisting of four linked stirrer tanks was used for simultaneous saccharification and continuous fermentation (SSCF). Although the mash contained sludge, continuous fermentation was successfully achieved. We chose the dilution rate on the basis of the maximum saccharification time; the highest volumetric productivity and ethanol yield were observed at a dilution rate of 0.028 h?1. The volumetric productivity, final ethanol concentration, and % of theoretical ethanol yield were 2.41 g/Lh, 86.1g/L, and 91%, respectively. This SSCF process using the self-flocculating yeast Saccharomyces cerevisiae CHFY0321 illustrates the possibility of realizing cost-effective bioethanol production by eliminating additional saccharification and filtration processes. In addition, flocculent CHFY0321, which our group developed, showed excellent fermentation results under continuous ethanol production.     

Bayesian latent multi‐state modeling for nonequidistant longitudinal electronic health records

Large amounts of longitudinal health records are now available for dynamic monitoring of the underlying processes governing the observations. However, the health status progression across time is not typically observed directly: records are observed only when a subject interacts with the system, yielding irregular and often sparse observations. This suggests that the observed trajectories should be modeled via a latent continuous‐time process potentially as a function of time‐varying covariates. We develop a continuous‐time hidden Markov model to analyze longitudinal data accounting for irregular visits and different types of observations. By employing a specific missing data likelihood formulation, we can construct an efficient computational algorithm. We focus on Bayesian inference for the model: this is facilitated by an expectation‐maximization algorithm and Markov chain Monte Carlo methods. Simulation studies demonstrate that these approaches can be implemented efficiently for large data sets in a fully Bayesian setting. We apply this model to a real cohort where patients suffer from chronic obstructive pulmonary disease with the outcome being the number of drugs taken, using health care utilization indicators and patient characteristics as covariates.     

Monte Carlo simulation of diffusion and reaction in water radiolysis – a study of reactant `jump through' and jump distances

In Monte Carlo simulations of water radiolysis, the diffusion of reactants can be approximated by “jumping” all species randomly, to represent the passage of a short period of time, and then checking their separations. If, at the end of a jump, two reactant species are within a distance equal to the reaction radius for the pair, they are allowed to react in the model. In principle, the possibility exists that two reactants could “jump through” one another and end up with a separation larger than the reaction radius with no reaction being scored. Ignoring this possibility would thus reduce the rate of reaction below that intended by such a model. By making the jump times and jump distances shorter, any error introduced by `jump through' is made smaller. This paper reports numerical results of a systematic study of `jump through' in Monte Carlo simulations of water radiolysis. With a nominal jump time of 3 ps, it is found that more than 40% of the reactions of the hydrated electron with itself and of the H atom with itself occur when reactions during `jump through' are allowed. For all other reactions, for which the effect is smaller, the contributions of `jump through' lie in the range l%–16% of the total. Corrections to computed rate constants for two reactions are evaluated for jump times between 0.1 and 30 ps. It is concluded that jump-through corrections are desirable in such models for jump times that exceed about 1 ps or even less. In a separate study, we find that giving all species of a given type the same size jump in a random direction yields results that are indistinguishable from those when the jump sizes are selected from a Gaussian distribution. In this comparison, the constant jump size is taken to be the root-mean-square jump size from the Gaussian distribution. Received: 8 September 1997 / Accepted in revised form: 27 October 1997     

Identification and estimation algorithm for stochastic neural system

An algorithm for the estimation of stochastic processes in a neural system is presented. This process is defined here as the continuous stochastic process reflecting the dynamics of the neural system which has some inputs and generates output spike trains. The algorithm proposed here is to identify the system parameters and then estimate the stochastic process called neural system process here. These procedures carried out on the basis of the output spike trains which are supposed to be the data observed in the randomly missing way by the threshold time function in the neural system. The algorithm is constructed with the well-known Kalman filters and realizes the estimation of the neural system process by cooperating with the algorithm for the parameter estimation of the threshold time function presented previously (Nakao et al., 1983). The performance of the algorithm is examined by applying it to the various spike trains simulated by some artificial models and also to the neural spike trains recorded in cat's optic tract fibers. The results in these applications are thought to prove the effectiveness of the algorithm proposed here to some extent. Such attempts, we think, will serve to improve the characterizing and modelling techniques of the stochastic neural systems.